Favourable Landscape of Phase Retrieval Problem with Optimal Sampling Complexity
Abstract
There are many efficient numerical solvers based on non-convex optimizations for the phase retrieval problem. Despite possible local minima of nonconvex objective functions, these algorithms often work remarkably well to find the global minimum. To explain this phenomenon theoretically, there are two frameworks. One theoretical framework is based on the analysis of the nonconvex objective functions locally in a small neighbourhood of global minimizers. It first constructs a special initialization that is close enough to a global minimizer, and then proves convergence of nonconvex algorithms to the global minimizer. This explanation usually needs only O(n) samples, the optimal sampling complexity. However, it does not explain why nonconvex algorithm with arbitrary initializations still works well. The other theoretical framework analyzes the nonconvex optimization more globally. It proves that nonconvex objective functions in phase retrieval have a favourable landscape - any local minimum is global. Therefore, it is not an issue to get trapped into a local minimum. To have such a favourable landscape, the best existing result needs O(n log^3n) samples, which is not optimal. In this talk, the speaker proves that, with O(n) samples, some nonconvex objective functions for phase retrieval can still have the favourable landscape.
About the speaker
Prof. CAI Jianfeng received his PhD in Mathematics at the Chinese University of Hong Kong in 2007. In 2007 – 2009, he was the Research Scientist at the Temasek Laboratories of the National University of Singapore. He then joined the University of California, Los Angeles as a CAM Assistant Adjunct Professor in 2009, before he moved to the University of Iowa as an Assistant Professor in 2011. He joined The Hong Kong University of Science and Technology in 2015 and is currently an Associate Professor of Mathematics.
Prof. Cai’s research focuses on the design and analysis algorithms for problems in data analysis, signal/image processing, and machine learning. He was named as a 2017 Highly Cited Researcher in Mathematics by Clarivate Analytics.
About the program
For more information, please refer to the program website at http://iasprogram.ust.hk/inverseproblems.
