Research map / Learning theory and algorithms / Clustering
Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming
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 a projective-clustering coreset and enumerate the sparse-factor pattern | Sparse dictionary learning · Sparse dictionary learning | approximation ratio: (1+\epsilon) | Helped |
| Combine dimensionality reduction, a coreset, and leverage-score sampling | Euclidean k-means · Euclidean k-means | running time: n\cdot\operatorname{poly}(k/\epsilon) + \exp(\frac{k}{\epsilon} \operatorname{polylog}(k/\epsilon)) | Helped |
| Use three linear sketches with guess-the-sketch | Euclidean k-means streaming algorithm · Euclidean k-means, turnstile stream | space: \tilde{\mathcal{O}}(n/\epsilon^2 + dk/\epsilon) | Helped |
| Restrict coefficient rows to a discrete r-sparse space and use three linear sketches | Sparse dictionary learning streaming algorithm · Discrete r-sparse dictionary learning, turnstile stream | space: \tilde{\mathcal{O}}(nr/\epsilon^2 + dk/\epsilon) | Helped |
| Require the algorithm to output assignments and centers for a nearly optimal clustering | Turnstile k-means streaming algorithms · Euclidean k-means with assignments and centers, turnstile stream | space lower bound: \tilde\Omega(n/\epsilon) | Hurt |
| Require near-optimal assignments for a fixed candidate set of centers | Turnstile k-means streaming algorithms · Fixed-center assignment, Euclidean k-means, turnstile stream | space lower bound: \Omega(\epsilon^{-2}n) | Hurt |
| Assume random-order row arrival and bounded maximum sensitivity | Euclidean k-means streaming algorithm · Euclidean k-means, random-order row arrival | space: \tilde O(\alpha nkd/\epsilon^4 + dk/\epsilon + n) | Helped |
| Set the sensitivity bound to \alpha \leq \epsilon^4/kd | Bounded-sensitivity k-means streaming algorithm · Euclidean k-means, random-order row arrival | space: \tilde O(n + dk/\epsilon) | Helped |
| Require outputting centers achieving a (1+\epsilon)-approximation | Row-arrival k-means streaming algorithms · Euclidean k-means, row-arrival stream | space lower bound: \tilde\Omega(dk/\epsilon) | Hurt |
Closest papers by meaning
- Randomized Sketches for Clustering: Fast and Optimal Kernel $k$-Means (NeurIPS 2022 · similarity 0.87)
- Simple, Scalable and Effective Clustering via One-Dimensional Projections (NeurIPS 2023 · similarity 0.87)
- Sparse Embedded $k$-Means Clustering (NeurIPS 2017 · similarity 0.86)
- Improved Learning-augmented Algorithms for k-means and k-medians Clustering (ICLR 2023 · similarity 0.86)
- Streaming Algorithms and Lower Bounds for Estimating Correlation Clustering Cost (NeurIPS 2023 · similarity 0.86)
- Learning-Augmented Streaming Algorithms for Correlation Clustering (NeurIPS 2025 · 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.