Convergence and stability of iteratively reweighted least squares for low-rank matrix recovery

Yun Cai; Song Li

doi:10.3934/ipi.2017030

Article Contents

2017, Volume 11, Issue 4: 643-661. Doi: 10.3934/ipi.2017030

This issue Previous Article A discrete Liouville identity for numerical reconstruction of Schrödinger potentials Next Article On the lifting of deterministic convergence rates for inverse problems with stochastic noise

Convergence and stability of iteratively reweighted least squares for low-rank matrix recovery

Yun Cai^1, and
Song Li^2, ,

1.
Department of Mathematics, Nanjing University of Chinese Medicine, Nanjing, Jiangsu 210023, China
2.
School of Mathematical Science, Zhejiang University, Hangzhou, Zhejiang 310027, China

^* Corresponding author: songli@zju.edu.cn
^* Corresponding author: songli@zju.edu.cn

Received: October 31, 2015

Revised: March 31, 2017

Published: October 2017

This work is supported by National Natural Science Foundation of China under Grant No. 11626133 and 11531013.

Abstract Full Text(HTML) Related Papers Cited by

Abstract

In this paper, we study the theoretical properties of iteratively reweighted least squares algorithm for recovering a matrix (IRLS-M for short) from noisy linear measurements. The IRLS-M was proposed by Fornasier et al. (2011) [17] for solving nuclear norm minimization and by Mohan et al. (2012) [31] for solving Schatten-$p$ (quasi) norm minimization ($0 < p≤q1$) in noiseless case, based on the iteratively reweighted least squares algorithm for sparse signal recovery (IRLS for short) (Daubechies et al., 2010) [15], and numerical experiments have been given to show its efficiency (Fornasier et al. and Mohan et al.) [17], [31]. In this paper, we focus on providing convergence and stability analysis of iteratively reweighted least squares algorithm for low-rank matrix recovery in the presence of noise. The convergence of IRLS-M is proved strictly for all $0 < p≤q1$. Furthermore, when the measurement map $\mathcal{A}$ satisfies the matrix restricted isometry property (M-RIP for short), we show that the IRLS-M is stable for $0 < p≤q1$. Specially, when $p=1$, we prove that the M-RIP constant $δ_{2r} < \sqrt{2}-1$ is sufficient for IRLS-M to recover an unknown (approximately) low rank matrix with an error that is proportional to the noise level. The simplicity of IRLS-M, along with the theoretical guarantees provided in this paper, make a compelling case for its adoption as a standard tool for low rank matrix recovery.

Keywords:

Mathematics Subject Classification: Primary: 15A83, 90C25; Secondary: 94A12.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	D. Ba, B. Babadi, P. L. Purdon and E. N. Brown, Convergence and stability of iteratively re-weighted least squares algorithms, IEEE Trans. Signal. Process., 62 (2014), 183-195. doi: 10.1109/TSP.2013.2287685.
[2]	R. Basri and D. Jacobs, Lambertian reflectance and linear subspaces, IEEE Trans. Pattern Anal. Mach. Intell., 25 (2003), 218-233. doi: 10.1109/ICCV.2001.937651.
[3]	D. P. Bertsekas, A. Nedic and A. E. Ozdaglar, Convex Analysis and Optimization, Athena Scientific, 2003.
[4]	S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004. doi: 10.1017/CBO9780511804441.
[5]	T. Cai and A. Zhang, Sparse representation of a polytope and recovery of sparse signals and low-rank matrices, IEEE Trans. Inform. Theory., 60 (2014), 122-132. doi: 10.1109/TIT.2013.2288639.
[6]	Y. Cai and S. Li, Convergence analysis of projected gradient descent for Schatten-$p$ nonconvex matrix recovery, Sci. China Math., 58 (2015), 845-858. doi: 10.1007/s11425-014-4949-1.
[7]	E. J. Candés and T. Tao, Decoding by linear programming, IEEE Trans. Inform. Theory., 51 (2005), 4203-4215. doi: 10.1109/TIT.2005.858979.
[8]	E. J. Candés, The restricted isometry property and its implications for compressed sensing, C. R. Math. Acad. Sci. Paris. Ser. I, 346 (2008), 589-592. doi: 10.1016/j.crma.2008.03.014.
[9]	E. J. Candés and B. Recht, Exact Matrix completion via convex optimization, Found. Comput. Math., 9 (2009), 717-772. doi: 10.1007/s10208-009-9045-5.
[10]	E. J. Candés and T. Tao, The power of convex relaxation: Near-optimal matrix completion, IEEE Trans. Inform. Theory., 56 (2010), 2053-2080. doi: 10.1109/TIT.2010.2044061.
[11]	E. J. Candés and Y. Plan, Matrix completion with noise, Proceedings of the IEEE, 98 (2009), 925-936.
[12]	E. J. Candés and Y. Plan, Tight oracle bounds for low-rank recovery from a minimal number of random measurements, IEEE Trans. Inform. Theory., 57 (2011), 2342-2359. doi: 10.1109/TIT.2011.2111771.
[13]	E. J. Candés, Y. Eldar, T. Strohmer and V. Voroninski, Phase retrieval via matrix completion, SIAM J. Imaging Sci., 6 (2013), 199-225. doi: 10.1137/110848074.
[14]	R. Chartrand and W. Yin, Iteratively reweighted algorithms for compressive sensing, International Conference on Acoustics, Speech and Signal Processing, (2008), 3869-3872.
[15]	I. Daubechies, R. Devore, M. Fornasier and C. S. Güntük, Iteratively reweighted least squares minimization for sparse recovery, Commu. Pure. Appl. Math., 63 (2010), 1-38. doi: 10.1002/cpa.20303.
[16]	M. Fazel, Matrix Rank Minimization with Applications, Ph. D thesis, Stanford University, 2002.
[17]	M. Fornasier, H. Rauhut and R. Ward, Low-rank matrix recovery via iteratively reweighted least squares minimization, SIAM J. Optim., 21 (2011), 1614-1640. doi: 10.1137/100811404.
[18]	S. Foucart and M. J. Lai, Sparsest solutions of underdetermined linear systems via $l_{q}$-minimization for $0 < q≤q1$, Appl. Comput. Harmon. Anal., 26 (2009), 395-407. doi: 10.1016/j.acha.2008.09.001.
[19]	M. Grant and S. Boyd, Graph implementations for nonsmooth convex programs, in Recent Advances in Learning and Control (tribute to M. Vidyasagar) (eds. V. Blondel, S. Boyd and H. Kimura), Springer, 2008, 95–110.
[20]	M. Grant and S. Boyd, CVX: Matlab software for disciplined convex programming, Available from: http://web.stanford.edu/boyd/software.html.
[21]	D. Gross, Y. K. Liu, S. T. Flammia, S. Becker and J. Eisert, Quantum state tomography via compressed sensing Phys. Rev. Lett., 105 (2010), 150401. doi: 10.1103/PhysRevLett.105.150401.
[22]	D. Gross, Recovery Low-rank matrices from few coefficients in any basis, IEEE Trans. Inform. Theory., 57 (2011), 1548-1566. doi: 10.1109/TIT.2011.2104999.
[23]	P. Jain, P. Netrapalli and S. Sanghavi, Low-rank matrix completion using alternating minimization, Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, (2013), 665-674. doi: 10.1145/2488608.2488693.
[24]	H. Ji, C. Liu, Z. W. Shen and Y. H. Xu, Robust video denoising using low rank matrix completion, IEEE Conference on Computer Vision and Pattern Recognition, (CVPR), San Francisco, (2010), 1548-1566.
[25]	F. Kramer and R. Ward, New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property, SIAM J. Math. Anal., 43 (2011), 1269-1281. doi: 10.1137/100810447.
[26]	M. J. Lai, Y. Xu and W. Yin, Improved iteratively reweighted least square for unconstrained smoothed $l_{q}$ minimization, SIAM J. Numer. Anal., 51 (2013), 927-957. doi: 10.1137/110840364.
[27]	C. L. Lawson, Contributions to the Theory of Linear Least Maximum Approximation, Ph. D thesis, University of California, Los Angeles, 1961.
[28]	J. Lin and S. Li, Convergence of projected Landweber iteration for matrix rank minimization, Appl. Comput. Harmon. Anal., 36 (2014), 316-325. doi: 10.1016/j.acha.2013.06.005.
[29]	Z. Liu and L. Vandenberghe, Interior-point method for nuclear norm approximation with application to system identification, SIAM J. Matrix Anal. Appl., 31 (2009), 1235-1256. doi: 10.1137/090755436.
[30]	K. Mohan and M. Fazel, Iterative reweighted least squares for matrix rank minimization In Proc. 48th Allerton Conference on Controls and Communications, Allerton, IL, 2010b. doi: 10.1109/ALLERTON.2010.5706969.
[31]	K. Mohan and and M. Fazel, Iterative reweighted algorithms for matrix rank minimization, J. Mach. Learn. Res., 13 (2012), 3441-3473.
[32]	T. Morita and T. Kanade, A sequential factorization method for recovering shape and motion from image streams, IEEE Trans. Pattern Anal. Mach. Intell., 19 (1997), 858-867. doi: 10.1109/34.608289.
[33]	Netflix Prize, Available from: http://www.netflixprize.com/.
[34]	S. Oymak, K. Mohan, M. Fazel and B. Hassibi, A simplified approach to recovery conditions for low rank matrices, in: IEEE International Symposium on Information Theory Proceedings, ISIT, (2011), 2318–2322. doi: 10.1109/ISIT.2011.6033976.
[35]	B. Recht, M. Fazel and P. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52 (2010), 471-501. doi: 10.1137/070697835.
[36]	B. Recht, A simpler approach to matrix completion, J. Mach. Learn. Res., 12 (2011), 3413-3430.
[37]	R. Saab and O. Yilmaz, Sparse recovery by non-convex optimization-instance optimality, Appl. Comput. Harmon. Anal., 29 (2010), 30-48. doi: 10.1016/j.acha.2009.08.002.
[38]	E. van den Berg and M. P. Friedlander, Sparse optimization with least-squares constraints, SIAM J. Optim., 21 (2011), 1201-1229. doi: 10.1137/100785028.
[39]	W. Wang, W. Xu and A. Tang, On the performance of sparse recovery via $l_{p}$-minimization, IEEE Trans. Inform. Theory., 57 (2011), 7255-7278. doi: 10.1109/TIT.2011.2159959.
[40]	K. Wei, J-F. Cai, T. F. Chan and S. Leung, Guarantees of riemannian optimization for low rank matrix recovery, SIAM J. Matrix Anal. Appl., 37 (2016), 1198-1222. doi: 10.1137/15M1050525.
[41]	M-C. Yue and A. Man-Cho So, A perturbation inequality for concave functions of singular values and its applications in low-rank matrix recovery, Appl. Comput. Harmon. Anal., 40 (2016), 396-416. doi: 10.1016/j.acha.2015.06.006.
[42]	M. Zhang, Z. Huang and Y. Zhang, Restricted $p$ -Isometry Properties of Nonconvex matrix recovery, IEEE Trans. Inform. Theory., 59 (2013), 4316-4323. doi: 10.1109/TIT.2013.2250577.
[43]	Z Zhou, J. Wright, X. Li, E. J. Candès and Y. Ma, Stable Principal Component Pursuit Proceedings of International Symposium on Information Theory, (2010). doi: 10.1109/ISIT.2010.5513535.