×

Convergence of proximal algorithms with stepsize controls for non-linear inverse problems and application to sparse non-negative matrix factorization. (English) Zbl 1455.65091

Summary: 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.

MSC:

65J22 Numerical solution to inverse problems in abstract spaces
65K05 Numerical mathematical programming methods
49M37 Numerical methods based on nonlinear programming
49J52 Nonsmooth analysis
65F50 Computational methods for sparse matrices
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alexandrov, T.; Becker, M.; Deininger, SO; Ernst, G.; Wehder, L.; Grasmair, M.; von Eggeling, F.; Thiele, H.; Maass, P., Spatial segmentation of imaging mass spectrometry data with edge-preserving image denoising and clustering, J. Proteome Res., 9, 12, 6535-6546 (2010) · doi:10.1021/pr100734z
[2] Alexandrov, T.; Kobarg, JH, Efficient spatial segmentation of large imaging mass spectrometry datasets with spatially aware clustering, Bioinformatics, 27, 13, i230-i238 (2011) · doi:10.1093/bioinformatics/btr246
[3] Attouch, H.; Bolte, J.; Svaiter, BF, Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Math. Program., 137, 1-2, 91-129 (2013) · Zbl 1260.49048 · doi:10.1007/s10107-011-0484-9
[4] Berry, MW; Browne, M.; Langville, AN; Pauca, VP; Plemmons, RJ, Algorithms and applications for approximate nonnegative matrix factorization, Comput. Stat. Data Analys., 52, 1, 155-173 (2007) · Zbl 1452.90298 · doi:10.1016/j.csda.2006.11.006
[5] Bolte, J.; Sabach, S.; Teboulle, M., Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program., 146, 1-2, 459-494 (2014) · Zbl 1297.90125 · doi:10.1007/s10107-013-0701-9
[6] Brunet, J.; Tamayo, P.; Golub, TR; Mesirov, JP, Metagenes and molecular pattern discovery using matrix factorization, Proc. Natl. Acad. Sci., 101, 12, 4164-4169 (2004) · doi:10.1073/pnas.0308531101
[7] Daubechies, I.; Defrise, M.; De Mol, C., Sparsity-enforcing regularisation and ISTA revisited, Inverse Problems, 32, 10, 104001 (2016) · Zbl 1402.65048 · doi:10.1088/0266-5611/32/10/104001
[8] Daubechies, I.; Defrise, M.; Demol, C., An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Comm. Pure Appl. Math., 57, 1413-1541 (2004) · Zbl 1077.65055 · doi:10.1002/cpa.20042
[9] Drakakis, K.; Rickard, S.; Fréin, RD; Cichocki, A., Analysis of financial data using non-negative matrix factorization, Int. Math. Forum, 3, 1853-1870 (2008) · Zbl 1160.91395
[10] Engl, HW; Hanke, M.; Neubauer, A., Regularization of inverse problems (1996), Dordrecht: Kluwer, Dordrecht · Zbl 0859.65054 · doi:10.1007/978-94-009-1740-8
[11] Engl, HW; Kunisch, K.; Neubauer, A., Convergence rates for Tikhonov regularization of non-linear ill-posed problems, Inverse Problems, 5, 4, 523 (1989) · Zbl 0695.65037 · doi:10.1088/0266-5611/5/4/007
[12] Greene, D.; Cagney, G.; Krogan, N.; Cunningham, P., Ensemble non-negative matrix factorization methods for clustering protein-protein interactions, Bioinformatics, 24, 15, 1722-1728 (2008) · doi:10.1093/bioinformatics/btn286
[13] Guo, Z.; Lin, S.; Shi, L., Distributed learning with multi-penalty regularization, Appl. Comput. Harmon. Anal., 46, 478-499 (2019) · Zbl 1431.68107 · doi:10.1016/j.acha.2017.06.001
[14] Hào, DN; Quyen, TNT, Convergence rates for total variation regularization of coefficient identification problems in elliptic equations I, Inverse Problems, 27, 075008 (2011) · Zbl 1267.35253 · doi:10.1088/0266-5611/27/7/075008
[15] Hào, DN; Quyen, TNT, Convergence rates for total variation regularization of coefficient identification problems in elliptic equations ii, J. Math. Anal. Appl., 388, 1, 593-616 (2012) · Zbl 1235.35099 · doi:10.1016/j.jmaa.2011.11.008
[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.; Takeuchi, T., Multi-parameter Tikhonov regularization, Methods and Applications of Analysis, 18, 1, 31-46 (2011) · Zbl 1285.65032 · doi:10.4310/MAA.2011.v18.n1.a2
[18] Lee, DD; Seung, HS, Learning the parts of objects by non-negative matrix factorization, Nature, 401, 6755, 788-791 (1999) · Zbl 1369.68285 · doi:10.1038/44565
[19] Lorenz, DA, Convergence rates and source conditions for Tikhonov regularization with sparsity constraints, J. Inv Ill-posed problems, 16, 463-478 (2008) · Zbl 1161.65041 · doi:10.1515/JIIP.2008.025
[20] Lorenz, DA; Maass, P.; 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., 39, 437-463 (2012) · Zbl 1287.65105
[21] Mairal, J.; Bach, F.; Ponce, J.; Sapiro, G., Online learning for matrix factorization and sparse coding, J. Mach. Learn. Res., 11, 19-60 (2010) · Zbl 1242.62087
[22] Moreau, J., Proximité et dualité dans un espace hilbertien, Bulletin de la Société Mathématique de France, 93, 273-299 (1965) · Zbl 0136.12101 · doi:10.24033/bsmf.1625
[23] Muoi, PQ, Reconstructing conductivity coefficients based on sparsity regularization and measured data in electrical impedance tomography, Inverse Problems in Science and Engineering, 23, 8, 1366-1387 (2015) · Zbl 1326.92048 · doi:10.1080/17415977.2015.1018678
[24] Muoi, PQ; Hào, DN; Maass, P.; Pidcock, M., Semismooth Newton and quasi-Newton methods in weighted l1-regularization, Journal of Inverse and Ill-Posed Problems, 21, 5, 665-693 (2013) · Zbl 1276.65034 · doi:10.1515/jip-2013-0031
[25] Muoi, PQ; Hào, DN; Maass, P.; Pidcock, M., Descent gradient methods for nonsmooth minimization problems in ill-posed problems, J. Comput. Appl. Math., 298, 105-122 (2016) · Zbl 1332.65072 · doi:10.1016/j.cam.2015.11.039
[26] Muoi, PQ; Hào, DN; Sahoo, SK; Tang, D.; Cong, NH; Dang, C., Inverse problems with nonnegative and sparse solutions: Algorithms and application to the phase retrieval problem, Inverse Problems, 34, 5, 055007 (2018) · Zbl 1393.78014 · doi:10.1088/1361-6420/aab6c9
[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., Multi-penalty regularization in learning theory, J. Complex., 36, 141-165 (2016) · Zbl 1350.68219 · doi:10.1016/j.jco.2016.05.003
[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.; Cheng, J., Multi-parameter Tikhonov regularization with the l0 sparsity constraint, Inverse Problems, 29, 6, 065018 (2013) · Zbl 1273.65068 · doi:10.1088/0266-5611/29/6/065018
[31] Xu, Y.; Yin, W., A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion, SIAM J. Imaging Sci., 6, 3, 1758-1789 (2013) · Zbl 1280.49042 · doi:10.1137/120887795
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.