Timezone: »
Talk
Algorithms for $\ell_p$ Low-Rank Approximation
Flavio Chierichetti · Sreenivas Gollapudi · Ravi Kumar · Silvio Lattanzi · Rina Panigrahy · David Woodruff
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.
Summary/NotesAuthor Information
Flavio Chierichetti (Sapienza University of Rome)
Sreenivas Gollapudi
Ravi Kumar (Google)
Silvio Lattanzi
Rina Panigrahy (Google)
David Woodruff
Related Events (a corresponding poster, oral, or spotlight)
-
2017 Poster: Algorithms for $\ell_p$ Low-Rank Approximation »
Tue. Aug 8th 08:30 AM -- 12:00 PM Room Gallery #29
More from the Same Authors
-
2021 : Randomized Response with Prior and Applications to Learning with Label Differential Privacy »
Badih Ghazi · Noah Golowich · Ravi Kumar · Pasin Manurangsi · Chiyuan Zhang -
2021 : User-Level Private Learning via Correlated Sampling »
Badih Ghazi · Ravi Kumar · Pasin Manurangsi -
2022 Poster: Parsimonious Learning-Augmented Caching »
Sungjin Im · Ravi Kumar · Aditya Petety · Manish Purohit -
2022 Poster: RUMs from Head-to-Head Contests »
Matteo Almanza · Flavio Chierichetti · Ravi Kumar · Alessandro Panconesi · Andrew Tomkins -
2022 Spotlight: RUMs from Head-to-Head Contests »
Matteo Almanza · Flavio Chierichetti · Ravi Kumar · Alessandro Panconesi · Andrew Tomkins -
2022 Spotlight: Parsimonious Learning-Augmented Caching »
Sungjin Im · Ravi Kumar · Aditya Petety · Manish Purohit -
2022 Poster: Faster Privacy Accounting via Evolving Discretization »
Badih Ghazi · Pritish Kamath · Ravi Kumar · Pasin Manurangsi -
2022 Spotlight: Faster Privacy Accounting via Evolving Discretization »
Badih Ghazi · Pritish Kamath · Ravi Kumar · Pasin Manurangsi -
2021 Poster: Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message »
Badih Ghazi · Ravi Kumar · Pasin Manurangsi · Rasmus Pagh · Amer Sinha -
2021 Spotlight: Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message »
Badih Ghazi · Ravi Kumar · Pasin Manurangsi · Rasmus Pagh · Amer Sinha -
2021 Poster: Locally Private k-Means in One Round »
Alisa Chang · Badih Ghazi · Ravi Kumar · Pasin Manurangsi -
2021 Oral: Locally Private k-Means in One Round »
Alisa Chang · Badih Ghazi · Ravi Kumar · Pasin Manurangsi -
2021 Poster: Light RUMs »
Flavio Chierichetti · Ravi Kumar · Andrew Tomkins -
2021 Spotlight: Light RUMs »
Flavio Chierichetti · Ravi Kumar · Andrew Tomkins -
2020 Poster: Online Learning with Imperfect Hints »
Aditya Bhaskara · Ashok Cutkosky · Ravi Kumar · Manish Purohit -
2020 Poster: Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead »
Badih Ghazi · Ravi Kumar · Pasin Manurangsi · Rasmus Pagh -
2019 Poster: Recursive Sketches for Modular Deep Learning »
Badih Ghazi · Rina Panigrahy · Joshua R. Wang -
2019 Poster: Faster Algorithms for Binary Matrix Factorization »
Ravi Kumar · Rina Panigrahy · Ali Rahimi · David Woodruff -
2019 Oral: Faster Algorithms for Binary Matrix Factorization »
Ravi Kumar · Rina Panigrahy · Ali Rahimi · David Woodruff -
2019 Oral: Recursive Sketches for Modular Deep Learning »
Badih Ghazi · Rina Panigrahy · Joshua R. Wang -
2018 Poster: Learning a Mixture of Two Multinomial Logits »
Flavio Chierichetti · Ravi Kumar · Andrew Tomkins -
2018 Oral: Learning a Mixture of Two Multinomial Logits »
Flavio Chierichetti · Ravi Kumar · Andrew Tomkins