ITLApplied  Computational Mathematics Division
ACMD Seminar Series
Attractive Image NIST

Universal Low-Rank Matrix Recovery from Pauli Measurements

Yi-Kai Liu
Applied and Computational Mathematics Division, NIST

Tuesday, May 15, 2012 15:00-16:00,
Building 101, Lecture Room F
Tuesday, May 15, 2012 13:00-14:00,
Room 1-4058


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 to compressed sensing methods for quantum state tomography. It is a non-commutative analogue of a well-studied problem: recovering a sparse vector from a few of its Fourier coefficients.

We give a solution to this problem based on the restricted isometry property (RIP), which improves on previous results using dual certificates. In particular, we show that almost all sets of O(rd log^6 d) Pauli measurements satisfy the rank-r 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. Our proof uses Dudley's inequality for Gaussian processes, together with bounds on covering numbers obtained via entropy duality.

Speaker Bio: Yi-Kai Liu is a staff scientist at the National Institute of Standards and Technology (NIST), in Gaithersburg, Maryland. He works on quantum computation and cryptography. Previously he was a postdoc at UC Berkeley and Caltech. He received his PhD in computer science at UC San Diego in 2007.

Presentation Slides: PDF

Contact: B. Cloteaux

Note: Visitors from outside NIST must contact Cathy Graham; (301) 975-3668; at least 24 hours in advance.

Privacy Policy | Disclaimer | FOIA
NIST is an agency of the U.S. Commerce Department.
Last updated: 2012-05-14.