Stable recovery of low rank matrices from nuclear norm minimization. (English) Zbl 1395.90203

Summary: Low rank matrix recovery is a new topic drawing the attention of many researchers which addresses the problem of recovering an unknown low rank matrix from few linear measurements. The matrix Dantzig selector and the matrix Lasso are two important algorithms based on nuclear norm minimization. In this paper, we first prove some decay properties of restricted isometry constants, then we discuss the recovery errors of these two algorithms and give a new bound of restricted isometry constant to guarantee stable recovery, which improves the results of [E. Candès and Y. Plan, IEEE Trans. Inf. Theory 57, No. 4, 2342–2359 (2011; Zbl 1366.90160)].


90C25 Convex programming
94A12 Signal theory (characterization, reconstruction, filtering, etc.)


Zbl 1366.90160


Full Text: DOI


[1] Argyriou, A., Micchelli, C.A., Pontil, M. Convex multi-task feature learning. Machine Learning., 73(3): 243-272 (2008) · Zbl 1470.68073 · doi:10.1007/s10994-007-5040-8
[2] Beck, C.; Andrea, RD, Computational study and comparisons of LFT reducibility methods (1998)
[3] Bickel, P., Ritov, Y., Tsybakov, A. Simultaneous analysis of Lasso and Dantzig Selector. Ann. Statist., 37(4): 1705-1732 (2009) · Zbl 1173.62022 · doi:10.1214/08-AOS620
[4] Blanchard, J., Cartis, C., Tanner, J. Decay properties of restricted isometry constants. IEEE Signal Processing Letters, 16(7): 572-575 (2009) · doi:10.1109/LSP.2009.2020882
[5] Cai, J.F., Candès, E.J., Shen, Z.W. A singular value thresholding algorithm for matrix completion. SIAM J. Optim., 20(4): 1956-1982 (2010) · Zbl 1201.90155 · doi:10.1137/080738970
[6] Cai, J.F., Osher, S., Shen, Z.W. Split Bregman methods and frame based image restoration. Multiscale Model. Simul., 8(2): 337-369 (2009) · Zbl 1189.94014 · doi:10.1137/090753504
[7] Cai, J.F., Osher, S., Shen, Z.W. Convergence of the linearized Bregman iteration for ℓ1-norm minimization. Math. Comp., 78(268): 2127-2136 (2009) · Zbl 1198.65103 · doi:10.1090/S0025-5718-09-02242-X
[8] Cai, T.T., Wang, L., Xu, G.W. Shifting inequality and recovery of sparse signals, IEEE Trans. Signal Process, 58(3): 1300-1308 (2010) · Zbl 1392.94117
[9] Candès, E.J. Compressive sampling. International Congress of Mathematics, 3: 1433-1452 (2006) · Zbl 1130.94013
[10] Candès, E.J. The restricted isometry property and its implications for compressed sensing. C. R. Acad. Sci. Paris. Ser.1, 346: 589-592 (2008) · Zbl 1153.94002 · doi:10.1016/j.crma.2008.03.014
[11] 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(4): 2342-2359 (2009) · Zbl 1366.90160 · doi:10.1109/TIT.2011.2111771
[12] Candès, E.J., Recht, B. Exact matrix completion via convex optimization. Found. Comput. Math., 9: 717-772 (2008) · Zbl 1219.90124 · doi:10.1007/s10208-009-9045-5
[13] Candès, E.J., Tao, T. The Dantzig selector: statistical estimation when p is much larger than n. Ann. Statist, 35(6): 2313-2351 (2007) · Zbl 1139.62019 · doi:10.1214/009053606000001523
[14] Chartrand, R., Staneva, V. Restricted isometry properties and nonconvex compressive sensing. Inverse Problems, 24: 1-14 (2008) · Zbl 1143.94004 · doi:10.1088/0266-5611/24/3/035020
[15] Goldfarb, D., Ma, S.Q. Convergence of fixed-point continuation algorithms for matrix rank minimization. Found. Comput. Math., 11(2): 183-210 (2011) · Zbl 1219.90195 · doi:10.1007/s10208-011-9084-6
[16] Horn, R.A., Johnson, C.R. Topics in matrix analysis. Cambridge University Press, New York, 1991 · Zbl 0729.15001 · doi:10.1017/CBO9780511840371
[17] Ji, H., Huang, S.B., Shen, Z.W., Xu, Y.H. Robust video restoration by joint sparse and low rank matrix approximation. SIAM J. Imaging Sci., 4(4): 1122 C-1142(2011) · Zbl 1234.68451 · doi:10.1137/100817206
[18] Lin, Z.C., Chen, M.M., Wu, L.Q. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices. Technical Report UILU-ENG-09-2215, UIUC, October, 2009
[19] Ma, S., Goldfarb, D., Chen, L. Fixed point and bregman iterative methods for matrix rank minimization. Math. Program, 128(1-2): 321-353 (2011) · Zbl 1221.65146 · doi:10.1007/s10107-009-0306-5
[20] Mo, Q., Li, S. New bounds on the restricted isometry constant δ2r. Appl. Comput. Harmon. Anal., 31(3): 460-468 (2011) · Zbl 1231.94027 · doi:10.1016/j.acha.2011.04.005
[21] Mohan, K., Fazel, M. New restricted isometry results for noisy low-rank recovery. ISIT, Austin, 2010 · doi:10.1109/ISIT.2010.5513471
[22] Needall, D., Tropp, J. Cosamp: Iterative signal recovery from incomplete and inaccurate samples. Appl. Comput. Harmon. Anal., 31(1): 59-73 (2010)
[23] Oymak, S.; Mohan, K.; Fazel, M.; Hassibi, B., A simplified approach to recovery conditions for low-rank matrices (2011)
[24] Recht, B., Fazel, M., Parrilo, P. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev., 14: 1-46 (2009)
[25] Rennie, JDM; Srebro, N., Fast maximum margin matrix factorization for collaborative prediction (2005)
[26] Shen, Y., Li, S. Restricted p-isometry property and its application for nonconvex compressive sensing, Adv. Comput. Math., 37(3): 441-452 (2011) · Zbl 1260.94028 · doi:10.1007/s10444-011-9219-y
[27] Uchiyama, M., Subadditivy of eigenvalue sums, 1405-1412 (2005) · Zbl 1093.93024
[28] Weinberger, K.Q., Saul, L.K. Unsupervised learning of image manifolds by semidefinite programming. Int. J. Computer Vision, 70(1): 77-90 (2006) · doi:10.1007/s11263-005-4939-z
[29] Yuan, M., Ekici, A., Lu, Z. Monteiro, R. Dimension reduction and coefficient estimation in multivariate linear regression. J. Roy. Statist. Soc. Ser. B, 69: 329-346 (2007) · Zbl 07555355 · doi:10.1111/j.1467-9868.2007.00591.x
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.