Uniqueness conditions for low-rank matrix recovery. (English) Zbl 1247.65056

The authors address the problem of recovering an unknown low-rank matrix from few linear measurements. In this respect, they consider the theoretical question of how many measurements are needed via any method whatsoever – tractable or not, and show thet for a family of random measurements ensembles \(m \geqslant 4nr - 4r^2\) and \(m \geqslant 2nr - r^2 + 1\) measurements are sufficient to guarantee strong recovery and weak recovery, respectively, by rank minimization (where \(n\) is the dimension of the matrix and \(r\) the fixed rank value).


65F30 Other matrix algorithms (MSC2010)
15A83 Matrix completion problems


Full Text: DOI


[1] Cai, J. F.; Candès, E. J.; Shen, Z., A singular value thresholding algorithm for matrix completion, SIAM J. Optim., 20, 4, 1956-1982 (2008) · Zbl 1201.90155
[2] Candès, E. J.; Plan, Y., Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements, IEEE Trans. Inform. Theory, 57, 4, 2342-2359 (2010) · Zbl 1366.90160
[3] Candès, E. J.; Plan, Y., Matrix completion with noise, Proc. IEEE, 98, 6, 925-936 (2010)
[4] Candès, E. J.; Recht, B., Exact matrix completion via convex optimization, Found. Comput. Math., 9, 6, 717-772 (2009) · Zbl 1219.90124
[5] Candès, E. J.; Romberg, J.; Tao, T., Robust uncertainty principles: Exact signal reconstruction from highly incomplete Fourier information, IEEE Trans. Inform. Theory, 52, 2, 489-509 (2006) · Zbl 1231.94017
[6] Dai, W.; Milenkovic, O., SET: an algorithm for consistent matrix completion, (ICASSP 2010 IEEE Int. Conf. (2010), IEEE), 3646-3649
[7] Gross, D., Recovering low-rank matrices from few coefficients in any basis, IEEE Trans. Inform. Theory, 57, 3, 1548-1566 (2011) · Zbl 1366.94103
[8] Lee, K.; Bresler, Y., Admira: Atomic decomposition for minimum rank approximation, IEEE Trans. Inform. Theory, 56, 9, 4402-4416 (2010) · Zbl 1366.94112
[9] Lorentz, G. G.; von Golitschek, M.; Makovoz, Y., Constructive Approximation: Advanced Problems (1996), Springer: Springer Berlin · Zbl 0910.41001
[10] Ma, S.; Goldfarb, D.; Chen, L., Fixed point and Bregman iterative methods for matrix rank minimization, Math. Program., 1-33 (2009)
[15] Parrilo, P. A.; Willsky, A. S.; Chandrasekaran, V.; Recht, B., The convex geometry of linear inverse problems (2010), available at
[17] Recht, B.; Fazel, M.; Parrilo, P. A., Guaranteed minimum rank solutions to linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 3, 471-501 (2010) · Zbl 1198.90321
[18] Tan, V. Y.F.; Balzano, L.; Draper, S. C., Rank minimization over finite fields: Fundamental limits and coding-theoretic interpretations, IEEE Trans. Inform. Theory, 58, 4, 2018-2039 (2012) · Zbl 1365.94190
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.