Convergence of proximal algorithms with stepsize controls for non-linear inverse problems and application to sparse non-negative matrix factorization
Abstract
We consider a general ill-posed inverse problem in a Hilbert space setting by minimizing a misfit functional coupling with a multi-penalty regularization for stabilization. For solving this minimization problem, we investigate two proximal algorithms with stepsize controls: a proximal fixed point algorithm and an alternating proximal algorithm. We prove the decrease of the objective functional and the convergence of both update schemes to a stationary point under mild conditions on the stepsizes. These algorithms are then applied to the sparse and non-negative matrix factorization problems. Based on a priori information of non-negativity and sparsity of the exact solution, the problem is regularized by corresponding terms. In both cases, the implementation of our proposed algorithms is straight-forward since the evaluation of the proximal operators in these problems can be done explicitly. Finally, we test the proposed algorithms for the non-negative sparse matrix factorization problem with both simulated and real-world data and discuss reconstruction performance, convergence, as well as achieved sparsity.
References
[1]
Alexandrov T, Becker M, Deininger SO, Ernst G, Wehder L, Grasmair M, von Eggeling F, Thiele H, and Maass P Spatial segmentation of imaging mass spectrometry data with edge-preserving image denoising and clustering J. Proteome Res. 2010 9 12 6535-6546
[2]
Alexandrov T and Kobarg JH Efficient spatial segmentation of large imaging mass spectrometry datasets with spatially aware clustering Bioinformatics 2011 27 13 i230-i238
[3]
Attouch H, Bolte J, and Svaiter BF Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods Math. Program. 2013 137 1-2 91-129
[4]
Berry MW, Browne M, Langville AN, Pauca VP, and Plemmons RJ Algorithms and applications for approximate nonnegative matrix factorization Comput. Stat. Data Analys. 2007 52 1 155-173
[5]
Bolte J, Sabach S, and Teboulle M Proximal alternating linearized minimization for nonconvex and nonsmooth problems Math. Program. 2014 146 1-2 459-494
[6]
Brunet J, Tamayo P, Golub TR, and Mesirov JP Metagenes and molecular pattern discovery using matrix factorization Proc. Natl. Acad. Sci. 2004 101 12 4164-4169
[7]
Daubechies I, Defrise M, and De Mol C Sparsity-enforcing regularisation and ISTA revisited Inverse Problems 2016 32 10 104001
[8]
Daubechies I, Defrise M, and Demol C An iterative thresholding algorithm for linear inverse problems with a sparsity constraint Comm. Pure Appl. Math. 2004 57 1413-1541
[9]
Drakakis K, Rickard S, Fréin RD, and Cichocki A Analysis of financial data using non-negative matrix factorization Int. Math. Forum 2008 3 1853-1870
[10]
Engl HW, Hanke M, and Neubauer A Regularization of inverse problems 1996 Dordrecht Kluwer
[11]
Engl HW, Kunisch K, and Neubauer A Convergence rates for Tikhonov regularization of non-linear ill-posed problems Inverse Problems 1989 5 4 523
[12]
Greene D, Cagney G, Krogan N, and Cunningham P Ensemble non-negative matrix factorization methods for clustering protein–protein interactions Bioinformatics 2008 24 15 1722-1728
[13]
Guo Z, Lin S, and Shi L Distributed learning with multi-penalty regularization Appl. Comput. Harmon. Anal. 2019 46 478-499
[14]
Hào DN and Quyen TNT Convergence rates for total variation regularization of coefficient identification problems in elliptic equations I Inverse Problems 2011 27 075008
[15]
Hào DN and Quyen TNT Convergence rates for total variation regularization of coefficient identification problems in elliptic equations ii J. Math. Anal. Appl. 2012 388 1 593-616
[16]
Hoyer, P.O.: Non-negative sparse coding. In: Proceedings of the 2002 12th IEEE workshop on neural networks for signal processing, 2002, pp. 557–565. IEEE (2002)
[17]
Ito K, Jin B, and Takeuchi T Multi-parameter Tikhonov regularization Methods and Applications of Analysis 2011 18 1 31-46
[18]
Lee DD and Seung HS Learning the parts of objects by non-negative matrix factorization Nature 1999 401 6755 788-791
[19]
Lorenz DA Convergence rates and source conditions for Tikhonov regularization with sparsity constraints J. Inv Ill-posed problems 2008 16 463-478
[20]
Lorenz DA, Maass P, and Muoi PQ Gradient descent methods based on quadratic approximations of Tikhonov functionals with sparsity constraints: theory and numerical comparison of stepsize rules Electron. Trans. Numer. Anal. 2012 39 437-463
[21]
Mairal J, Bach F, Ponce J, and Sapiro G Online learning for matrix factorization and sparse coding J. Mach. Learn. Res. 2010 11 19-60
[22]
Moreau J Proximité et dualité dans un espace hilbertien Bulletin de la Société Mathématique de France 1965 93 273-299
[23]
Muoi PQ Reconstructing conductivity coefficients based on sparsity regularization and measured data in electrical impedance tomography Inverse Problems in Science and Engineering 2015 23 8 1366-1387
[24]
Muoi PQ, Hào DN, Maass P, and Pidcock M Semismooth Newton and quasi-Newton methods in weighted l1-regularization Journal of Inverse and Ill-Posed Problems 2013 21 5 665-693
[25]
Muoi PQ, Hào DN, Maass P, and Pidcock M Descent gradient methods for nonsmooth minimization problems in ill-posed problems J. Comput. Appl. Math. 2016 298 105-122
[26]
Muoi PQ, Hào DN, Sahoo SK, Tang D, Cong NH, and Dang C Inverse problems with nonnegative and sparse solutions: Algorithms and application to the phase retrieval problem Inverse Problems 2018 34 5 055007
[27]
Nesterov, Y.: Gradient methods for minimizing composite objective function CORE discussion papers, 2007076, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE (2007)
[28]
Sivananthan S et al. Multi-penalty regularization in learning theory J. Complex. 2016 36 141-165
[29]
Smaragdis, P., Brown, J.C.: Non-negative matrix factorization for polyphonic music transcription. In: 2003 IEEE workshop on applications of signal processing to audio and acoustics, pp. 177–180. IEEE (2003)
[30]
Wang W, Lu S, Mao H, and Cheng J Multi-parameter Tikhonov regularization with the l0 sparsity constraint Inverse Problems 2013 29 6 065018
[31]
Xu Y and Yin W A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion SIAM J. Imaging Sci. 2013 6 3 1758-1789
Index Terms
- Convergence of proximal algorithms with stepsize controls for non-linear inverse problems and application to sparse non-negative matrix factorization
Index terms have been assigned to the content through auto-classification.
Recommendations
Improved Symbolic and Numerical Factorization Algorithms for Unsymmetric Sparse Matrices
We present algorithms for the symbolic and numerical factorization phases in the direct solution of sparse unsymmetric systems of linear equations. We have modified a classical symbolic factorization algorithm for unsymmetric matrices to inexpensively ...
Damping proximal coordinate descent algorithm for non-convex regularization
Non-convex regularization has attracted much attention in the fields of machine learning, since it is unbiased and improves the performance on many applications compared with the convex counterparts. The optimization is important but difficult for non-...
Sparse topical analysis of dyadic data using matrix tri-factorization
Many applications involve dyadic data, where associations between one pair of domain entities, such as documents, words and associations between another pair, such as documents, users are completely observed. We motivate the analysis of such dyadic data ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© Springer Science+Business Media, LLC, part of Springer Nature 2020.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 01 December 2020
Accepted: 04 December 2019
Received: 29 April 2019
Author Tags
Author Tags
Qualifiers
- Research-article
Funding Sources
- NAFOSTED
- German Federal Ministry of Education and Research
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 22 Jan 2025