APDE: Seminars

Seminars in Applied and Computational Analysis

Stable Gabor Phase Retrieval and Spectral Clustering

We consider the problem of reconstructing a signal $f$ from its spectrogram, i.e., the magnitudes $|V_\varphi f|$ of its Gabor transform $$V_\varphi f (x,y):=\int_{\mathbb{R}}f(t)ee{-2\pi \i y t}dt, \quad x,y\in \mathbb{R}.$$ Such problems occur in a wide range of applications, from optical imaging of nanoscale structures to audio processing and classification.

While it is well-known that the solution of the above Gabor phase retrieval problem is unique up to natural identifications, the stability of the reconstruction has remained wide open. The present paper discovers a deep and surprising connection between phase retrieval, spectral clustering and spectral geometry. We show that the stability of the Gabor phase reconstruction is bounded by the reciprocal of the \emph{Cheeger constant} of the flat metric on $\mathbb{R}^2$, conformally multiplied with $|V_\varphi f|$. The Cheeger constant, in turn, plays a prominent role in the field of spectral clustering, and it precisely quantifies the `disconnectedness’ of the measurements $V_\varphi f$.

It has long been known that a disconnected support of the measurements results in an instability—our result for the first time provides a converse in the sense that there are no other sources of instabilities.

Due to the fundamental importance of Gabor phase retrieval in coherent diffraction imaging, we also provide a new understanding of the stability properties of these imaging techniques: Contrary to most classical problems in imaging science whose regularization requires the promotion of smoothness or sparsity, the correct regularization of the phase retrieval problem promotes the `connectedness’ of the measurements in terms of bounding the Cheeger constant from below. Our work thus, for the first time, opens the door to the development of efficient regularization strategies.

Undecidability in geometry and topology

There is a beautiful tension in topology between positive classification theorems and negative “no-go” theorems. The positive results come from geometry, and often derive ultimately from analysis. The negative results, by contrast, come from undecidability results in logic. I’ll give a survey of the history of this tension, and mention the highlight theorems — examples include Markov’s theorem that 4-manifolds cannot be classified (on the negative side), and Perelman’s Geometrization Theorem in dimension 3 (on the positive side). I’ll then go on to describe some recent undecidability results, which limit possible computations in matrix groups. This is joint work with Martin Bridson.

Graduate Seminars (WE 15:00, MR5)