Can we recover a complex signal from its Fourier magnitudes? More generally,
given a set of $m$ measurements, $y_k = |\mathbf a_k^* \mathbf x|$ for $k = 1,
\dots, m$, is it possible to recover $\mathbf x \in \mathbb{C}^n$ (i.e.,
length-$n$ complex vector)? This **generalized phase retrieval** (GPR) problem
is a fundamental task in various disciplines, and has been the subject of much
recent investigation. Natural nonconvex heuristics often work remarkably well
for GPR in practice, but lack clear theoretical explanations. In this paper, we
take a step towards bridging this gap. We prove that when the measurement
vectors $\mathbf a_k$'s are generic (i.i.d. complex Gaussian) and the number of
measurements is large enough ($m \ge C n \log^3 n$), with high probability, a
natural least-squares formulation for GPR has the following benign geometric
structure: (1) there are no spurious local minimizers, and all global
minimizers are equal to the target signal $\mathbf x$, up to a global phase;
and (2) the objective function has a negative curvature around each saddle
point. This structure allows a number of iterative optimization methods to
efficiently find a global minimizer, without special initialization. To
corroborate the claim, we describe and analyze a second-order trust-region
algorithm.

本文研究了广义相位恢复问题，并证明了当测量向量为一组具有一般性质（即满足 i.i.d 复高斯分布）且测量数量充足时，自然的最小二乘优化方法能够找到目标信号的全局最小值，同时避免了漏解及假解。为了证实该算法的可行性，本文还提出并分析了一个二阶信任域算法。

相位恢复的几何分析

A Geometric Analysis of Phase Retrieval

In this note, we focus on smooth nonconvex optimization problems that obey:
(1) all local minimizers are also global; and (2) around any saddle point or
local maximizer, the objective has a negative directional curvature. Concrete
applications such as dictionary learning, generalized phase retrieval, and
orthogonal tensor decomposition are known to induce such structures. We
describe a second-order trust-region algorithm that provably converges to a
global minimizer efficiently, without special initializations. Finally we
highlight alternatives, and open problems in this direction.

通过二阶信赖域算法，我们可以高效地找到满足所有局部极小值点也是全局极小值点并且任何一点的方向曲率为负的非凸优化问题的全局极小解。