Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
复制标题
DOI：
--
复制
发表时间：
2016-05
期刊：
影响因子：
--
通讯作者：
Huishuai Zhang;Yi Zhou;Ying Q. Liang;Yuejie Chi
中科院分区：
文献类型：
--
作者：
Huishuai Zhang;Yi Zhou;Ying Q. Liang;Yuejie Chi
我们研究了相位恢复问题，它解决了二次方程组，即，从它的幅度测量值$y_i恢复向量$\boldsymbol{x}\in \mathbb{R}^n$=|\langle \boldsymbol{a}_i，\boldsymbol{x}\rangle|，i=1，.，m$。我们开发了一个类似梯度的算法（简称为RWF代表重塑Wirtinger流）通过最小化非凸非光滑损失函数。与现有的非凸Wirtinger流算法相比，虽然损失函数变得非光滑，但它只涉及变量的二次幂，从而降低了算法的复杂度.我们表明，随机高斯测量，RWF享有几何收敛到一个全局最优点，只要测量的数量$m$的顺序$n$，未知$\boldsymbol{x}$的维度。这提高了WF的样本复杂度，并实现了与截断Wirtinger流（TWF）\cite{chen 2015 solving}相同的样本复杂度，但在梯度循环中没有截断。此外，RWF的计算成本低于WF，并且在数值上比WF和TWF运行得更快。我们进一步发展的增量（随机）重塑Wirtinger流（IRWF），并表明IRWF线性收敛到真实的信号。我们进一步建立现有的Kaczmarz方法的相位恢复问题的基础上，其连接到IRWF的性能保证。我们还实证表明，IRWF优于现有的ITWF算法（随机版本的TWF）以及其他批处理算法。
We study the phase retrieval problem, which solves quadratic system of equations, i.e., recovers a vector $\boldsymbol{x}\in \mathbb{R}^n$ from its magnitude measurements $y_i=|\langle \boldsymbol{a}_i, \boldsymbol{x}\rangle|, i=1,..., m$. We develop a gradient-like algorithm (referred to as RWF representing reshaped Wirtinger flow) by minimizing a nonconvex nonsmooth loss function. In comparison with existing nonconvex Wirtinger flow (WF) algorithm \cite{candes2015phase}, although the loss function becomes nonsmooth, it involves only the second power of variable and hence reduces the complexity. We show that for random Gaussian measurements, RWF enjoys geometric convergence to a global optimal point as long as the number $m$ of measurements is on the order of $n$, the dimension of the unknown $\boldsymbol{x}$. This improves the sample complexity of WF, and achieves the same sample complexity as truncated Wirtinger flow (TWF) \cite{chen2015solving}, but without truncation in gradient loop. Furthermore, RWF costs less computationally than WF, and runs faster numerically than both WF and TWF. We further develop the incremental (stochastic) reshaped Wirtinger flow (IRWF) and show that IRWF converges linearly to the true signal. We further establish performance guarantee of an existing Kaczmarz method for the phase retrieval problem based on its connection to IRWF. We also empirically demonstrate that IRWF outperforms existing ITWF algorithm (stochastic version of TWF) as well as other batch algorithms.