# Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming

arXiv: https://arxiv.org/abs/2310.19068 · HTML: https://mlsanity.com/paper/2310.19068/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 39 references that are in the map.
- First posted on arXiv 29 Oct 2023.

## Builds on (most cited first, 15 of 15)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Relative Error Tensor Low Rank Approximation](https://mlsanity.com/paper/1704.08246/) (2017)
- [Optimality of the Johnson-Lindenstrauss Lemma](https://mlsanity.com/paper/1609.02094/) (2016)
- [New Frameworks for Offline and Streaming Coreset Constructions](https://mlsanity.com/paper/1612.00889/) (2016)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [Optimal Principal Component Analysis in Distributed and Streaming Models](https://mlsanity.com/paper/1504.06729/) (2015)
- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [New Coresets for Projective Clustering and Applications](https://mlsanity.com/paper/2203.04370/) (2022)
- [One-Shot Coresets: The Case of k-Clustering](https://mlsanity.com/paper/1711.09649/) (2017)
- [Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets](https://mlsanity.com/paper/2204.04828/) (2022)
- [The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction](https://mlsanity.com/paper/1411.2404/) (2014)
- [Lower bounds for oblivious subspace embeddings](https://mlsanity.com/paper/1308.3280/) (2013)
- [New Subset Selection Algorithms for Low Rank Approximation: Offline and Online](https://mlsanity.com/paper/2304.09217/) (2023)
- [Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel k-means Clustering](https://mlsanity.com/paper/1905.06394/) (2019)

## Abstract (arXiv)

Sketching algorithms have recently proven to be a powerful approach both for designing low-space streaming algorithms as well as fast polynomial time approximation schemes (PTAS). In this work, we develop new techniques to extend the applicability of sketching-based approaches to the sparse dictionary learning and the Euclidean k-means clustering problems. In particular, we initiate the study of the challenging setting where the dictionary/clustering assignment for each of the n input points must be output, which has surprisingly received little attention in prior work. On the fast algorithms front, we obtain a new approach for designing PTAS's for the k-means clustering problem, which generalizes to the first PTAS for the sparse dictionary learning problem. On the streaming algorithms front, we obtain new upper bounds and lower bounds for dictionary learning and k-means clustering. In particular, given a design matrix mathbf A∈mathbb Rn× d in a turnstile stream, we show an tilde O(nr/ε2 + dk/ε) space upper bound for r-sparse dictionary learning of size k, an tilde O(n/ε2 + dk/ε) space upper bound for k-means clustering, as well as an tilde O(n) space upper bound for k-means clustering on random order row insertion streams with a natural "bounded sensitivity" assumption. On the lower bounds side, we obtain a general tildeOmega(n/ε + dk/ε) lower bound for k-means clustering, as well as an tildeOmega(n/ε2) lower bound for algorithms which can estimate the cost of a single fixed set of candidate centers.