Universal Low-rank Matrix Recovery from Pauli Measurements
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.
Advances in Neural Information Processing Systems (NIPS)
December 12-17, 2011
La Jolla, CA
Neural Information Processing Systems (NIPS)
Quantum state tomography, matrix completion, compressed sensing