@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}
}