Timezone: »

 
Poster
Regularized Weighted Low Rank Approximation
Frank Ban · David Woodruff · Richard Zhang

Wed Dec 11 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #17
in Algorithms -- Collaborative Filtering »
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.
Keywords: Regularization · Algorithms · Applications -> Matrix and Tensor Factorization; Theory
[ Paper]  [ Poster] 

Author Information

Frank Ban (UC Berkeley / Google)
David Woodruff (Carnegie Mellon University)
Richard Zhang (UC Berkeley)

More from the Same Authors