Regularized Weighted Low Rank Approximation
This work addresses computational efficiency in low rank approximation for machine learning and data analysis, offering incremental improvements over existing methods.
The paper tackles the NP-hard variant of weighted low rank approximation with regularization, improving upon prior polynomial-time algorithms by deriving sharper guarantees based on statistical dimension rather than rank, leading to significantly faster rank-independent runtime.
The classical low rank approximation problem is to find a rank $k$ matrix $UV$ (where $U$ has $k$ columns and $V$ has $k$ rows) that minimizes the Frobenius norm of $A - UV$. Although this problem can be solved efficiently, we study an NP-hard variant of this problem that involves weights and regularization. A previous paper of [Razenshteyn et al. '16] derived a polynomial time algorithm for weighted low rank approximation with constant rank. We derive provably sharper guarantees for the regularized version by obtaining parameterized complexity bounds in terms of the statistical dimension rather than the rank, allowing for a rank-independent runtime that can be significantly faster. Our improvement comes from applying sharper matrix concentration bounds, using a novel conditioning technique, and proving structural theorems for regularized low rank problems.