nips nips2011 nips2011-297 nips2011-297-reference knowledge-graph by maker-knowledge-mining

297 nips-2011-Universal low-rank matrix recovery from Pauli measurements

Source: pdf

Author: Yi-kai Liu

Abstract: We study the problem of reconstructing an unknown matrix M of rank r and dimension d using O(rd poly log d) Pauli measurements. This has applications in quantum state tomography, and is a non-commutative analogue of a well-known problem in compressed sensing: recovering a sparse vector from a few of its Fourier coefficients. We show that almost all sets of O(rd log6 d) Pauli measurements satisfy the rankr restricted isometry property (RIP). This implies that M can be recovered from a fixed (“universal”) set of Pauli measurements, using nuclear-norm minimization (e.g., the matrix Lasso), with nearly-optimal bounds on the error. A similar result holds for any class of measurements that use an orthonormal operator basis whose elements have small operator norm. Our proof uses Dudley’s inequality for Gaussian processes, together with bounds on covering numbers obtained via entropy duality. 1

reference text

[1] M. Fazel. Matrix Rank Minimization with Applications. PhD thesis, Stanford, 2002.

[2] N. Srebro. Learning with Matrix Factorizations. PhD thesis, MIT, 2004.

[3] B. Recht, M. Fazel, and P. A. Parrilo. Guaranteed minimum rank solutions to linear matrix equations via nuclear norm minimization. SIAM Review, 52(3):471–501, 2010.

[4] M. Fazel, E. Candes, B. Recht, and P. Parrilo. Compressed sensing and robust recovery of low rank matrices. In 42nd Asilomar Conference on Signals, Systems and Computers, pages 1043–1047, 2008.

[5] E. J. Candes and Y. Plan. Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements. 2009.

[6] E. J. Candes and B. Recht. Exact matrix completion via convex optimization. Found. of Comput. Math., 9:717–772.

[7] E. J. Candes and T. Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Trans. Inform. Theory, 56(5):2053–2080, 2009.

[8] D. Gross. Recovering low-rank matrices from few coefficients in any basis. IEEE Trans. Inform. Theory, to appear. arXiv:0910.1879, 2010.

[9] B. Recht. A simpler approach to matrix completion. J. Machine Learning Research (to appear), 2010.

[10] S. Negahban and M. J. Wainwright. Restricted strong convexity and weighted matrix completion: Optimal bounds with noise. arXiv:1009.2118, 2010.

[11] E. J. Candes and T. Tao. Near-optimal signal recovery from random projections: universal encoding strategies. IEEE Trans. Inform. Theory, 52:5406–5425, 2004.

[12] M. Rudelson and R. Vershynin. On sparse reconstruction from Fourier and Gaussian measurements. Commun. Pure and Applied Math., 61:1025–1045, 2008.

[13] D. Gross, Y.-K. Liu, S. T. Flammia, S. Becker, and J. Eisert. Quantum state tomography via compressed sensing. Phys. Rev. Lett., 105(15):150401, Oct 2010. arXiv:0909.3304.

[14] E. J. Candes and Y. Plan. Matrix completion with noise. Proc. IEEE, 98(6):925 – 936, 2010.

[15] B. Brown, S. Flammia, D. Gross, and Y.-K. Liu. in preparation, 2011.

[16] O. Gu´ don, S. Mendelson, A. Pajor, and N. Tomczak-Jaegermann. Majorizing measures and e proportional subsets of bounded orthonormal systems. Rev. Mat. Iberoamericana, 24(3):1075– 1095, 2008.

[17] G. Aubrun. On almost randomizing channels with a short Kraus decomposition. Commun. Math. Phys., 288:1103–1116, 2009.

[18] M. A. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2001.

[19] A. Rohde and A. Tsybakov. Estimation of high-dimensional low-rank matrices. arXiv:0912.5338, 2009.

[20] V. Koltchinskii, K. Lounici, and A. B. Tsybakov. Nuclear norm penalization and optimal rates for noisy low rank matrix completion. arXiv:1011.6256, 2010.

[21] Y.-K. Liu. Universal low-rank matrix recovery from Pauli measurements. arXiv:1103.2816, 2011.

[22] M. Ledoux and M. Talagrand. Probability in Banach spaces. Springer, 1991.

[23] G. Pisier. The volume of convex bodies and Banach space geometry. Cambridge, 1999.

[24] F. Krahmer and R. Ward. New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property. SIAM J. Math. Anal., 43(3):1269–1281, 2011.

[25] A. Shabani, R. L. Kosut, M. Mohseni, H. Rabitz, M. A. Broome, M. P. Almeida, A. Fedrizzi, and A. G. White. Efficient measurement of quantum dynamics via compressive sensing. Phys. Rev. Lett., 106(10):100401, 2011.

[26] P. Wojtaszczyk. Stability and instance optimality for gaussian measurements in compressed sensing. Found. Comput. Math., 10(1):1–13, 2009. 9