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.
Method
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{ positivesemidefinite}
\nonumber\\
&U_{i,i}=1,\quad i=1,...,n\nonumber\end{align}\]
Problem (3) can be solved efficiently ; we call PhaseCut the resulting algorithm.
Example



Function \(f\)
 Reconstruction of \(f\) by PhaseCut, from its wavelet transform's moduli
 Reconstruction of \(f\) by the GerchbergSaxton algorithm [5]




Moduli of \(f\)'s wavelet transform
 Moduli reconstructed by PhaseCut
 Moduli reconstructed by the GerchbergSaxton 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).

Figure 1: Schematic layout of the scattering transform's computation
References
[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 shorttime 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