Universal low-rank matrix recovery from Pauli measurements

摘要: We study the problem of reconstructing an unknown matrix M rank r and dimension d using O(rd poly log d) Pauli measurements. This has applications in quantum state tomography, is a non-commutative analogue well-known compressed sensing: recovering sparse vector from few its Fourier coefficients. We show that almost all sets log^6 measurements satisfy rank-r restricted isometry property (RIP). implies can be recovered fixed ("universal") set measurements, nuclear-norm minimization (e.g., Lasso), with nearly-optimal bounds on error. A similar result holds for any class use orthonormal operator basis whose elements have small norm. Our proof uses Dudley's inequality Gaussian processes, together covering numbers obtained via entropy duality.