



01292nas a2200121   4500008004100000245006300041210006200104260001500166300001400181520092200195100001601117856003701133       2011                        eng d00aUniversal low-rank matrix recovery from Pauli measurements0 aUniversal lowrank matrix recovery from Pauli measurements  c2011/03/14  a1638-16463 a  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's
inequality for Gaussian processes, together with bounds on covering numbers
obtained via entropy duality.
1 aLiu, Yi-Kai  uhttp://arxiv.org/abs/1103.2816v2