@article {1427, title = {Universal low-rank matrix recovery from Pauli measurements}, journal = {Advances in Neural Information Processing Systems (NIPS)}, year = {2011}, month = {2011/03/14}, pages = {1638-1646}, 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 log^6 d) Pauli measurements satisfy the rank-r 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{\textquoteright}s inequality for Gaussian processes, together with bounds on covering numbers obtained via entropy duality. }, url = {http://arxiv.org/abs/1103.2816v2}, author = {Yi-Kai Liu} }