Universal Low-rank Matrix Recovery from Pauli Measurements



Playing this video requires the latest flash player from Adobe.

Download link (right click and 'save-as') for playing in VLC or other f4v compatible player.


Recording Details

Speaker(s): 
Scientific Areas: 
PIRSA Number: 
12040101

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.