Stable low-rank matrix recovery via null space properties. (English) Zbl 1388.94018

Summary: The problem of recovering a matrix of low rank from an incomplete and possibly noisy set of linear measurements arises in a number of areas. In order to derive rigorous recovery results, the measurement map is usually modelled probabilistically. We derive sufficient conditions on the minimal amount of measurements ensuring recovery via convex optimization. We establish our results via certain properties of the null space of the measurement map. In the setting where the measurements are realized as Frobenius inner products with independent standard Gaussian random matrices, we show that \(10r(n_1+n_2)\) measurements are enough to uniformly and stably recover an \(n_1\times n_2\) matrix of rank at most \(r\). We then significantly generalize this result by only requiring independent mean zero, variance one entries with four finite moments at the cost of replacing \(10\) by some universal constant. We also study the case of recovering Hermitian rank-\(r\) matrices from measurement matrices proportional to rank-one projectors. For \(m\geq Crn\) rank-one projective measurements onto independent standard Gaussian vectors, we show that nuclear norm minimization uniformly and stably reconstructs Hermitian rank-\(r\) matrices with high probability. Next, we partially de-randomize this by establishing an analogous statement for projectors onto independent elements of a complex projective 4-designs at the cost of a slightly higher sampling rate \(m\geq Crn\log n\). Moreover, if the Hermitian matrix to be recovered is known to be positive semidefinite, then we show that the nuclear norm minimization approach may be replaced by minimizing the \(\ell_q\)-norm of the residual subject to the positive semidefinite constraint (e.g. by a positive semidefinite least squares problem). Then no estimate of the noise level is required a priori. We discuss applications in quantum physics and the phase retrieval problem.


94A12 Signal theory (characterization, reconstruction, filtering, etc.)
Full Text: DOI arXiv


[1] Ahlswede,, R.; Winter,, A., Strong converse for identification via quantum channels., IEEE Trans. Inform. Theory, 48, 579, (2002) · Zbl 1071.94530
[2] Ahmed,, A.; Romberg,, J., Compressive multiplexing of correlated signals., IEEE Trans. Inform. Theory, 61, 498, (2015) · Zbl 1359.94049
[3] Ambainis,, A.; Emerson,, J., Quantum t-designs: t-wise independence in the quantum world., Proceedings of the 22nd Annual IEEE Conference on Computational Complexity, 140, (2007)
[4] Amelunxen,, D.,; Lotz,, M.,; McCoy,, M. B.; Tropp,, J. A., Living on the edge: Phase transitions in convex programs with random data., Inform. Inference, 3, 294, (2014) · Zbl 1339.90251
[5] Balan,, R.,; Bodmann,, B. G.,; Casazza,, P. G.; Edidin,, D., Painless reconstruction from magnitudes of frame coefficients., J. Fourier Anal. Appl., 15:, 501, (2009) · Zbl 1181.42032
[6] Banaszek,, K.,; Cramer,, M.; Gross,, D., Focus on quantum tomography., New J. Phys., 15, 125020, (2013)
[7] Bhatia,, R., Matrix Analysis, (1997)
[8] Bickel,, P.,; Ritov,, Y.; Tsybakov,, A., Simultaneous analysis of Lasso and Dantzig selector., Ann. Stat., 37, 1732, (2009) · Zbl 1173.62022
[9] Boyd,, S.; Vandenberghe,, L., Convex Optimization., (2004) · Zbl 1058.90049
[10] Bruckstein,, A. M.,; Elad,, M.; Zibulevsky,, M., On the uniqueness of nonnegative sparse solutions to underdetermined systems of equations., IEEE Trans. Inform. Theory, 54, 4820, (2008) · Zbl 1319.15007
[11] Candès,, E.,; Strohmer,, T.; Voroninski,, V., PhaseLift: exact and stable signal recovery from magnitude measurements via convex programming., Commun. Pure Appl. Math., 66, 1274, (2013) · Zbl 1335.94013
[12] Candes,, E.; Tao,, T., The power of convex relaxation: near-optimal matrix completion., IEEE Trans. Inform. Theory, 56, 2080, (2010) · Zbl 1366.15021
[13] Candès,, E. J.,; Eldar,, Y. C.,; Strohmer,, T.; Voroninski,, V., Phase retrieval via matrix completion., SIAM J. Imaging Sci., 6, 225, (2013) · Zbl 1280.49052
[14] Candès,, E. J.; Li,, X., Solving quadratic equations via PhaseLift when there are about as many equations as unknowns., Found. Comput. Math., 14, 1026, (2013) · Zbl 1312.90054
[15] Candès,, E. J.,; Li,, X.; Soltanolkotabi,, M., Phase retrieval via Wirtinger flow: Theory and algorithms., IEEE Trans. Inform. Theory, 61, 2007, (2015) · Zbl 1359.94069
[16] Candès,, E. J.; Plan,, Y., Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements., IEEE Trans. Inform. Theory, 57, 2359, (2011) · Zbl 1366.90160
[17] Candès,, E. J.; Recht,, B., Exact matrix completion via convex optimization., Found. Comput. Math., 9, 772, (2009) · Zbl 1219.90124
[18] Carpentier,, A.,; Eisert,, J.,; Gross,, D.; Nickl,, R., Uncertainty quantification for matrix compressed sensing and quantum tomography problems., preprint arXiv:1504.03234, (2015)
[19] Chandrasekaran,, V.,; Recht,, B.,; Parrilo,, P.; Willsky,, A., The convex geometry of linear inverse problems., Found. Comput. Math., 12, 849, (2012) · Zbl 1280.52008
[20] Chen,, Y.,; Chi,, Y.; Goldsmith,, A., Exact and stable covariance estimation from quadratic sampling via convex programming., IEEE Trans. Inform. Theory, 61, 4059, (2015) · Zbl 1359.62181
[21] Chen,, Z.; Dongarra,, J. J., Condition numbers of Gaussian random matrices., SIAM J. Matrix Anal. A, 27, 620, (2005) · Zbl 1107.15016
[22] Demanet,, L.; Hand,, P., Stable optimizationless recovery from phaseless linear measurements., J. Fourier Anal. Appl., 20, 221, (2014) · Zbl 1330.90069
[23] Dirksen,, S.,; Lecué,, G.; Rauhut,, H., On the gap between RIP-properties and sparse recovery conditions., IEEE Trans. Inform. Theory, (2016)
[24] Fazel,, M., Matrix rank minimization., Ph.D. Thesis, (2002)
[25] Ferrie,, C.; Kueng,, R., Have you been using the wrong estimator? These guys bound average fidelity using this one weird trick von Neumann didn’t want you to know., preprint arXiv:1503.00677, (2015)
[26] Flammia,, S. T.,; Gross,, D.,; Liu,, Y.-K.; Eisert,, J., Quantum tomography via compressed sensing: error bounds, sample complexity and efficient estimators., New J. Phys., 14, 095022, (2012) · Zbl 1448.81075
[27] Fornasier,, M.,; Rauhut,, H.; Ward,, R., Low-rank matrix recovery via iteratively reweighted least squares minimization., SIAM J. Optim., 21, 1640, (2011) · Zbl 1236.65044
[28] Foucart,, S.; Rauhut,, H.; Benedetto, J. S., A mathematical introduction to compressive sensing., Applied and Numerical Harmonic Analysis, (2013) · Zbl 1315.94002
[29] Gordon,, Y.; Lindenstrauss, J.; Milman, V. D., On Milman’s inequality and random subspaces which escape through a mesh in {\({\mathbb R}^n\)}., Geometric Aspects of Functional Analysis (1986/87), Volume 1317, 106, (1988)
[30] Gross,, D.,; Krahmer,, F.; Kueng,, R., A partial derandomization of Phaselift using spherical designs., J. Fourier Anal. Appl., 21, 266, (2014) · Zbl 1332.90197
[31] Gross,, D.,; Krahmer,, F.; Kueng,, R., Improved recovery guarantees for phase retrieval from coded diffraction patterns., Appl. Comput. Harmon. Anal. · Zbl 1393.94250
[32] Gross,, D.,; Liu,, Y.-K.,; Flammia,, S. T.,; Becker,, S.; Eisert,, J., State tomography via compressed sensing., Phys. Rev. Lett., 105, 150401, (2010)
[33] Heinosaari,, T.,; Mazzarella,, L.; Wolf,, M. M., Quantum tomography under prior information., Commun. Math. Phys., 318, 374, (2013) · Zbl 1263.81102
[34] Helstrom,, C. W., Quantum detection and estimation theory., J. Statist. Phys., 1, 252, (1969)
[35] Horn,, R.; Johnson,, C., Topics in Matrix Analysis, (1991) · Zbl 0729.15001
[36] Kabanava,, M.,; Rauhut,, H.; Terstiege,, U., Analysis of low rank matrix recovery via Mendelson’s small ball method., Proceedings of the 11th International Conference on Sampling Theory and Applications (SampTA 2015), 391, (2015)
[37] Kabanava,, M.,; Rauhut,, H.; Terstiege,, U., On the minimal number of measurements in low-rank matrix recovery., Proceedings of the 11th International Conference on Sampling Theory and Applications (SampTA 2015), 386, (2015)
[38] Kalev,, A.,; Riofrio,, C.,; Kosut,, R.; Deutsch,, I., Informationally complete measurements from compressed sensing methodology., Bull. Am. Phys. Soc., 60, (2015)
[39] Kech,, M.,; Vrana,, P.; Wolf,, M., The role of topology in quantum tomography., J. Phys. A Math. Theor., 48, 303, (2015) · Zbl 1325.81045
[40] Kech,, M.; Wolf,, M., From quantum tomography to phase retrieval and back., Proceedings of the 11th International Conference on Sampling Theory and Applications (SampTA 2015), 177, (2015)
[41] Kech,, M.; Wolf,, M. M., Quantum tomography of semi-algebraic sets with constrained measurements., preprint ArXiv:1507.00903, (2015) · Zbl 1325.81045
[42] Koltchinskii,, V.; Mendelson,, S., Bounding the smallest singular value of a random matrix without concentration., Int. Math. Res. Notices, 2015, 13008, (2015) · Zbl 1331.15027
[43] Kueng,, R.,; Daniel,, S.; Gross,, D., Direct characterization of linear-optical networks via PhaseLift, in preparation,, (2015)
[44] Kueng,, R.,; Gross,, D.; Krahmer,, F., Spherical designs as a tool for derandomization: the case of PhaseLift., Proceedings of the 11th International Conference on Sampling Theory and Applications (SampTA 2015), 196, (2015) · Zbl 1332.90197
[45] Kueng,, R.,; Rauhut,, H.; Terstiege,, U., Low rank matrix recovery from rank one measurements., Appl. Comput. Harmonic Anal. · Zbl 1393.94310
[46] Latała,, R., Some estimates of norms of random matrices., Proc. Am. Math. Soc., 133, 1282, (2005) · Zbl 1067.15022
[47] Ledoux,, M.; Talagrand,, M., Probability in Banach Spaces., (1991) · Zbl 0662.60008
[48] Lee,, K.; Bresler,, Y., ADMiRA: Atomic decomposition for minimum rank approximation., IEEE Trans. Image Process., 56, 4416, (2010) · Zbl 1366.94112
[49] Liu,, Y.-K., Universal low-rank matrix recovery from Pauli measurements., Adv. Neural Inf. Process. Syst., 24, 1646, (2011)
[50] Matthews,, W.,; Wehner,, S.; Winter,, A., Distinguishability of quantum states under restricted families of measurements with an application to quantum data hiding., Commun. Math. Phys., 291, 843, (2009) · Zbl 1179.81020
[51] McCoy,, M. B.; Tropp,, J. A., Sharp recovery bounds for convex demixing, with applications., Found. Comput. Math., 14, 567, (2014) · Zbl 1312.94016
[52] Mendelson,, S., Learning without concentration., J. ACM, 62, 25, (2015) · Zbl 1333.68232
[53] Mohan,, K.; Fazel,, M., Iterative reweighted least squares for matrix rank minimization., Proceedings of the Allerton Conference, 661, (2010)
[54] Mohan,, K.; Fazel,, M., New restricted isometry results for noisy low-rank recovery., Proceedings of the International Symposium on Information Theory, (2010)
[55] Nielsen,, M. A.; Chuang,, I. L., Quantum Computation and Quantum Information, (2010) · Zbl 1288.81001
[56] Oymak,, S.,; Mohan,, K.,; Fazel,, M.; Hassibi,, B., A simplified approach to recovery conditions for low rank matrices., 2011 IEEE International Symposium on Information Theory Proceedings (ISIT), 2322, (2011)
[57] Parikh,, N.; Boyd,, S., Proximal algorithms., Found. Trends Optim., 1, 231, (2014)
[58] Raskutti,, G.,; Wainwright,, M. J.; Yu,, B., Restricted eigenvalue properties for correlated Gaussian designs., J. Machine Learn. Res., 11, 2259, (2010) · Zbl 1242.62071
[59] Recht,, B.,; Fazel,, M.; Parrilo,, P. A., Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization., SIAM Rev., 52, 501, (2010) · Zbl 1198.90321
[60] Recht,, B.,; Xu,, W.; Hassibi,, B., Necessary and sufficient conditions for success of the nuclear norm heuristic for rank minimization., Proceedings of the 47th IEEE Conference on Decision and Control, 3070, (2008)
[61] Recht,, B.,; Xu,, W.; Hassibi,, B., Null space conditions and thresholds for rank minimization., Math. Program., 127, 211, (2011) · Zbl 1211.90172
[62] Rudelson,, M.; Vershynin,, R., On sparse reconstruction from Fourier and Gaussian measurements., Commun. Pure Appl. Math., 61, 1045, (2008) · Zbl 1149.94010
[63] Schindler,, P.,; Nigg,, D.,; Monz,, T.,; Barreiro,, J. T.,; Martinez,, E.,; Wang,, S. X.,; Quint,, S.,; Brandl,, M. F.,; Nebendahl,, V.,; Roos,, C. F.,; Chwalla,, M.,; Hennrich,, M.,; Blatt,, R., A quantum information processor with trapped ions., New J. Phys., 15, 123012, (2013)
[64] Schölkopf,, B.; Smola,, A. J., Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond, (2002)
[65] Scott,, A., Tight informationally complete quantum measurements., J. Phys. A-Math. Gen., 39, 13530, (2006) · Zbl 1107.81017
[66] Slawski,, M.,; Li,, P.; Hein,, M., Regularization-free estimation in trace regression with symmetric positive semidefinite matrices., Proceedings of NIPS 28, 2772, (2015)
[67] Tanner,, J.; Wei,, K., Normalized iterative hard thresholding for matrix completion., SIAM J. Sci. Comput., 59, 7508, (2013) · Zbl 1282.65043
[68] Tropp,, J. A., User-friendly tail bounds for sums of random matrices., Found. Comput. Math., 12, 434, (2012) · Zbl 1259.60008
[69] Tropp,, J. A.; Pfander, G., Convex recovery of a structured signal from independent random linear measurements., Sampling Theory, a Renaissance, 101, (2015) · Zbl 1358.94034
[70] Vershynin,, R.; Eldar,, Y.; Kutyniok,, G., Introduction to the non-asymptotic analysis of random matrices., Compressed Sensing: Theory and Applications, 268, (2012)
[71] Xu,, Z., The minimal measurement number for low-rank matrices recovery., preprint ArXiv:1505.07204, (2015)
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.