Timezone: »
Poster
Faster Algorithms for Binary Matrix Factorization
Ravi Kumar · Rina Panigrahy · Ali Rahimi · David Woodruff
We give faster approximation algorithms for well-studied variants of Binary Matrix Factorization (BMF), where we are given a binary $m \times n$ matrix $A$ and would like to find binary rank-$k$ matrices $U, V$ to minimize the Frobenius norm of $U \cdot V - A$. In the first setting, $U \cdot V$ denotes multiplication over $\mathbb{Z}$, and we give a constant-factor approximation algorithm that runs in $2^{O(k^2 \log k)} \textrm{poly}(mn)$ time, improving upon the previous $\min(2^{2^k}, 2^n) \textrm{poly}(mn)$ time. Our techniques generalize to minimizing $\|U \cdot V - A\|_p$ for $p \geq 1$, in $2^{O(k^{\lceil p/2 \rceil + 1}\log k)} \textrm{poly}(mn)$ time. For $p = 1$, this has a graph-theoretic consequence, namely, a $2^{O(k^2)} \poly(mn)$-time algorithm to approximate a graph as a union of disjoint bicliques. In the second setting, $U \cdot V$ is over $\GF(2)$, and we give a bicriteria constant-factor approximation algorithm that runs in $2^{O(k^3)} \poly(mn)$ time
to find binary rank-$O(k \log m)$ matrices $U$, $V$ whose cost is as good as the best rank-$k$ approximation, improving upon $\min(2^{2^k}mn, \min(m,n)^{k^{O(1)}} \textrm{poly}(mn))$ time.
Author Information
Ravi Kumar (Google)
Rina Panigrahy (Google)
Ali Rahimi (Google)
David Woodruff (Carnegie Mellon University)
Related Events (a corresponding poster, oral, or spotlight)
-
2019 Oral: Faster Algorithms for Binary Matrix Factorization »
Thu. Jun 13th through Fri the 14th Room Seaside Ballroom
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 -
2023 Poster: Improved Algorithms for White-Box Adversarial Streams »
Ying Feng · David Woodruff -
2023 Poster: Sharper Bounds for $\ell_p$ Sensitivity Sampling »
David Woodruff · Taisuke Yasuda -
2023 Oral: Sharper Bounds for $\ell_p$ Sensitivity Sampling »
David Woodruff · Taisuke Yasuda -
2023 Poster: Bandit Online Linear Optimization with Hints and Queries »
Aditya Bhaskara · Ashok Cutkosky · Ravi Kumar · Manish Purohit -
2023 Poster: Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization »
Ameya Velingker · Maximilian Vötsch · David Woodruff · Samson Zhou -
2023 Poster: On User-Level Private Convex Optimization »
Badih Ghazi · Pritish Kamath · Ravi Kumar · Pasin Manurangsi · Raghu Meka · Chiyuan Zhang -
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 -
2022 Poster: Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra »
Nadiia Chepurko · Kenneth Clarkson · Lior Horesh · Honghao Lin · David Woodruff -
2022 Spotlight: Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra »
Nadiia Chepurko · Kenneth Clarkson · Lior Horesh · Honghao Lin · David Woodruff -
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 Workshop: Identifying and Understanding Deep Learning Phenomena »
Hanie Sedghi · Samy Bengio · Kenji Hata · Aleksander Madry · Ari Morcos · Behnam Neyshabur · Maithra Raghu · Ali Rahimi · Ludwig Schmidt · Ying Xiao -
2019 Poster: Recursive Sketches for Modular Deep Learning »
Badih Ghazi · Rina Panigrahy · Joshua Wang -
2019 Poster: Dimensionality Reduction for Tukey Regression »
Kenneth Clarkson · Ruosong Wang · David Woodruff -
2019 Poster: Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel $k$-means Clustering »
Taisuke Yasuda · David Woodruff · Manuel Fernandez -
2019 Oral: Recursive Sketches for Modular Deep Learning »
Badih Ghazi · Rina Panigrahy · Joshua Wang -
2019 Oral: Dimensionality Reduction for Tukey Regression »
Kenneth Clarkson · Ruosong Wang · David Woodruff -
2019 Oral: Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel $k$-means Clustering »
Taisuke Yasuda · David Woodruff · Manuel Fernandez -
2018 Poster: Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order »
Vladimir Braverman · Stephen Chestnut · Robert Krauthgamer · Yi Li · David Woodruff · Lin Yang -
2018 Oral: Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order »
Vladimir Braverman · Stephen Chestnut · Robert Krauthgamer · Yi Li · David Woodruff · Lin Yang -
2018 Poster: Leveraging Well-Conditioned Bases: Streaming and Distributed Summaries in Minkowski $p$-Norms »
Charlie Dickens · Graham Cormode · David Woodruff -
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 -
2018 Oral: Leveraging Well-Conditioned Bases: Streaming and Distributed Summaries in Minkowski $p$-Norms »
Charlie Dickens · Graham Cormode · David Woodruff -
2017 Poster: Algorithms for $\ell_p$ Low-Rank Approximation »
Flavio Chierichetti · Sreenivas Gollapudi · Ravi Kumar · Silvio Lattanzi · Rina Panigrahy · David Woodruff -
2017 Talk: Algorithms for $\ell_p$ Low-Rank Approximation »
Flavio Chierichetti · Sreenivas Gollapudi · Ravi Kumar · Silvio Lattanzi · Rina Panigrahy · David Woodruff