Take a sneak peek at the new NIST.gov and let us know what you think!
(Please note: some content may not be complete on the beta site.).
NIST Authors in Bold
|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)|
|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|