Universal low-rank matrix recovery from Pauli measurements

Details Universal low-rank matrix recovery from Pauli measurements Universal low-rank matrix recovery from Pauli measurements

2011-03-14

arxiv.org/abs/1103.2816v2

Advances in Neural Information Processing Systems (NIPS) 24, pp.1638-1646 (2011)

Physics

Quantum Physics

v2: corrected typos, added proof details, 9+8 pages, to appear in NIPS 2011

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Universal low-rank matrix recovery from Pauli measurements does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Universal low-rank matrix recovery from Pauli measurements, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Universal low-rank matrix recovery from Pauli measurements will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-138336