Special PACM Student Colloquium!

-
Dustin Mixon, Afonso Bandeira, Princeton University
Fine Hall 214

Dustin Mixon - "Phaseless recovery with polarization": In many applications, an unknown vector is measured according to the magnitude of its inner product with some known vector. It is desirable to design an ensemble of vectors for which any unknown vector can be recovered from such measurements (up to a global phase factor). In 2006, Balan et al. demonstrated that this measurement process is injective for generic M-dimensional vector ensembles of size at least 4M-2. Recently, Candes et al. used semidefinite programming to stably reconstruct from measurements with random ensembles of size O(MlogM). In this talk, we use the polarization identity and expander graphs to efficiently recover from measurements with specific deterministic ensembles of size O(M). We then observe how the theory of synchronization can be leveraged to demonstrate stability in this method. Afonso Bandeira - "Cheeger Inequality for the Graph Connection Laplacian": The $O(d)$ Synchronization problem consists of estimating a set of unknown orthogonal transformations $O_i$ from noisy measurements of a subset of the pairwise ratios $O_iO_j^{-1}$. We formulate and prove a Cheeger-type inequality that relates a measure of how well it is possible to solve the $O(d)$ synchronization problem with the spectra of an operator, the graph Connection Laplacian. We also show how this inequality provides a worst case performance guarantee for a spectral method to solve this problem. This is joint work with Amit Singer (Princeton) and Daniel Spielman (Yale).