×

Convergence of projected Landweber iteration for matrix rank minimization. (English) Zbl 1302.65144

Summary: We study the performance of the projected Landweber iteration (PLW) for the general low rank matrix recovery. The PLW was first proposed by H. Zhang and L. Z. Chen (2010) [J. Comput. Appl. Math. 235, No. 3, 593–601 (2010; Zbl 1225.65049)] based on the sparse recovery algorithm APG in the matrix completion setting, and numerical experiments have been given to show its efficiency [loc. cit.]. In this paper, we focus on providing a convergence rate analysis of the PLW in the general setting of low rank matrix recovery with the affine transform having the matrix restricted isometry property. We show robustness of the algorithm to noise with a strong geometric convergence rate even for noisy measurements provided that the affine transform satisfies a matrix restricted isometry property condition.

MSC:

65J15 Numerical solutions to equations with nonlinear operators

Citations:

Zbl 1225.65049
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Blumensath, T.; Davies, M., Iterative thresholding for sparse approximations, J. Fourier Anal. Appl., 14, 629-654 (2008) · Zbl 1175.94060
[2] Blumensath, T.; Davies, M., Iterative hard thresholding for compressive sensing, Appl. Comput. Harmon. Anal., 27, 265-274 (2009) · Zbl 1174.94008
[3] Basri, R.; Jacobs, D., Lambertian reflectance and linear subspaces, IEEE Trans. Pattern Anal. Mach. Intell., 25, 218-233 (2003)
[4] Bahmani, S.; Raj, B., A unifying analysis of projected gradient descent for \(l_p\)-constrained least squares, Appl. Comput. Harmon. Anal., 34, 366-378 (2013) · Zbl 1268.65054
[5] Candès, E. J., The restricted isometry property and its implications for compressed sensing, C. R. Math. Acad. Sci. Paris, Ser. I, 346, 589-592 (2008) · Zbl 1153.94002
[6] Candès, E. J.; Plan, Y., Tight oracle bounds for low-rank recovery from a minimal number of random measurements, IEEE Trans. Inform. Theory, 57, 2342-2359 (2011) · Zbl 1366.90160
[7] Cai, J. F.; Candès, E. J.; Shen, Z. W., A singular value thresholding algorithm for matrix completion, SIAM J. Optim., 20, 1956-1982 (2010) · Zbl 1201.90155
[8] Candès, E. J.; Li, X.; Ma, Y.; Wright, J., Robust principal component analysis?, J. ACM, 58 (2011) · Zbl 1327.62369
[9] Candes, E. J.; Recht, B., Exact matrix completion via convex optimization, Found. Comput. Math., 9, 717-772 (2009) · Zbl 1219.90124
[10] Candès, E. J.; Romberg, J.; Tao, T., Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory, 52, 489-509 (2006) · Zbl 1231.94017
[11] Candès, E. J.; Romberg, J.; Tao, T., Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math., 59, 1207-1223 (2006) · Zbl 1098.94009
[12] Candès, E. J.; Tao, T., The power of convex relaxation: Near-optimal matrix completion, IEEE Trans. Inform. Theory, 56, 2053-2080 (2010) · Zbl 1366.15021
[13] Cai, T.; Zhang, A., Sharp RIP bound for sparse signal and low-rank matrix recovery, Appl. Comput. Harmon. Anal., 35, 74-93 (2013) · Zbl 1310.94021
[14] Daubechies, I.; Fornasier, M.; Loris, I., Accelerated projected gradient method for linear inverse problems with sparsity constraints, J. Fourier Anal. Appl., 14, 764-792 (2008) · Zbl 1175.65062
[15] Fazel, M., Matrix rank minimization with applications (2002), Stanford University, PhD thesis
[16] Foucart, S., Hard thresholding pursuit: An algorithm for compressive sensing, SIAM J. Numer. Anal., 49, 2543-2563 (2011) · Zbl 1242.65060
[17] Fornasier, M.; Rauhut, H.; Ward, R., Low-rank matrix recovery via iteratively reweighted least squares minimization, SIAM J. Optim., 21, 1614-1640 (2011) · Zbl 1236.65044
[18] Gross, D., Recovering low-rank matrices from few coefficients in any basis, IEEE Trans. Inform. Theory, 57, 1548-1566 (2011) · Zbl 1366.94103
[19] Gross, D.; Liu, Y. K.; Flammia, S. T.; Becker, S.; Eisert, J., Quantum state tomography via compressed sensing, Phys. Rev. Lett., 105, 150401 (2010)
[20] Goldfarb, D.; Ma, S., Convergence of fixed point continuation algorithms for matrix rank minimization, Found. Comput. Math., 11, 183-210 (2011) · Zbl 1219.90195
[21] Horn, R.; Johnson, C., Matrix Analysis (1990), Cambridge University Press · Zbl 0704.15002
[22] Hale, E. T.; Yin, W.; Zhang, Y., Fixed-point continuation for \(l_1\)-minimization: Methodology and convergence, SIAM J. Optim., 19, 1107-1130 (2008) · Zbl 1180.65076
[23] Keshavan, R. H.; Montanari, A.; Oh, S., Matrix completion from a few entries, IEEE Trans. Inform. Theory, 56, 2980-2998 (2010) · Zbl 1366.62111
[24] Keshavan, R. H.; Oh, S., OptSpace: A gradient descent algorithm on the Grassman manifold for matrix completion (2009), available at
[25] Kramer, F.; Ward, R., New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property, SIAM J. Math. Anal., 43, 1269-1281 (2011) · Zbl 1247.15019
[26] Lee, K.; Bresler, Y., ADMiRA: Atomic decomposition for minimum rank approximation, IEEE Trans. Inform. Theory, 56, 4402-4416 (2010) · Zbl 1366.94112
[27] Liu, Z.; Vandenberghe, L., Interior-point method for nuclear norm approximation with application to system identification, SIAM J. Matrix Anal. Appl., 31, 1235-1256 (2008) · Zbl 1201.90151
[28] Mohan, K.; Fazel, M., Reweighted nuclear norm minimization with application to system identification, (Proc. of the American Control Conference (2010)), 2953-2959
[29] Mohan, K.; Fazel, M., Iterative reweighted algorithms for matrix rank minimization, J. Mach. Learn. Res., 13, 3253-3285 (2012)
[30] Ma, S.; Goldfarb, D.; Chen, L., Fixed point and Bregman iterative methods for matrix rank minimization, Math. Program., 128, 321-353 (2011) · Zbl 1221.65146
[31] Mazumder, R.; Hastie, T.; Tibshirani, R., Spectral regularization algorithms for learning large incomplete matrices, J. Mach. Learn. Res., 11, 2287-2322 (2010) · Zbl 1242.68237
[32] Meka, R.; Jain, P.; Dhillon, I. S., Guaranteed rank minimization via singular value projection, (Proc. of the Neural Information Processing Systems Conference (2010))
[33] Natarajan, B. K., Sparse approximate solutions to linear systems, SIAM J. Comput., 24, 227-234 (1995) · Zbl 0827.68054
[34] Needell, D.; Tropp, J. A., CoSaMP: Iterative signal recovery from noisy samples, Appl. Comput. Harmon. Anal., 26, 301-321 (2008) · Zbl 1163.94003
[35] Osher, S.; Mao, Y.; Dong, B.; Yin, W., Fast linearized Bregman iteration for compressive sensing and sparse denoising, Commun. Math. Sci., 8, 93-111 (2010) · Zbl 1190.49040
[36] Oymak, S.; Mohan, K.; Fazel, M.; Hassibi, B., A simplified approach to recovery conditions for low rank matrices, (IEEE International Symposium on Information Theory Proceedings. IEEE International Symposium on Information Theory Proceedings, ISIT (2011)), 2318-2322
[37] Recht, B., A simpler approach to matrix completion, J. Mach. Learn. Res., 12, 3413-3430 (2011) · Zbl 1280.68141
[38] Recht, B.; Fazel, M.; Parrilo, P., Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 471-501 (2010) · Zbl 1198.90321
[39] Srebro, N.; Rennie, J. D.M.; Jakkola, T. S., Maximum-margin matrix factorization, (Advances in Neural Information Processing Systems (2005))
[40] Toh, K. C.; Yun, S. W., An accelerated proximal gradient algorithm for nuclear norm regularized least squares problem, Pac. J. Optim., 6, 615-640 (2010) · Zbl 1205.90218
[41] Wang, H.; Li, S., The bounds of restricted isometry constants for low rank matrices recovery, Sci. China Math., 56, 1117-1127 (2013) · Zbl 1273.90156
[42] Yin, W.; Osher, S.; Goldfarb, D.; Darbon, J., Bregman iterative algorithms for \(l_1\)-minimization with applications to compressed sensing, SIAM J. Imaging Sci., 1, 143-168 (2008) · Zbl 1203.90153
[43] Zhang, H.; Cheng, L. Z., Projected Landweber iteration for matrix completion, J. Comput. Appl. Math., 235, 593-601 (2010) · Zbl 1225.65049
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.