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 log^6 d) Pauli measurements satisfy the rank-r restricted isometry property (RIP). This implies that M can be recovered using nuclear norm minimization (e.g., the matrix Lasso), using a fixed ("universal") set of Pauli measurements, and with nearly-optimal bounds on the error. Our proof uses Dudleys inequality for Gaussian processes, together with bounds on covering numbers obtained via entropy duality.
Proceedings Title: Advances in Neural Information Processing Systems (NIPS)
Conference Dates: December 12-17, 2011
Conference Location: La Jolla, CA
Conference Title: Neural Information Processing Systems (NIPS)
Pub Type: Conferences
Quantum state tomography, matrix completion, compressed sensing