APDE: Seminars

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)e^e{-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.

• Part of Applied and Computational Analysis
• Speaker: Philipp Grohs (University of Vienna)
• Thursday 05 October 2017, 15:00-16:00
• MR 14, CMS.

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.

• Part of Applied and Computational Analysis
• Speaker: Henry Wilton (University of Cambridge)
• Thursday 12 October 2017, 15:00-16:00
• MR 14, CMS.