Abstract
Sparse Dictionary Learning (SDL) and $k$-means clustering are foundational techniques in unsupervised learning. While approximation schemes for $k$-means are well-established, similar guarantees for SDL have remained elusive. Furthermore, maintaining cluster or dictionary assignments in the challenging turnstile streaming model—where data can be both added and deleted—presents significant space complexity hurdles. This paper presents the first Polynomial Time Approximation Scheme (PTAS) for SDL and establishes near-optimal space bounds for the assignment problem in turnstile streams.
Introduction
In $k$-means clustering, the goal is to partition $n$ data points into $k$ clusters, minimizing the sum of squared distances to the nearest center. Sparse Dictionary Learning (SDL) generalizes this by representing each data point as a linear combination of at most $r$ dictionary atoms from a set of $k$ atoms. Despite their ubiquity, two significant gaps persist in the literature: the lack of a PTAS for SDL and the high memory cost of the "assignment problem" in streaming environments.
The assignment problem involves not just finding the optimal centers or dictionary, but also determining which atoms or clusters correspond to each specific data point. In "turnstile" streams, where entries can be updated arbitrarily, this task becomes particularly difficult. This work addresses these gaps by leveraging a unified toolkit of sketching and coresets.
A PTAS for Sparse Dictionary Learning
The primary theoretical contribution is the first PTAS for SDL. For fixed $k, r,$ and $\epsilon$, the algorithm provides a $(1+\epsilon)$ approximation in polynomial time.
SDL as Projective Clustering
A key insight of this work is that $r$-sparse dictionary learning can be framed as a specific instance of $(l, m)$-projective clustering. In projective clustering, the goal is to find a collection of low-dimensional subspaces that best fit the data. By establishing this connection, the authors adapt advanced coreset techniques originally developed for geometric clustering to the SDL problem.
Coreset Construction
To handle the massive scale of potential data, the algorithm reduces the dataset of $n$ points into a representative "coreset" of size $O(\log n)$. This reduction preserves the objective function's value within a $(1+\epsilon)$ factor for any candidate dictionary. The small size of the coreset allows the use of sophisticated polynomial system solvers, such as Renegar’s algorithm, to find the optimal dictionary atoms in time polynomial in $n$.
The Assignment Problem in Turnstile Streams
In many real-world applications, identifying the dictionary atoms or cluster centers is insufficient; one must also recover the assignments for each data point.
Space Complexity and Lower Bounds
The paper demonstrates that outputting assignments is fundamentally more memory-intensive than simply identifying centers. In a turnstile stream, any algorithm that outputs assignments for $k$-means requires at least $\Omega(n/\epsilon)$ bits of space. This lower bound is derived using reductions from the "Set Disjointness" problem in communication complexity, proving that the $n$ dependency is unavoidable.
Upper Bounds via Sketching
To match these lower bounds, the authors propose a "guess-the-sketch" framework. By maintaining small linear sketches (such as Johnson-Lindenstrauss transforms), the algorithm can verify and refine assignments at the end of the stream. The resulting space complexities are:
- SDL: $O(nr/\epsilon^2 + dk/\epsilon)$
- $k$-means: $O(n/\epsilon^2 + dk/\epsilon)$
These results show that the proposed algorithms are nearly tight with respect to the number of points $n$.
Sensitivity and Random Order Streams
The authors further explore how data distribution affects complexity. In "random-order" streams—where the rows of the data matrix arrive in a uniformly random sequence—the space requirements can be relaxed if the data has "bounded sensitivity" (meaning no single point disproportionately affects the total clustering cost). Under these conditions, the $1/\epsilon^2$ penalty in the space complexity can be reduced, achieving $\tilde{O}(n + dk/\epsilon)$ space.
Conclusion
This work provides a robust theoretical framework for SDL and streaming clustering. By bridging the gap between projective clustering and dictionary learning, the authors deliver the first PTAS for SDL. Additionally, the exploration of the assignment problem in turnstile streams establishes fundamental limits on space complexity while providing near-optimal algorithms for practical use. Future research may focus on removing assumptions regarding bit complexity and closing the remaining $\epsilon$ gap in streaming bounds.
Summary updated