Turning big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering

By Dan Feldman, Melanie Schmidt, Christian Sohler. ACM-SIAM Symposium on Discrete Algorithms, 2013

591 citations recorded by the source corpus.

@d can be approximated up to (1 + e)-factor, for an arbitrary small e > 0, using the O(k/e2)-rank approximation of A and a constant. This implies, for example, that the optimal k-means clustering of the rows of A is (1 + e)-approximated by an optimal k-means clustering of their projection on the O(k/e2) first right singular vectors (principle components) of A. A (j, k)-coreset for projective clustering is a small set of points that yields a (1 + e)-approximation to the sum of squared distances from the n rows of A to any set of k affine subspaces, each of dimension at most j. Our embedding yields (0, k)-coresets of size O(k) for handling k-means queries, (j, 1)-coresets of size O(j) for PCA queries, and (j, k)-coresets of size (log n)O(jk) for any j, k ≥ 1 and constant e e (0, 1/2). Previous coresets usually have a size which is linearly or even exponentially dependent of d, which makes them useless when d ~ n. Using our coresets with the merge-and-reduce approach, we obtain embarrassingly parallel streaming algorithms for problems such as k-means, PCA and projective clustering. These algorithms use update time per point and memory that is polynomial in log n and only linear in d. For cost functions other than squared Euclidean distances we suggest a simple recursive coreset construction that produces coresets of size

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/ceb55d64d564dae512fa07c5cee5386dac083e4f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computational Theory and Mathematics

Citations in the corpus

Sketching as a Tool for Numerical Linear Algebra (2014, methodology): “ety of problems, such as Non-Negative Matrix Factorization (NNMF) [75], Latent Dirichlet Allocation (LDA) [16], and face recognition. It has also recently been used for ℓ2-error shape-ﬁtting problems [50], such as k-means and projective clustering. Here we demonstrate an application to latent semant”
k-Means for Streaming and Distributed Big Sparse Data (2015, background): “Coresets of size O(k/ε) that are based on projections on low-dimensional subspaces that diminishes the sparsity of the input data were recently suggested in [9] by improving the analysis in [14].”
Performance of Johnson-Lindenstrauss transform for k-means and k-medians clustering (2018, background): “The literature on data-dependent dimension reduction for k -means is ample [DFK + 99, Sar06, BDM09, BZD10, FSS13, BMI13, BZMD15, CEM + 15] and we refer the reader to [CEM + 15] for a comprehensive overview.”
Weighted low rank approximations with provable guarantees (2016, background): “Low rank approximation is arguably one of the most wellstudied problems in randomized numerical linear algebra, with diverse applications to clustering [19, 23, 38, 18], data mining [5], distance matrix completion [13], information retrieval [45], learning mixtures of distributions [2, 32], recommen”
Coreset-Based Neural Network Compression (2018, methodology): “Feldman et al. [12] demonstrate that this problem is equivalent to ﬁnding a low-rank approximation of the ﬁlter matrix.”
Training Mixture Models at Scale via Coresets (2017, methodology): “…subspace approximation (Feldman et al., 2006a; Mahoney and Drineas, 2009), (k,m)-segment mean (Feldman et al., 2012), PCA and projective clustering (Feldman et al., 2013b), distributed k-means and kmedian (Balcan et al., 2013), dictionary learning (Feldman et al., 2013a), k-segmentation of…”
Differentially private subspace clustering (2015, background): “…columns in X and Y. Differential privacy ensures the output distribution is obfuscated to the point that every user has a plausible deniability about being in the dataset, and in addition any inferences about individual user will have nearly the same confidence before and after the private release.”
Sparse Variational Inference: Bayesian Coresets from Scratch (2019, methodology): “of data known as a Bayesian coreset [30], a concept originating from the computational geometry and optimization literature [52–57].”
Improved Distributed Principal Component Analysis (2014, methodology): “tasks, such as k-means, Non-Negative Matrix Factorization (NNMF) (Lee and Seung, 2001) and Latent Dirichlet Allocation (LDA) (Blei et al., 2003). In the distributed model, approximate PCA was used by Feldman et al. (2013) for solving a number of shape ﬁtting problems such as k-means clustering, wher”
Communication-Optimal Distributed Clustering (2016, background): “which develops protocols for spectral clustering in the common message passing and blackboard models, and lower bounds are lacking as 2 well. For geometric clustering, while upper bounds exist (e.g., [3,4,10]), no provable lower bounds in either model existed, and our main contribution is to show th”
Coresets for Scalable Bayesian Logistic Regression (2016, background): “[1]), but then became popular in theoretical computer science as a way to efficiently solve clustering problems such as k-means and PCA (see [9, 11] and references therein).”
Automated Scalable Bayesian Inference via Hilbert Coresets (2017, background): “1The concept of a coreset originated in computational geometry and optimization (Agarwal et al., 2005; Feldman and Langberg, 2011; Feldman et al., 2013; Bachem et al., 2015; Lucic et al., 2016; Bachem et al., 2016; Feldman et al., 2011; Han et al., 2016).”