Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk

Vlad Voroninski recently posted an arXiv preprint with Paul Hand that provides compressed sensing guarantees using a neural net-based generative signal model. This offers some theoretical justification for the shocking empirical results presented in the “Compressed sensing using generative models” paper, which demonstrates compressed sensing with 10 times fewer measurements than conventional compressed sensing. I was especially excited to see this paper, having recently read Michael Elad’s editorial on deep learning. To learn more, I interviewed Vlad (see below); I’ve lightly edited his responses for formatting and hyperlinks:

DGM: What is the origin story of this project? Were you and Paul inspired by the “Compressed sensing using generative models” paper?

VV: I have been working extensively with applied deep learning for the last year or so, and have been inspired by recent applications of deep generative image priors to classical inverse problems, such as the super resolution work by Fei Fei Li et al. Moreover, recent work on regularizing with deep generative priors for synthesizing the preferred inputs to neural activations, by Yosinski et al., made me optimistic that GAN-based generative priors are capturing sophisticated natural image structure (the synthetic images obtained in this paper look incredibly realistic).

Continue reading Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk

A polynomial-time relaxation of the Gromov-Hausdorff distance

Soledad Villar recently posted her latest paper on the arXiv (joint work with Afonso Bandeira, Andrew Blumberg and Rachel Ward). This paper reduces an instance of cutting-edge data science (specifically, shape matching and point-cloud comparison) to a semidefinite program, and then investigates fast solvers using non-convex local methods. (Check out her blog for an interactive illustration of the results.) Soledad is on the job market this year, and I read about this paper in her research statement. I wanted to learn more, so I decided to interview her. I’ve lightly edited her responses for formatting and hyperlinks:

Continue reading A polynomial-time relaxation of the Gromov-Hausdorff distance

On the low-rank approach for semidefinite programs arising in synchronization and community detection

From MaxCut to PhaseLift, semidefinite programming has proven to be rather powerful, especially for convex relaxation. SDP solvers take polynomial time, but the exponent is large, and anyone who’s run an SDP on CVX has experienced some frustration with the runtime. In practice, the SDP-optimal matrix tends to have extremely low rank, and so one may apply a rank constraint to facilitate the search for the SDP’s solution. This heuristic was first introduced by Burer and Monteiro, and it works well in practice, but the rank-constrained program is nonconvex and the theory is scant. Recently, the theory gap started to close with this paper:

On the low-rank approach for semidefinite programs arising in synchronization and community detection

Afonso S. Bandeira, Nicolas Boumal, Vladislav Voroninski

As the title suggests, this paper provides strong performance guarantees for the Burer-Monteiro heuristic in the particular cases of \mathbb{Z}_2 synchronization and community detection. I was very excited to see this paper, and so I interviewed one of the authors (Nicolas Boumal). I’ve lightly edited his responses for formatting and hyperlinks:

Continue reading On the low-rank approach for semidefinite programs arising in synchronization and community detection

Phase retrieval from coded diffraction patterns

In a previous post, I described a paper I wrote with Afonso and Yutong about how to design O(\log n) masked illuminations that enable efficient phase retrieval of n-dimensional signals for X-ray crystallography and related applications. This masked-illumination methodology was originally proposed in this paper, and our phase retrieval guarantee was based on a recovery method known as polarization. This week, the following paper was posted online, and it gives the first guarantee of this kind for a more popular recovery method called PhaseLift:

Phase retrieval from coded diffraction patterns

Emmanuel J. Candes, Xiaodong Li, Mahdi Soltanolkotabi

In particular, this paper shows that O(\log^4 n) masked illuminations enable PhaseLift recovery, and their result actually holds for a wide assortment of masks. Since this paper is so related to my research, I decided to interview one of the authors (Mahdi Soltanolkotabi). I’ve lightly edited his responses for formatting and hyperlinks:

Continue reading Phase retrieval from coded diffraction patterns

Determination of all pure quantum states from a minimal number of observables

Last year, I wrote a blog post that describes how phase retrieval applies to quantum mechanics.  The main idea is that the probability distribution of outcomes of a particular observable provide intensity measurements of the (pure) state vector with the observable’s eigenstates. In other words, each observable corresponds to a unitary matrix, with which we will effectively take intensity measurements of the desired state vector.  In a paper from 1978, Andrew Vogt mentioned Wright’s conjecture – that 3 observables suffice to determine the state vector up to phase.  This was inadvertently disproved in 2011 by Teiko Heinosaari, Luca Mazzarella and Michael M. Wolf (see this paper), who showed that 4M-o(M) measurements are necessary for injectivity over \mathbb{C}^M.  The natural question is then:

Do 4 observables suffice to completely determine a pure state?

The answer (in the affirmative) appeared on the arXiv today:

Determination of all pure quantum states from a minimal number of observables

Damien Mondragon, Vladislav Voroninski

In fact, Mondragon and Voroninski show something much stronger: four generic unitary matrices lend injective intensity measurements. Having spent a considerable amount of time thinking about this sort of problem, I was very excited to see this closure to Wright’s conjecture, and I decided to interview one of the authors (Voroninski).  I took the liberty of adding hyperlinks throughout:

Continue reading Determination of all pure quantum states from a minimal number of observables