Phase retrieval

I’ve got the power. / Like the crack of the whip/ I snap attack/ Front to back

January 17, 2017 — November 8, 2019

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).

Figure 2: Diagram from TiFGAN (Marafioti et al. 2019) via CJ.

TODO: investigate Yue M Lu’s work on phase retrieval as an important example in a large classe of somewhat- analytically-understood nonconvex problems, starting from his recent slide deck on that theme.

🏗

1 References

Adali, T., P. J. Schreier, and L. L. Scharf. 2011. “Complex-Valued Signal Processing: The Proper Way to Deal With Impropriety.” IEEE Transactions on Signal Processing 59 (11): 5101–25.

Bahmani, Sohail, and Justin Romberg. 2016. “Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation.” arXiv:1610.04210 [Cs, Math, Stat], October.

Barkhuijsen, H., R. de Beer, W. M. J. Bovée, and D. van Ormondt. 1985. “Retrieval of Frequencies, Amplitudes, Damping Factors, and Phases from Time-Domain Signals Using a Linear Least-Squares Procedure.” Journal of Magnetic Resonance (1969) 61 (3): 465–81.

Candes, Emmanuel J., Thomas Strohmer, and Vladislav Voroninski. 2011. “PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming.” Communications on Pure and Applied Mathematics 66 (8): 1241–74.

Candes, Emmanuel, Xiaodong Li, and Mahdi Soltanolkotabi. 2015. “Phase Retrieval via Wirtinger Flow: Theory and Algorithms.” IEEE Transactions on Information Theory 61 (4): 1985–2007.

Chen, Yuxin, and Emmanuel 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, edited by C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, 739–47. Curran Associates, Inc.

Chi, Yuejie, Yue M. Lu, and Yuxin Chen. 2019. “Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview.” IEEE Transactions on Signal Processing 67 (20): 5239–69.

Dhifallah, Oussama, Christos Thrampoulidis, and Yue M. Lu. 2018. “Phase Retrieval via Polytope Optimization: Geometry, Phase Transitions, and New Algorithms.” arXiv:1805.09555 [Cs, Math], May.

Goldstein, Tom, and Christoph Studer. 2016. “PhaseMax: Convex Phase Retrieval via Basis Pursuit.” arXiv:1610.07531 [Cs, Math], October.

Griffin, D., and Jae Lim. 1984. “Signal Estimation from Modified Short-Time Fourier Transform.” IEEE Transactions on Acoustics, Speech, and Signal Processing 32 (2): 236–43.

Grosse, Roger, Rajat Raina, Helen Kwong, and Andrew Y. Ng. 2007. “Shift-Invariant Sparse Coding for Audio Classification.” In The Twenty-Third Conference on Uncertainty in Artificial Intelligence (UAI2007), 9:8.

Hand, Paul, and Vladislav Voroninski. 2016. “An Elementary Proof of Convex Phase Retrieval in the Natural Parameter Space via the Linear Program PhaseMax.” arXiv:1611.03935 [Cs, Math], November.

Jaganathan, Kishore, Yonina C. Eldar, and Babak Hassibi. 2015. “Phase Retrieval: An Overview of Recent Developments.” arXiv:1510.07713 [Cs, Math], October.

Jagatap, G., and C. Hegde. 2018. “Towards Sample-Optimal Methods for Solving Random Quadratic Equations with Structure.” In 2018 IEEE International Symposium on Information Theory (ISIT), 1000:2296–2300.

Li, Ji, and Tie Zhou. 2016. “On Gradient Descent Algorithm for Generalized Phase Retrieval Problem.” arXiv:1607.01121 [Math], July.

Luo, Wangyu, Wael Alghamdi, and Yue M. Lu. 2019. “Optimal Spectral Initialization for Signal Recovery with Applications to Phase Retrieval.” IEEE Transactions on Signal Processing 67 (9): 2347–56.

Marafioti, Andrés, Nathanaël Perraudin, Nicki Holighaus, and Piotr Majdak. 2019. “Adversarial Generation of Time-Frequency Features with Application in Audio Synthesis.” In International Conference on Machine Learning, 4352–62. PMLR.

Masuyama, Yoshiki, Kohei Yatabe, Yuma Koizumi, Yasuhiro Oikawa, and Noboru Harada. 2019. “Deep Griffin-Lim Iteration.” In ICASSP 2019.

Moravec, Matthew L., Justin K. Romberg, and Richard G. Baraniuk. 2007. “Compressive Phase Retrieval.” In Wavelets XII, 6701:670120. San Diego, CA: International Society for Optics and Photonics.

Perraudin, Nathanael, Peter Balazs, and Peter L. Sondergaard. 2013. “A Fast Griffin-Lim Algorithm.” In 2013 IEEE Workshop on Applications of Signal Processing to Audio and Acoustics, 1–4. New Paltz, NY: IEEE.

Pinilla, S., J. Bacca, J. Tourneret, and H. Arguello. 2018. “A Smoothing Stochastic Phase Retrieval Algorithm for Solving Random Quadratic Systems.” In 2018 IEEE Statistical Signal Processing Workshop (SSP), 278–82.

Pru, Zdeneˇk, and Peter L Søndergaard. 2016. “Real-Time Spectrogram Inversion Using Phase Gradient Heap Integration,” 5.

Rajaei, Boshra, Sylvain Gigan, Florent Krzakala, and Laurent Daudet. 2017. “Robust Phase Retrieval with the Swept Approximate Message Passing (prSAMP) Algorithm.” Image Processing On Line 7 (January): 43–55.

Seuret, Alexandre, and Frédéric Gouaisbaut. 2013. “Wirtinger-Based Integral Inequality: Application to Time-Delay Systems.” Automatica 49 (9): 2860–66.

Shechtman, Y., A. Beck, and Y. C. Eldar. 2014. “GESPAR: Efficient Phase Retrieval of Sparse Signals.” IEEE Transactions on Signal Processing 62 (4): 928–38.

Shechtman, Y., Y. C. Eldar, O. Cohen, H. N. Chapman, J. Miao, and M. Segev. 2015. “Phase Retrieval with Application to Optical Imaging: A Contemporary Overview.” IEEE Signal Processing Magazine 32 (3): 87–109.

Slaney, M., D. Naar, and R.E. Lyon. 1994. “Auditory Model Inversion for Sound Separation.” In Proceedings of ICASSP ’94., ii:II/77–80. Adelaide, SA, Australia: IEEE.

Sturm, Bob L., Laurent Daudet, and Curtis Roads. 2006. “Pitch-Shifting Audio Signals Using Sparse Atomic Approximations.” In Proceedings of the 1st ACM Workshop on Audio and Music Computing Multimedia, 45–52. AMCMM ’06. New York, NY, USA: ACM.

Wang, Gang, Georgios Giannakis, Yousef Saad, and Jie Chen. 2017. “Solving Most Systems of Random Quadratic Equations.” In Advances in Neural Information Processing Systems 30, edited by I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, 1867–77. Curran Associates, Inc.

Zhang, Huishuai, Yuejie Chi, and Yingbin Liang. 2016. “Provable Non-Convex Phase Retrieval with Outliers: Median Truncated Wirtinger Flow.” arXiv:1603.03805 [Stat], March.

Zhang, Huishuai, and Yingbin Liang. 2016. “Reshaped Wirtinger Flow for Solving Quadratic System of Equations.” In Advances in Neural Information Processing Systems 29, edited by D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, 2622–30. Curran Associates, Inc.