Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile
  Streaming
Gregory Dexter Petros Drineas David P. Woodruff Taisuke Yasuda
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\in\mathbb R^{n\times d}$ in a
turnstile stream, we show an $\tilde O(nr/\epsilon^2 + dk/\epsilon)$ space
upper bound for $r$-sparse dictionary learning of size $k$, an $\tilde
O(n/\epsilon^2 + dk/\epsilon)$ 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 $\tilde\Omega(n/\epsilon +
dk/\epsilon)$ lower bound for $k$-means clustering, as well as an
$\tilde\Omega(n/\epsilon^2)$ lower bound for algorithms which can estimate the
cost of a single fixed set of candidate centers.