Low rank matrix recovery from rank one measurements. (English) Zbl 1393.94310

Summary: We study the recovery of Hermitian low rank matrices \(X \in \mathbb{C}^{n \times n}\) from undersampled measurements via nuclear norm minimization. We consider the particular scenario where the measurements are Frobenius inner products with random rank-one matrices of the form \(a_j a_j^*\) for some measurement vectors \(a_1,\ldots, a_m\), i.e., the measurements are given by \(b_j = \text{tr}(X a_j a_j^*)\). The case where the matrix \(X = x x^*\) to be recovered is of rank one reduces to the problem of phaseless estimation (from measurements \(b_j = | \langle x, a_j \rangle |^2\)) via the PhaseLift approach, which has been introduced recently. We derive bounds for the number \(m\) of measurements that guarantee successful uniform recovery of Hermitian rank \(r\) matrices, either for the vectors \(a_j\), \(j = 1, \ldots, m\), being chosen independently at random according to a standard Gaussian distribution, or \(a_j\) being sampled independently from an (approximate) complex projective \(t\)-design with \(t = 4\). In the Gaussian case, we require \(m \geq Crn\) measurements, while in the case of 4-designs we need \(m \geq Crn \log(n)\). Our results are uniform in the sense that one random choice of the measurement vectors \(a_j\) guarantees recovery of all rank \(r\)-matrices simultaneously with high probability. Moreover, we prove robustness of recovery under perturbation of the measurements by noise. The result for approximate 4-designs generalizes and improves a recent bound on phase retrieval due to D. Gross et al. [Appl. Comput. Harmon. Anal. 42, No. 1, 37–64 (2017; Zbl 1393.94250)]. In addition, it has applications in quantum state tomography. Our proofs employ the so-called bowling scheme which is based on recent ideas by Mendelson and Koltchinskii.


94A12 Signal theory (characterization, reconstruction, filtering, etc.)
94A20 Sampling theory in information and communication theory
60B20 Random matrices (probabilistic aspects)
90C25 Convex programming
81P50 Quantum state estimation, approximate cloning


Zbl 1393.94250
Full Text: DOI arXiv


[2] Alexeev, B.; Bandeira, A. S.; Fickus, M.; Mixon, D. G., Phase retrieval with polarization, SIAM J. Imaging Sci., 7, 35-66 (2014) · Zbl 1304.49071
[3] Ambainis, A.; Emerson, J., Quantum t-designs: t-wise independence in the quantum world, (22nd Annual IEEE Conference on Computational Complexity, Proceedings (2007)), 129-140
[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, 3, 224-294 (2014) · Zbl 1339.90251
[5] Bachoc, C.; Ehler, M., Signal reconstruction from the magnitude of subspace components (2012)
[6] Bajnok, B., Construction of spherical \(t\)-designs, Geom. Dedicata, 43, 167-179 (1992) · Zbl 0765.05032
[7] Balan, R.; Bodmann, B. G.; Casazza, P. G.; Edidin, D., Painless reconstruction from magnitudes of frame coefficients, J. Fourier Anal. Appl., 15, 488-501 (2009) · Zbl 1181.42032
[8] Balan, R.; Casazza, P.; Edidin, D., On signal reconstruction without phase, Appl. Comput. Harmon. Anal., 20, 3, 345-356 (2006) · Zbl 1090.94006
[9] Berger, B., The fourth moment method, SIAM J. Comput., 26, 4, 1188-1207 (1997) · Zbl 0885.68080
[10] Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge Univ. Press · Zbl 1058.90049
[11] Brandao, F. G.; Harrow, A. W.; Horodecki, M., Local random quantum circuits are approximate polynomial-designs (2012), Preprint
[12] Bunk, O.; Diaz, A.; Pfeiffer, F.; David, C.; Schmitt, B.; Satapathy, D. K.; van der Veen, J. F., Diffractive imaging for periodic samples: retrieving one-dimensional concentration profiles across microfluidic channels, Acta Crystallogr. Sect. A, 63, 4, 306-314 (2007)
[13] Candès, E. J.; Eldar, Y.; Strohmer, T.; Voroninski, V., Phase retrieval via matrix completion, SIAM J. Imaging Sci., 6, 1, 199-225 (2013) · Zbl 1280.49052
[14] Candès, E.; Li, X., Solving quadratic equations via PhaseLift when there are about as many equations as unknowns, Found. Comput. Math., 1-10 (2013)
[16] Candès, E. J.; Li, X.; Soltanolkotabi, M., Phase retrieval from coded diffraction patterns, Appl. Comput. Harmon. Anal., 39, 2, 277-299 (2015) · Zbl 1329.78056
[17] 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 (2011) · Zbl 1366.90160
[18] Candès, E. J.; Recht, B., Exact matrix completion via convex optimization, Found. Comput. Math., 9, 6, 717-772 (2009) · Zbl 1219.90124
[19] Candès, E. J.; Strohmer, T.; Voroninski, V., PhaseLift: exact and stable signal recovery from magnitude measurements via convex programming, Comm. Pure Appl. Math., 66, 1241-1274 (2013) · Zbl 1335.94013
[20] Candès, E. J.; Tao, T., Near optimal signal recovery from random projections: universal encoding strategies?, IEEE Trans. Inform. Theory, 52, 12, 5406-5425 (2006) · Zbl 1309.94033
[21] Candès, E. J.; Tao, T., The power of matrix completion: near-optimal convex relaxation, IEEE Trans. Inform. Theory, 56, 5, 2053-2080 (2010) · Zbl 1366.15021
[22] Chandrasekaran, V.; Recht, B.; Parrilo, P.; Willsky, A., The convex geometry of linear inverse problems, Found. Comput. Math., 12, 6, 805-849 (2012) · Zbl 1280.52008
[23] Chen, Y., Incoherence-optimal matrix completion (2013), Preprint · Zbl 1359.15022
[24] Chen, Y.; Bhojanapalli, S.; Sanghavi, S.; Ward, R., Completing any low-rank matrix, provably (2013)
[25] Chen, Y.; Chi, Y.; Goldsmith, A., Exact and stable covariance estimation from quadratic sampling via convex programming, IEEE Trans. Inform. Theory, 61, 4034-4059 (2015) · Zbl 1359.62181
[26] Combettes, P.; Pesquet, J.-C., Proximal splitting methods in signal processing, (Bauschke, H.; Burachik, R.; Combettes, P.; Elser, V.; Luke, D.; Wolkowicz, H., Fixed-Point Algorithms for Inverse Problems in Science and Engineering (2011), Springer), 185-212 · Zbl 1242.90160
[27] Dankert, C.; Cleve, R.; Emerson, J.; Livine, E., Exact and approximate unitary 2-designs: constructions and applications (2006), Preprint
[28] De La Harpe, P.; Pache, C., Cubature formulas, geometrical designs, reproducing kernels, and Markov operators, (Infinite Groups: Geometric, Combinatorial and Dynamical Aspects (2005), Springer), 219-267 · Zbl 1124.05019
[29] Delsarte, P.; Goethals, J.; Seidel, J., Spherical codes and designs, Geom. Dedicata, 6, 363-388 (1977) · Zbl 0376.05015
[30] Donoho, D. L., Compressed sensing, IEEE Trans. Inform. Theory, 52, 4, 1289-1306 (2006) · Zbl 1288.94016
[31] Ehler, M.; Fornasier, M.; Sigl, J., Quasi-linear compressed sensing, Multiscale Model. Simul., 12, 2, 725-754 (2014) · Zbl 1380.94050
[32] Fazel, M., Matrix rank minimization with applications (2002), PhD thesis
[33] Fienup, C.; Dainty, J., Phase retrieval and image reconstruction for astronomy, (Stark, H., Image Recovery: Theory and Application (1987), Academic Press: Academic Press San Diego), 231-275
[34] Fienup, J., Phase retrieval algorithms: a comparison, Appl. Optim., 21, 15, 2758-2769 (1982)
[35] 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
[36] Fornasier, M.; Rauhut, H.; Ward, R., Low-rank matrix recovery via iteratively reweighted least squares minimization, SIAM J. Optim., 21, 4, 1614-1640 (2011) · Zbl 1236.65044
[37] Foucart, S.; Rauhut, H., A Mathematical Introduction to Compressive Sensing, Applied and Numerical Harmonic Analysis (2013), Birkhäuser · Zbl 1315.94002
[38] Gerchberg, R.; Saxton, W., Phase retrieval by iterated projection, Optik, 35 (1972)
[39] Gross, D., Recovering low-rank matrices from few coefficients in any basis, IEEE Trans. Inform. Theory, 57, 1548-1566 (2011) · Zbl 1366.94103
[40] Gross, D.; Audenaert, K.; Eisert, J., Evenly distributed unitaries: on the structure of unitary designs, J. Math. Phys., 48, 052104 (2007), 22 · Zbl 1144.81351
[41] Gross, D.; Krahmer, F.; Kueng, R., Improved recovery guarantees for phase retrieval from coded diffraction patterns, Appl. Comput. Harmon. Anal., 42, 1, 37-64 (2017), Preprint · Zbl 1393.94250
[42] Gross, D.; Krahmer, F.; Kueng, R., A partial derandomization of PhaseLift using spherical designs, J. Fourier Anal. Appl., 21, 2, 229-266 (2015) · Zbl 1332.90197
[43] Gross, D.; Liu, Y.-K.; Flammia, S. T.; Becker, S.; Eisert, J., Quantum state tomography via compressed sensing, Phys. Rev. Lett., 105, 150401 (Oct 2010)
[44] Harrison, R., Phase problem in crystallography, J. Opt. Soc. Amer. A, 10, 5, 1046-1055 (1993)
[45] Hayashi, A.; Hashimoto, T.; Horibe, M., Reexamination of optimal quantum state estimation of pure states, Phys. Rev. A, 72 (Sep 2005)
[46] Hayden, P.; Leung, D.; Shor, P. W.; Winter, A., Randomizing quantum states: constructions and applications, Comm. Math. Phys., 250, 2, 371-391 (2004) · Zbl 1065.81025
[47] Keshavan, R. H.; Montanari, A.; Oh, S., Matrix completion from a few entries, IEEE Trans. Inform. Theory, 56, 6, 2980-2998 (2010) · Zbl 1366.62111
[48] Koltchinskii, V.; Mendelson, S., Bounding the smallest singular value of a random matrix without concentration, Int. Math. Res. Not. (2015), in press · Zbl 1331.15027
[49] Korevaar, J.; Meyers, J., Chebyshev-type quadrature on multidimensional domains, J. Approx. Theory, 79, 144-164 (1994) · Zbl 0814.41023
[50] Kueng, R.; Gross, D.; Krahmer, F., Spherical designs as a tool for derandomization: the case of PhaseLift, (11th International Conference on Sampling Theory and Applications. 11th International Conference on Sampling Theory and Applications, SampTA (2015)) · Zbl 1332.90197
[51] Kuperberg, G., Numerical cubature using error-correcting codes, SIAM J. Numer. Anal., 44, 3, 897-907 (2006) · Zbl 1126.65025
[52] Kyrillidis, A.; Cevher, V., Matrix recipes for hard thresholding methods, J. Math. Imaging Vision, 48, 235-265 (2014) · Zbl 1311.90141
[53] Lancien, C.; Winter, A., Distinguishing multi-partite states by local measurements, Comm. Math. Phys., 323, 2, 555-573 (2013) · Zbl 1280.81024
[54] Landsberg, J. M., Tensors: Geometry and Applications (2012), American Mathematical Society (AMS): American Mathematical Society (AMS) Providence, RI · Zbl 1238.15013
[55] Lecué, G.; Mendelson, S., Sparse recovery under weak moment assumptions, J. Eur. Math. Soc. (2015), in press · Zbl 1414.62135
[56] Lee, K.; Bresler, Y., ADMiRA: atomic decomposition for minimum rank approximation, IEEE Trans. Image Process., 56, 9, 4402-4416 (2010) · Zbl 1366.94112
[57] Liu, Y.-K., Universal low-rank matrix recovery from Pauli measurements, Adv. Neural Inf. Process. Syst., 1638-1646 (2011)
[58] Low, R. A., Large deviation bounds for \(k\)-designs, Proc. R. Soc. Lond., Ser. A, Math. Phys. Eng. Sci., 465, 3289-3308 (2009) · Zbl 1186.82034
[59] Low, R. A., Pseudo-randomness and learning in quantum computation (2010), PhD thesis, University of Bristol
[60] Matthews, W.; Wehner, S.; Winter, A., Distinguishability of quantum states under restricted families of measurements with an application to quantum data hiding, Comm. Math. Phys., 291, 3, 813-843 (2009) · Zbl 1179.81020
[61] Mendelson, S., Learning without concentration, J. ACM (2015), in press · Zbl 1333.68232
[62] Millane, R., Phase retrieval in crystallography and optics, J. Opt. Soc. Amer. A, 7, 3, 394-411 (1990)
[63] Nakata, Y.; Koashi, M.; Murao, M., Generating a state t-design by diagonal quantum circuits, New J. Phys., 16, 5, 053043 (2014) · Zbl 1451.81150
[64] Nebe, G.; Rains, E.; Sloane, N., The invariants of the Clifford groups, Des. Codes Cryptogr., 24, 99-121 (2001) · Zbl 1002.11057
[65] Netrapalli, P.; Jain, P.; Sanghavi, S., Phase retrieval using alternating minimization, (Advances in Neural Information Processing Systems (2013)), 2796-2804
[66] Nielsen, M. A.; Chuang, I. L., Quantum Computation and Quantum Information (2010), Cambridge Univ. Press · Zbl 1288.81001
[67] Parikh, N.; Boyd, S., Proximal algorithms, Found. Trends Optim., 1, 3, 123-231 (2013)
[68] Recht, B.; Fazel, M.; Parrilo, P. A., Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 471-501 (2010) · Zbl 1198.90321
[69] Schwemmer, C.; Tóth, G.; Niggebaum, A.; Moroder, T.; Gross, D.; Gühne, O.; Weinfurter, H., Experimental comparison of efficient tomography schemes for a six-qubit state, Phys. Rev. Lett., 113, 4, 040503 (2014)
[70] Scott, A., Tight informationally complete quantum measurements, J. Phys. A: Math. Gen., 39, 13507-13530 (2006) · Zbl 1107.81017
[71] Seymour, P.; Zaslavsky, T., Averaging sets: a generalization of mean values and spherical designs, Adv. Math., 52, 213-240 (1984) · Zbl 0596.05012
[72] Shechtman, Y.; Eldar, Y. C.; Cohen, O.; Chapman, H. N.; Miao, J.; Segev, M., Phase retrieval with application to optical imaging (Feb 2014), Preprint
[73] Sidelnikov, V., Spherical 7-designs in \(2^n\)-dimensional Euclidean space, J. Algebraic Combin., 10, 279-288 (1999) · Zbl 0938.05021
[74] Stanley, R., Enumerative Combinatorics, vol. I (1997), Cambridge Univ. Press · Zbl 0889.05001
[75] Tanner, J.; Wei, K., Normalized iterative hard thresholding for matrix completion, SIAM J. Sci. Comput., 59, 11, 7491-7508 (2013)
[76] Toh, K.; Yun, S., An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems, Pac. J. Optim., 6, 615-640 (2010) · Zbl 1205.90218
[77] Tropp, J. A., User-friendly tail bounds for sums of random matrices, Found. Comput. Math., 12, 4, 389-434 (2012) · Zbl 1259.60008
[79] Tropp, J. A., Convex recovery of a structured signal from independent random linear measurements, (Sampling Theory, a Renaissance (2015)) (2014), in press
[80] Vershynin, R., Introduction to the non-asymptotic analysis of random matrices, (Eldar, Y.; Kutyniok, G., Compressed Sensing: Theory and Applications (2012), Cambridge Univ. Press), 210-268
[81] Walther, A., The question of phase retrieval in optics, J. Modern Opt., 10, 1, 41-49 (1963)
[83] Watson, G. A., Characterization of the subdifferential of some matrix norms, Linear Algebra Appl., 170, 33-45 (1992) · Zbl 0751.15011
[84] Zauner, G., Quantendesigns: Grundzüge einer nichtkommutativen Designtheorie (1999), University of Vienna, PhD thesis
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.