NIST logo

Publication Citation: Universal Low-rank Matrix Recovery from Pauli Measurements

NIST Authors in Bold

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