Phase retrieval
I’ve got the power. / Like the crack of the whip/ I snap attack/ Front to back
2017-01-16 — 2019-11-07
Wherein the reconstruction of lost phase is undertaken and iterative methods such as the Griffin–Lim algorithm are presented, and gradient-based Wirtinger flow strategies are described for practical recovery.
feature construction
Hilbert space
machine learning
model selection
neural nets
optimization
You know the power of the signal; what is the phase? Griffin-Lim algorithm, Wirtinger flow methods based on Wirtinger calculus, “phase-gradient heap integration” (Pru and Søndergaard 2016).
TODO: investigate Yue M Lu’s work on phase retrieval as an important example in a large class of somewhat-analytically-understood nonconvex problems, starting from his recent slide deck on that theme.
🏗
1 Griffin-Lim iteration
A classic.
2 References
Adali, Schreier, and Scharf. 2011. “Complex-Valued Signal Processing: The Proper Way to Deal With Impropriety.” IEEE Transactions on Signal Processing.
Bahmani, and Romberg. 2016. “Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation.” arXiv:1610.04210 [Cs, Math, Stat].
Barkhuijsen, de Beer, Bovée, et al. 1985. “Retrieval of Frequencies, Amplitudes, Damping Factors, and Phases from Time-Domain Signals Using a Linear Least-Squares Procedure.” Journal of Magnetic Resonance (1969).
Candes, Emmanuel, Li, and Soltanolkotabi. 2015. “Phase Retrieval via Wirtinger Flow: Theory and Algorithms.” IEEE Transactions on Information Theory.
Candes, Emmanuel J., Strohmer, and Voroninski. 2011. “PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming.” Communications on Pure and Applied Mathematics.
Chen, and Candès. 2015. “Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems.” In Advances in Neural Information Processing Systems 28.
Chi, Lu, and Chen. 2019. “Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview.” IEEE Transactions on Signal Processing.
Dhifallah, Thrampoulidis, and Lu. 2018. “Phase Retrieval via Polytope Optimization: Geometry, Phase Transitions, and New Algorithms.” arXiv:1805.09555 [Cs, Math].
Goldstein, and Studer. 2016. “PhaseMax: Convex Phase Retrieval via Basis Pursuit.” arXiv:1610.07531 [Cs, Math].
Griffin, and Lim. 1984. “Signal Estimation from Modified Short-Time Fourier Transform.” IEEE Transactions on Acoustics, Speech, and Signal Processing.
Grosse, Raina, Kwong, et al. 2007. “Shift-Invariant Sparse Coding for Audio Classification.” In The Twenty-Third Conference on Uncertainty in Artificial Intelligence (UAI2007).
Hand, and Voroninski. 2016. “An Elementary Proof of Convex Phase Retrieval in the Natural Parameter Space via the Linear Program PhaseMax.” arXiv:1611.03935 [Cs, Math].
Jaganathan, Eldar, and Hassibi. 2015. “Phase Retrieval: An Overview of Recent Developments.” arXiv:1510.07713 [Cs, Math].
Jagatap, and Hegde. 2018. “Towards Sample-Optimal Methods for Solving Random Quadratic Equations with Structure.” In 2018 IEEE International Symposium on Information Theory (ISIT).
Li, and Zhou. 2016. “On Gradient Descent Algorithm for Generalized Phase Retrieval Problem.” arXiv:1607.01121 [Math].
Luo, Alghamdi, and Lu. 2019. “Optimal Spectral Initialization for Signal Recovery with Applications to Phase Retrieval.” IEEE Transactions on Signal Processing.
Marafioti, Perraudin, Holighaus, et al. 2019. “Adversarial Generation of Time-Frequency Features with Application in Audio Synthesis.” In International Conference on Machine Learning.
Masuyama, Yatabe, Koizumi, et al. 2019. “Deep Griffin-Lim Iteration.” In ICASSP 2019.
Moravec, Romberg, and Baraniuk. 2007. “Compressive Phase Retrieval.” In Wavelets XII.
Perraudin, Balazs, and Sondergaard. 2013. “A Fast Griffin-Lim Algorithm.” In 2013 IEEE Workshop on Applications of Signal Processing to Audio and Acoustics.
Pinilla, Bacca, Tourneret, et al. 2018. “A Smoothing Stochastic Phase Retrieval Algorithm for Solving Random Quadratic Systems.” In 2018 IEEE Statistical Signal Processing Workshop (SSP).
Pru, and Søndergaard. 2016. “Real-Time Spectrogram Inversion Using Phase Gradient Heap Integration.”
Rajaei, Gigan, Krzakala, et al. 2017. “Robust Phase Retrieval with the Swept Approximate Message Passing (prSAMP) Algorithm.” Image Processing On Line.
Seuret, and Gouaisbaut. 2013. “Wirtinger-Based Integral Inequality: Application to Time-Delay Systems.” Automatica.
Shechtman, Beck, and Eldar. 2014. “GESPAR: Efficient Phase Retrieval of Sparse Signals.” IEEE Transactions on Signal Processing.
Shechtman, Eldar, Cohen, et al. 2015. “Phase Retrieval with Application to Optical Imaging: A Contemporary Overview.” IEEE Signal Processing Magazine.
Slaney, Naar, and Lyon. 1994. “Auditory Model Inversion for Sound Separation.” In Proceedings of ICASSP ’94.
Sturm, Daudet, and Roads. 2006. “Pitch-Shifting Audio Signals Using Sparse Atomic Approximations.” In Proceedings of the 1st ACM Workshop on Audio and Music Computing Multimedia. AMCMM ’06.
Wang, Giannakis, Saad, et al. 2017. “Solving Most Systems of Random Quadratic Equations.” In Advances in Neural Information Processing Systems 30.
Zhang, Chi, and Liang. 2016. “Provable Non-Convex Phase Retrieval with Outliers: Median Truncated Wirtinger Flow.” arXiv:1603.03805 [Stat].
Zhang, and Liang. 2016. “Reshaped Wirtinger Flow for Solving Quadratic System of Equations.” In Advances in Neural Information Processing Systems 29.