Timezone: »
Poster
Approximation Algorithms for $\ell_0$-Low Rank Approximation
Karl Bringmann · Pavel Kolev · David Woodruff
We study the $\ell_0$-Low Rank Approximation Problem, where the goal is, given an $m \times n$ matrix $A$, to output a rank-$k$ matrix $A'$ for which $\|A'-A\|_0$ is minimized. Here, for a matrix $B$, $\|B\|_0$ denotes the number of its non-zero entries. This NP-hard variant of low rank approximation is natural for problems with no underlying metric, and its goal is to minimize the number of disagreeing data positions. We provide approximation algorithms which significantly improve the running time and approximation factor of previous work. For $k > 1$, we show how to find, in poly$(mn)$ time for every $k$, a rank $O(k \log(n/k))$ matrix $A'$ for which $\|A'-A\|_0 \leq O(k^2 \log(n/k)) \OPT$. To the best of our knowledge, this is the first algorithm with provable guarantees for the $\ell_0$-Low Rank Approximation Problem for $k > 1$, even for bicriteria algorithms. For the well-studied case when $k = 1$, we give a $(2+\epsilon)$-approximation in {\it sublinear time}, which is impossible for other variants of low rank approximation such as for the Frobenius norm. We strengthen this for the well-studied case of binary matrices to obtain a $(1+O(\psi))$-approximation in sublinear time, where $\psi = \OPT/\nnz{A}$. For small $\psi$, our approximation factor is $1+o(1)$.
Author Information
Karl Bringmann (Saarland University)
Pavel Kolev (Max-Planck-Institut für Informatik)
David Woodruff (Carnegie Mellon University)
More from the Same Authors
-
2021 Spotlight: Optimal Sketching for Trace Estimation »
Shuli Jiang · Hai Pham · David Woodruff · Richard Zhang -
2021 Poster: Linear and Kernel Classification in the Streaming Model: Improved Bounds for Heavy Hitters »
Arvind Mahankali · David Woodruff -
2021 Poster: Optimal Sketching for Trace Estimation »
Shuli Jiang · Hai Pham · David Woodruff · Richard Zhang -
2021 Poster: Few-Shot Data-Driven Algorithms for Low Rank Approximation »
Piotr Indyk · Tal Wagner · David Woodruff -
2020 Poster: Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes »
Minh Hoang · Nghia Hoang · Hai Pham · David Woodruff -
2020 Poster: Impossibility Results for Grammar-Compressed Linear Algebra »
Amir Abboud · Arturs Backurs · Karl Bringmann · Marvin Künnemann -
2020 Poster: Secretary and Online Matching Problems with Machine Learned Advice »
Antonios Antoniadis · Themis Gouleakis · Pieter Kleer · Pavel Kolev -
2017 Poster: Near Optimal Sketching of Low-Rank Tensor Regression »
Xingguo Li · Jarvis Haupt · David Woodruff -
2017 Poster: Is Input Sparsity Time Possible for Kernel Low-Rank Approximation? »
Cameron Musco · David Woodruff