快速交替极小化算法求解相位恢复问题：理论、方法及其应用

The phase retrieval (PR) problem is a fundamental problem in many fields, which is appealing for investigation. There are a lot of existing algorithms, including convex algorithms and nonconvex ones. For PR, heuristic methods based on nonconvex optimization often work surprisingly well in practice. However, investigation to understand nonconvex optimization in theory has started only recently. In this program, we will investigate the theory, algorithms of PR by fast alternating minimization algorithm with applications. We employ a strategy by splitting the variables and solve bivariate optimization problem. Frist of all, we investigate the geometry of the models, proving all local minimizers are the global minimizers for the bivariate optimization problems. It means we can find the global minimizer as long as algorithms converge to local minimizers. It is unnecessary to do careful initialization. Thus, our algorithm starts from random initialization and iterate by alternating gradient descent. We also prove that it converges to global minimizer piecewise-linearly. At last, we will apply our algorithm in real-world problems.

相位恢复问题是很多领域的基本问题，吸引着越来越多的研究者去深入研究。大量的算法对相位恢复问题进行了研究，包括凸优化的算法和非凸优化的算法。尤其是非凸优化的算法，在实际问题中的效果非常好。但是从理论上理解用于求解相位恢复问题的非凸优化算法才刚刚开始。本项目主要研究快速交替极小化算法求解相位恢复问题的理论、算法及其应用。我们运用分离变量的策略，求解双变量优化问题。首先我们来探究模型的几何特性，证明所有的局部极小点都是全局极小点。这就意味着只要算法收敛到局部极小点，那么我们就找到了全局极小点。从而寻求一个好的初始化是没有必要的。这样，我们的算法从随机初始化出发利用交替梯度下降算法迭代求解。我们证明算法分片线性收敛到全局最优解。最后，我们将相位恢复的算法应用到实际问题当中。

相位恢复是近年来信号处理领域的研究热点之一，它起源于研究从信号的Fourier变换的绝对值恢复信号的相位，在X射线晶体学、光学成像等很多领域有广泛的应用。对相位恢复问题，大量的算法对其进行了研究，包括凸优化的算法和非凸优化的算法。本项目将相位恢复问题建模为一个双变量优化问题，对模型的几何特性以及求解算法的收敛性进行了探讨。首先我们来探究模型的几何特性，证明所有的局部极小点都是全局极小点。这就意味着只要算法收敛到局部极小点，那么我们就找到了全局极小点。其次，我们提出了求解双变量优化问题的算法，并证明了算法是分片线性收敛到全局最优解。另外，我们对非高斯测量数据的相位恢复问题做了深入的研究。我们提出了广义谱初始化方法作为非凸目标函数的初始值，进而通过梯度下降方法得到全局最优解。数值结果进一步验证了理论结果。最后，我们将求解相位恢复问题的双变量优化问题推广到三变量优化问题求解张量分解问题。