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{ 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.
Example
|
|
|
Function \(f\)
| Reconstruction of \(f\) by PhaseCut, from its wavelet transform's moduli
| Reconstruction of \(f\) by the Gerchberg-Saxton algorithm [5]
|
|
|
|
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).
|
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 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