Universal low-rank matrix recovery from Pauli measurements
arXiv:1103.2816
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's inequality for Gaussian processes, together with bounds on covering numbers obtained via entropy duality.
arXiv commentv2: corrected typos, added proof details, 9+8 pages, to appear in NIPS 2011
References in corpus (6)
- Quantum state tomography via compressed sensing
- A Simpler Approach to Matrix Completion
- Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
- Estimation of high-dimensional low-rank matrices
- Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements
- On almost randomizing channels with a short Kraus decomposition
Cited by in corpus (16)
- A Partial Derandomization of PhaseLift using Spherical Designs
- RIPless compressed sensing from anisotropic measurements
- Universal Matrix Completion
- Recovering quantum gates from few average gate fidelities
- Dropping Convexity for Faster Semi-definite Optimization
- Guaranteed recovery of quantum processes from few measurements
- Optimal large-scale quantum state tomography with Pauli measurements
- Asymptotic equivalence of quantum state tomography and noisy matrix completion
- Exact and Stable Covariance Estimation from Quadratic Sampling via Convex Programming
- Statistical Inferences of Linear Forms for Noisy Matrix Completion
- Quantum Polarimetry
- A Counterexample for the Validity of Using Nuclear Norm as a Convex Surrogate of Rank
- Estimation of low rank density matrices by Pauli measurements
- A Rank-Corrected Procedure for Matrix Completion with Fixed Basis Coefficients
- Using non-convex optimization in quantum process tomography: Factored gradient descent is tough to beat
- A Robust Compressive Quantum State Tomography Algorithm Using ADMM