# Linear Convergence of Frank-Wolfe for Rank-One Matrix Recovery Without Strong Convexity

arXiv: https://arxiv.org/abs/1912.01467 · HTML: https://mlsanity.com/paper/1912.01467/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Dec 2019.

## Built on by (most cited first, 7 of 7)

- [Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise](https://mlsanity.com/paper/2506.04192/) (2025)
- [Frank-Wolfe with a Nearest Extreme Point Oracle](https://mlsanity.com/paper/2102.02029/) (2021)
- [Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problems](https://mlsanity.com/paper/2202.04026/) (2022)
- [Local Linear Convergence of Gradient Methods for Subspace Optimization via Strict Complementarity](https://mlsanity.com/paper/2202.04020/) (2022)
- [Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization Problems](https://mlsanity.com/paper/2206.11523/) (2022)
- [A Randomized Linearly Convergent Frank-Wolfe-type Method for Smooth Convex Minimization over the Spectrahedron](https://mlsanity.com/paper/2503.01441/) (2025)
- [Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity](https://mlsanity.com/paper/2511.02821/) (2025)

## Abstract (arXiv)

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 ε-approximated solution in only O(log1/ε) iterations (as opposed to the previous best known bound of O(1/ε)), 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.