Poster
Tue Aug 08 01:30 AM -- 05:00 AM (PDT) @ Gallery #29
Algorithms for $\ell_p$ Low-Rank Approximation
In
Posters Tue
[
PDF]
[
Summary/Notes]
We consider the problem of approximating a given matrix by a
low-rank matrix so as to minimize the entrywise $\ell_p$-approximation error,
for any $p \geq 1$; the case $p = 2$ is the classical SVD problem.
We obtain the first provably good approximation algorithms for this
robust version of low-rank approximation that work for
every value of $p$.
Our algorithms are simple, easy to implement, work well in
practice, and illustrate interesting tradeoffs between the
approximation quality, the running time, and the rank of the
approximating matrix.