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.