Inverse Problems

Phase Retrieval

Phase retrieval is an inverse problem whose goal is to recover the complex phase of a linear invertible tranfsorm of a signal given the value of its complex modulus.Such problems appear in physics when wave amplitudes can be measured but not their phase ([1] for a review), and in audio signal processing [2]. Recovering the complex phase of a Fourier transform from its modulus is a classic phase retrieval problem.

Let \(a_1,...,a_n\in\mathbb{C}^p\) be fixed ; \(f\in\mathbb{C}^p\) is unknown.
The goal is to: \[\begin{align}\mbox{Reconstruct } &f\in\mathbb{C}^p\\ \mbox{from }&\{|\langle f,a_k\rangle|\}_{k=1,...,n}\nonumber \end{align}\] Here, \(|.|\) denotes the complex modulus.

We use a "PhaseCut" convexification technique having similarities with the convexification algorithm described in [3,4].
Let \(A\) be the matrix whose rows are the \(a_k^*\) (we denote by \(a_k^*\) the transpose of \(a_k\)'s complex conjugate). For a suitable matrix \(M\), with a change of variables, one can rewrite (1) as \[\begin{align}\mbox{Minimize }&\mbox{Tr }(Muu^*)\\ \mbox{subject to }&u\in\mathbb{C}^n\nonumber\\ &|u_i|=1,\quad i=1,...,n\nonumber\end{align}\] and this last problem can be approximated by \[\begin{align}\mbox{Minimize }&\mbox{Tr }(MU)\\ \mbox{subject to }&U \mbox{ positive-semidefinite} \nonumber\\ &|U_{i,i}|=1,\quad i=1,...,n\nonumber\end{align}\] Problem (3) can be solved efficiently ; we call PhaseCut the resulting algorithm.

Gaussian noise The same Gaussian noise as left An approximation of poor quality of the Gaussian noise displayed on the first two images
Function \(f\) Reconstruction of \(f\) by PhaseCut, from its wavelet transform's moduli Reconstruction of \(f\) by the Gerchberg-Saxton algorithm [5]
Wavelet transform of f, in modulus, with four wavelets Wavelet transform of f's reconstruction by PhaseLift, same as f's wavelet transform Wavelet transform of f's reconstruction by the Gerchberg-Saxton algorithm, similar but clearly different from f's wavelet transform
Moduli of \(f\)'s wavelet transform Moduli reconstructed by PhaseCut Moduli reconstructed by the Gerchberg-Saxton algorithm

Paper and software

Paper reference on phase recovery is given by Phase Recovery, MaxCut and Complex Semidefinite Programming, d'Aspremont A., Mallat S., Waldspurger I., Mathematical Programming, 2015. (PDF).

An implementation of PhaseCut in Octave/MATLAB is available here.

Relation to scattering

The scattering transform is computed by composing with itself an operator \(U\) of the form \(U:f\to\{|f\star\psi_j|\}_{j\in\mathbb{Z}}\), where the \(\psi_j\)'s are functions of \(L^2\). Under particular hypotheses, one can show that \(U\) is invertible ; the study of \(U^{-1}\) and of its instabilities is interesting for the comprehension of the scattering operator's behavior.
After discretization, the problem of calculating \(U^{-1}\) is of the form (1).
Representation of the scattering operator as a cascade of operators U
Figure 1: Schematic layout of the scattering transform's computation


[1] Recent advances in phase retrieval, R. P. Millane, in “Image Reconstruction from Incomplete Data IV”, P.J. Bones, M.A. Fiddy and R.P. Millane (editors), Proceedings of SPIE, Vol. 6316, 2006

[2] Signal estimation from modified short-time Fourier transform, D. W. Griffin, J. S. Lim, IEEE Transactions on acoustics, speech and signal processing, April 1984

[3] PhaseLift: exact and stable signal recovery from magnitude measurements via convex programming E. J. Candès, T. Strohmer, V. Voroninski, to appear in "Communications on Pure and Applied Mathematics", 2011

[4] Phase retrieval via matrix completion E. J. Candès, Y. Eldar, T. Strohmer, V. Voroninski, 2011

[5] A practical algorithm for the determination of phase from image and diffraction plane pictures R. Gerchberg, W. Saxton, Optik, volume 35, 1972