We consider convex optimization problems which are widely used as convex relaxations for low-rank matrix recovery problems. In particular, in several important problems, such as phase retrieval and robust PCA, the underlying assumption in many cases is that the optimal solution is rank-one. In this paper we consider a simple and natural sufficient condition on the objective so that the optimal solution to these relaxations is indeed unique and rank-one. Mainly, we show that under this condition, the standard Frank-Wolfe method with line-search (i.e., without any tuning of parameters whatsoever), which only requires a single rank-one SVD computation per iteration, finds an $\epsilon$-approximated solution in only $O(\log{1/\epsilon})$ iterations (as opposed to the previous best known bound of $O(1/\epsilon)$), despite the fact that the objective is not strongly convex. We consider several variants of the basic method with improved complexities, as well as an extension motivated by robust PCA, and finally, an extension to nonsmooth problems.

研究了低秩矩阵恢复问题的凸松弛问题，给出了使问题具有唯一秩为1的最优解的充分条件，并使用Frank-Wolfe方法和单个秩为1 SVD计算每个迭代来找到一个近似解。

无强凸性情况下Frank-Wolfe算法在秩一矩阵恢复中的线性收敛