Two common approaches in low-rank optimization problems are either working
directly with a rank constraint on the matrix variable, or optimizing over a
low-rank factorization so that the rank constraint is implicitly ensured. In
this paper, we study the natural connection between the rank-constrained and
factorized approaches. We show that all second-order stationary points of the
factorized objective function correspond to fixed points of projected gradient
descent run on the original problem (where the projection step enforces the
rank constraint). This result allows us to unify many existing optimization
guarantees that have been proved specifically in either the rank-constrained or
the factorized setting, and leads to new results for certain settings of the
problem. We demonstrate application of our results to several concrete low-rank
optimization problems arising in matrix inverse problems.

本文研究了低秩优化问题中矩阵变量秩约束和低秩分解优化方法的自然联系，证明了低秩分解目标函数的所有二阶稳定点对应于原问题上投影梯度下降算法的不动点，并统一了现有的优化保证，为某些情况下特定的问题提供了新结果。最后，将结果应用于矩阵逆问题。

排名限制与低秩分解的临界点之间的等价性

An equivalence between critical points for rank constraints versus  low-rank factorizations

Alternating Minimization is a widely used and empirically successful
heuristic for matrix completion and related low-rank optimization problems.
Theoretical guarantees for Alternating Minimization have been hard to come by
and are still poorly understood. This is in part because the heuristic is
iterative and non-convex in nature. We give a new algorithm based on
Alternating Minimization that provably recovers an unknown low-rank matrix from
a random subsample of its entries under a standard incoherence assumption. Our
results reduce the sample size requirements of the Alternating Minimization
approach by at least a quartic factor in the rank and the condition number of
the unknown matrix. These improvements apply even if the matrix is only close
to low-rank in the Frobenius norm. Our algorithm runs in nearly linear time in
the dimension of the matrix and, in a broad range of parameters, gives the
strongest sample bounds among all subquadratic time algorithms that we are
aware of.
Underlying our work is a new robust convergence analysis of the well-known
Power Method for computing the dominant singular vectors of a matrix. This
viewpoint leads to a conceptually simple understanding of Alternating
Minimization. In addition, we contribute a new technique for controlling the
coherence of intermediate solutions arising in iterative algorithms based on a
smoothed analysis of the QR factorization. These techniques may be of interest
beyond their application here.

使用一种基于交替最小化的新算法，在标准不连贯性假设下，可从一个未知的低秩矩阵中恢复随机子样本的条目，并减少至少一次方之秩和相似矩阵的条件数的交替最小化方法的样本大小要求。