Talk
Algorithms for $\ell_p$ Low-Rank Approximation
Flavio Chierichetti · Sreenivas Gollapudi · Ravi Kumar · Silvio Lattanzi · Rina Panigrahy · David Woodruff
C4.4
[
Abstract
]
Abstract:
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.
Live content is unavailable. Log in and register to view live content