| Author(s): |
Yi-Kai Liu; |
| Title: |
Universal Low-rank Matrix Recovery from Pauli Measurements |
| Published: |
December 12, 2011 |
| 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 using nuclear norm minimization (e.g., the matrix Lasso), using a fixed ("universal") set of Pauli measurements, and with nearly-optimal bounds on the error. Our proof uses Dudley’s inequality for Gaussian processes, together with bounds on covering numbers obtained via entropy duality. |
| Conference: |
Neural Information Processing Systems (NIPS) |
| Proceedings: |
Advances in Neural Information Processing Systems (NIPS) |
| Volume: |
24 |
| Pages: |
pp. 1638 - 1646 |
| Location: |
La Jolla, CA |
| Dates: |
December 12-17, 2011 |
| Keywords: |
Quantum state tomography; matrix completion; compressed sensing |
| Research Areas: |
Quantum Computing, Quantum Devices, Statistics |
