Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time

arXiv:2302.11068v3 Announce Type: replace
Abstract: Given a matrix $M\in \mathbb{R}^{m\times n}$, the low rank matrix completion problem asks us to find a rank-$k$ approximation of $M$ as $UV^\top$ for $U\in \mathbb{R}^{m\times k}$ and $V\in \mathbb{R}^{n\times k}$ by only observing a few entries specified by a set of entries $\Omega\subseteq [m]\times [n]$. In particular, we examine an approach that is widely used in practice -- the alternating minimization framework. Jain, Netrapalli, and Sanghavi [JNS13] showed that if $M$ has incoherent rows …

abstract approximation arxiv cs.ds cs.lg linear low math.oc matrix robust set stat.ml type via