We propose a simple, scalable, and fast gradient descent algorithm to
optimize a nonconvex objective for the rank minimization problem and a closely
related family of semidefinite programs. With $O(r^3 \kappa^2 n \log n)$ random
measurements of a positive semidefinite $n \times n$ matrix of rank $r$ and
condition number $\kappa$, our method is guaranteed to converge linearly to the
global optimum.

本研究提出了一种基于梯度下降的简单、可扩展、快速的算法来优化处理秩最小化问题及其相关的半定规划问题。通过对一个秩为 r 和条件数为 κ 的正半定 n x n 矩阵进行 O (r³κ²n log n) 次随机测量，我们证明了该方法可线性收敛于全局最优解。

一种收敛的梯度下降算法，用于基于随机线性测量的秩降和半定规划

A Convergent Gradient Descent Algorithm for Rank Minimization and  Semidefinite Programming from Random Linear Measurements

We study the problem of recovering the phase from magnitude measurements;
specifically, we wish to reconstruct a complex-valued signal x of C^n about
which we have phaseless samples of the form y_r = |< a_r,x >|^2, r = 1,2,...,m
(knowledge of the phase of these samples would yield a linear system). This
paper develops a non-convex formulation of the phase retrieval problem as well
as a concrete solution algorithm. In a nutshell, this algorithm starts with a
careful initialization obtained by means of a spectral method, and then refines
this initial estimate by iteratively applying novel update rules, which have
low computational complexity, much like in a gradient descent scheme. The main
contribution is that this algorithm is shown to rigorously allow the exact
retrieval of phase information from a nearly minimal number of random
measurements. Indeed, the sequence of successive iterates provably converges to
the solution at a geometric rate so that the proposed scheme is efficient both
in terms of computational and data resources. In theory, a variation on this
scheme leads to a near-linear time algorithm for a physically realizable model
based on coded diffraction patterns. We illustrate the effectiveness of our
methods with various experiments on image data. Underlying our analysis are
insights for the analysis of non-convex optimization schemes that may have
implications for computational problems beyond phase retrieval.

本文提出一种非凸公式的相位恢复方法，通过随机数迭代更新的规则精确地重建了信号的相位信息。此算法具有低计算复杂性并在计算和数据资源方面都非常有效。

通过 Wirtinger Flow 进行相位恢复：理论和算法

Phase Retrieval via Wirtinger Flow: Theory and Algorithms

Suppose we are given a vector $f$ in $\R^N$. How many linear measurements do
we need to make about $f$ to be able to recover $f$ to within precision
$\epsilon$ in the Euclidean ($\ell_2$) metric? Or more exactly, suppose we are
interested in a class ${\cal F}$ of such objects--discrete digital signals,
images, etc; how many linear measurements do we need to recover objects from
this class to within accuracy $\epsilon$? This paper shows that if the objects
of interest are sparse or compressible in the sense that the reordered entries
of a signal $f \in {\cal F}$ decay like a power-law (or if the coefficient
sequence of $f$ in a fixed basis decays like a power-law), then it is possible
to reconstruct $f$ to within very high accuracy from a small number of random
measurements.

论文证明，假设我们的目标是以欧几里得距离恢复稀疏或可压缩的离散数字信号、图像等，那么我们需要多少线性测量来达到精度为 ε 的要求，结果表明如果目标的重新排序条目以幂律衰减 (或在固定基中的系数序列以幂律衰减)，那么只需要很少的随机测量就可以高精度重建目标。