Research map / Learning theory and algorithms / Matrix and tensor methods
Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the coreset-and-sketch algorithm for rank-k BMF | Binary matrix factorization with Frobenius loss · BMF, Frobenius loss | approximation ratio: C≥576 -> 1+ε | Helped |
| Use the coreset-and-sketch algorithm instead of the prior doubly exponential approach | Binary matrix factorization with Frobenius loss · BMF, Frobenius loss | runtime: 2^{\frac{2^{\O{k}}}{\varepsilon^2}\log\frac{1}{\varepsilon}}\poly(n,d) -> 2^{\tO{k^2/\varepsilon^4}}\poly(n,d) | Helped |
| Allow a bicriteria rank increase for the L_p algorithm | Binary matrix factorization · BMF, L_p loss | approximation ratio: C≥122^{2p-2}+2^{p-1} -> 1+ε | Helped |
| Use the proposed bicriteria algorithm instead of the prior constant-factor algorithm | Binary matrix factorization · BMF, L_p loss | runtime: 2^{\poly(k)}\poly(n,d) -> 2^{\poly(k/\varepsilon)}\poly(n,d) | Mixed |
| Allow a bicriteria rank increase for BMF over F₂ | Binary matrix factorization · BMF over F₂ | approximation ratio: C≥40001 -> 1+ε | Helped |
| Use the proposed bicriteria algorithm instead of the prior algorithm without bicriteria relaxation | Binary matrix factorization over F₂ · BMF over F₂ | runtime: 2^{\frac{2^{\O{k}}}{\varepsilon^2}\log\frac{1}{\varepsilon}}\poly(n,d) -> 2^{\poly(k/\varepsilon)}\poly(n,d) | Helped |
Closest papers by meaning
- Faster Algorithms for Binary Matrix Factorization (ICML 2019 · similarity 0.95)
- Consistent Low-Rank Approximation (ICLR 2026 · similarity 0.88)
- Approximation Algorithms for $\ell_0$-Low Rank Approximation (NeurIPS 2017 · similarity 0.87)
- Efficiently Factorizing Boolean Matrices using Proximal Gradient Descent (NeurIPS 2022 · similarity 0.87)
- Federated Binary Matrix Factorization Using Proximal Optimization (AAAI 2025 · similarity 0.87)
- Provable Acceleration of Nesterov's Accelerated Gradient for Asymmetric Matrix Factorization and Linear Neural Networks (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.