Incomplete low-rank matrices can be exactly recovered in most cases, so long as the rank is low enough relative to the number of known entries. This result was famously proved by Cands and Recht in the paper Exact Matrix Completion via Convex Optimization. Algorithmically, the nuclear norm minimization that recovers the full matrix requires keeping the entire data matrix in memory, and only after convergence can the matrix be reduced to its low-rank parts.Suppose we know that our matrix $X\in\mathbb{R}^{n\times n}$ is rank one: $X = uv^T$, $u$, $v\in\mathbb{R}^n$. When $n$ is large, keeping $X$ in memory may be intractable, even if it's very tractable to keep $u$ and $v$. A nice identity about the nuclear norm is that $||X||_* = \min_{u,v\,st\,uv^T=X} \frac{1}{2}||u||^2_2 + \frac{1}{2}||v||^2_2$, so it is possible to recast nuclear norm minimization as a minimization over $u$ and $v$ constrained such that $uv^T$ agrees with known entries of $X$. My question is this: can we carry out this minimization tractably? Will we still converge to the exact solution? How do we perform this minimization?
Exact recovery of large incomplete rank-one matrices?
optimization