A reminder of Yi-Kai Liu's talk at 4pm in the Time room at PI.
Title:
Universal Low-rank Matrix Recovery from Pauli Measurements
Speaker: Yi-Kai Liu (National Institute of Standards and Technology)
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 to compressed sensing methods for quantum state
tomography. 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.
Date: April 04, 2012 - 4:00 pm
Series: Perimeter Institute Quantum Discussions
Location: Time Rm