Gabor Phase Retrieval via Semidefinite Programming

We consider the problem of reconstructing a function f is an element of L2(R)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f\in L<^>2({\mathbb R})$$\end{document} given phase-less samples of its Gabor transform, which is defined by Gf(x,y):=214 integral Rf(t)e-pi(t-x)2e-2 pi iytdt,(x,y)is an element of R2.\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} {\mathcal {G}}f(x,y) :=2<^>{\frac{1}{4}} \int _{\mathbb R}f(t) e<^>{-\pi (t-x)<^>2} e<^>{-2\pi i y t}\,\text{ d }t,\quad (x,y)\in {\mathbb R}<^>2. \end{aligned}$$\end{document}More precisely, given sampling positions Omega subset of R2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega \subseteq {\mathbb R}<^>2$$\end{document} the task is to reconstruct f (up to global phase) from measurements {|Gf(omega)|:omega is an element of Omega}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{|{\mathcal {G}}f(\omega )|: \,\omega \in \Omega \}$$\end{document}. This non-linear inverse problem is known to suffer from severe ill-posedness. As for any other phase retrieval problem, constructive recovery is a notoriously delicate affair due to the lack of convexity. One of the fundamental insights in this line of research is that the connectivity of the measurements is both necessary and sufficient for reconstruction of phase information to be theoretically possible. In this article we propose a reconstruction algorithm which is based on solving two convex problems and, as such, amenable to numerical analysis. We show, empirically as well as analytically, that the scheme accurately reconstructs from noisy data within the connected regime. Moreover, to emphasize the practicability of the algorithm we argue that both convex problems can actually be reformulated as semi-definite programs for which efficient solvers are readily available. The approach is based on ideas from complex analysis, Gabor frame theory as well as matrix completion. As a byproduct, we also obtain improved truncation error for Gabor expensions with Gaussian generators.