Fundamental Limits of Weak Recovery with Applications to Phase Retrieval

Marco Mondelli recently posted his latest paper on the arXiv (joint work with Andrea Montanari). This paper proves sharp guarantees for weak recovery in phase retrieval. In particular, given phaseless measurements against Gaussian vectors, they demonstrate that a properly tuned spectral estimate exhibits correlation with the ground truth, even when the sampling rate is at the information-theoretic limit. In addition, they show that their spectral estimate empirically performs well even when the measurements follow a more realistic coded diffraction model. I decided to reach out to Marco to learn more, and what follows is my interview. I’ve lightly edited his responses for formatting and hyperlinks:

DGM: Judging by your website, this project in phase retrieval appears to be a departure from your coding theory background. How did this project come about?

MM: Many of the tools employed in information and coding theory are very general and they prove useful also to solve problems in other fields, such as, compressed sensing, machine learning or data analysis. So this is the general philosophy that motivated my “detour”.

Probably certifiably correct algorithms

This post is based on two papers (one and two). The task is to quickly solve typical instances of a given problem, and to quickly produce a certificate of that solution. Generally, problems of interest are NP-hard, and so we consider a random distribution on problem instances with the philosophy that real-world instances might mimic this distribution. In my community, it is common to consider NP-hard optimization problems:

minimize subject to .     (1)

In some cases, is convex but is not, and so one might relax accordingly:

minimize subject to ,     (2)

where is some convex set. If the minimizer of (2) happens to be a member of , then it’s also a minimizer of (1) — when this happens, we say the relaxation is tight. For some problems (and distributions on instances), the relaxation is typically tight, which means that (1) can be typically solved by instead solving (2); for example, this phenomenon occurs in phase retrieval, in community detection, and in geometric clustering. Importantly, strong duality ensures that solving the dual of the convex relaxation provides a certificate of optimality.

Frames and Combinatorial & Algebraic Geometry

This last week, I attended a workshop at Universitat Bremen on Frames and Combinatorial & Algebraic Geometry. The organizers (Emily King and Eva Maria Feichtner) did a phenomenal job, and I was impressed by the quality of the talks (see this page for the slides). Below are a few of the things that we discussed throughout the workshop:

— Strohmer’s Problem —

At this year’s SampTA conference, Thomas Strohmer posed an interesting frame theory problem during his plenary talk. On the first day of the workshop, Ole Christensen suggested that we study the problem, and it ended up being one of our main focuses. Here’s a technical statement of the problem sans frame-theoretic jargon:

Strohmer’s Problem. Let be a known matrix, let be an unknown diagonal matrix, and let be an unknown matrix. Under what conditions does uniquely determine  and/or ?

This problem is motivated by the real-world problem of self-calibration (see for example this blog entry). In particular, the columns of represent unknown test signals, whereas represents unknown parameters of a linear sensor . The goal of self-calibration is to calibrate your sensor without requiring knowledge of the input (this is particularly important for applications like deep-space imaging).

The 4M-4 Conjecture is False!

Congratulations to Cynthia Vinzant for disproving the 4M-4 conjecture! The main result of her 4-page paper is the existence of a matrix such that is injective modulo a global phase factor (indeed, ). This is not Cynthia’s first contribution to this problem—her recent paper with Conca, Edidin and Hering proves that the conjecture holds for infinitely many .

I wanted to briefly highlight the main idea behind this paper: She provides an algorithm that, on input of a matrix with complex rational entries, either outputs “not known to be injective” or outputs “injective” along with a certificate of injectivity. The algorithm is fundamentally based on the following characterization of injectivity:

Sparse Representations, Numerical Linear Algebra, and Optimization Workshop

A couple of weeks ago, I attended the “Sparse Representations, Numerical Linear Algebra, and Optimization Workshop.” It was my first time at Banff, and I was thoroughly impressed by the weather, the facility, and the workshop organization. A few of the talks were recorded and are available here. Check out this good-looking group of participants:

I wanted to briefly outline some of the problems that were identified throughout the workshop.

Compressed sensing: Variations on a theme

A couple of months ago, I attended a workshop at Oberwolfach (my first!) called “Mathematical Physics meets Sparse Recovery.” I had a great time. I was asked to give the first talk of the week to get everyone on the same page with respect to sparse recovery. Here are the slides from my talk. What follows is an extended abstract (I added hyperlinks throughout for easy navigation):

Compressed sensing has been an exciting subject of research over the last decade, and the purpose of this talk was to provide a brief overview of the subject. First, we considered certain related topics (namely image compression and denoising) which led up to the rise of compressed sensing. In particular, wavelets provide a useful model for images, as natural images tend to be approximated by linear combinations of particularly few wavelets. This sparsity model has enabled JPEG2000 to provide particularly efficient image compression with negligible distortion. Additionally, this model has been leveraged to remove random noise from natural images.

Considering natural images enjoy such a useful model, one may ask whether the model can be leveraged to decrease the number of measurements necessary to completely determine an image. For example, an MRI scan might require up to 2 hours of exposure time, and then the image might be compressed with JPEG2000 after the fact, meaning most of the measurements can be effectively ignored. So is it possible to simply measure the important parts of the image and not waste time in the image acquisition process? This is the main idea underlying compressed sensing, as introduced by Candes, Romberg and Tao and Donoho.

Phase retrieval from coded diffraction patterns

In a previous post, I described a paper I wrote with Afonso and Yutong about how to design masked illuminations that enable efficient phase retrieval of -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 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:

Phase retrieval from very few measurements

Before the AIM meeting last month, I posted a paper on the arXiv that I wrote with Matt Fickus, Aaron Nelson and Yang Wang. This paper provides some very interesting results for phase retrieval in the setting where you wish to use as few intensity measurements as possible. There are really three different types of results in this paper, and they are partitioned into three different sections accordingly.

— 4M-4 injective intensity measurements —

Recall that Bodmann and Hammen provide a construction of vectors in which yield injective intensity measurements. Such an explicit construction is rather interesting because is conjectured to be the smallest for which this is even possible. From my perspective, any insight into the structure of such ensembles could lead to a deeper understanding of what it takes to be injective in the complex case, and so such constructions are particularly important.

In our paper, we provide a second construction of injective intensity measurements, and our method for proving injectivity was very different from the Bodmann-Hammen approach. Specifically, it is not clear if the Bodmann-Hammen construction has an efficient reconstruction algorithm, whereas for our construction, injectivity is essentially proved by applying a particular reconstruction algorithm that we designed in concert with the ensemble. We used several key ideas in our design, and I’ll briefly discuss them here.

AIM workshop: Frame theory intersects geometry

A couple of years ago, I was invited to attend my first AIM workshop, and it was finally held this last week. The topic was Frame theory intersects geometry, and as the name suggests, this workshop was an experiment of sorts to get two different communities together to solve various problems. Specifically, we focused on how to leverage techniques from algebraic geometry to solve certain infamous problems in frame theory, and with a number of successes. This entry overviews these successes.

— Part b of the 4M-4 conjecture is true —

Phase retrieval served as one of the main thrusts of this workshop. To help get the ball rolling on this subject, Thomas Strohmer and I gave survey talks on the subject (here are my slides). As a workshop, we quickly put our sights on the 4M-4 conjecture, which states that 4M-4 intensity measurements are necessary and generically sufficient for injectivity. I detail this conjecture in this blog post, where I also offer $100 for the solution. In that post, I indicated that part b (generic sufficiency) is probably the lower-hanging fruit. In another post, I interviewed Vlad Voroninski about his recent proof that 4 generic unitaries suffice for injectivity, and he indicated that similar proof techniques should resolve part b. This week, these suspicions proved correct, as part b was solved (or at least an extremely plausible argument was sketched and will be written up rigorously soon).

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 measurements are necessary for injectivity over .  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: