# Sketching for Large-Scale Learning of Mixture Models

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jun 2016.

## Built on by (most cited first, 14 of 14)

- [Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling](https://mlsanity.com/paper/2112.15199/) (2021)
- [Controlling Wasserstein Distances by Kernel Norms with Application to Compressive Statistical Learning](https://mlsanity.com/paper/2112.00423/) (2021)
- [Two-way kernel matrix puncturing: towards resource-efficient PCA and spectral clustering](https://mlsanity.com/paper/2102.12293/) (2021)
- [Mean Nystr"om Embeddings for Adaptive Compressive Learning](https://mlsanity.com/paper/2110.10996/) (2021)
- [FastPart: Over-Parameterized Stochastic Gradient Descent for Sparse optimisation on Measures](https://mlsanity.com/paper/2312.05993/) (2023)
- [Compressive Clustering with an Optical Processing Unit](https://mlsanity.com/paper/2206.05928/) (2022)
- [Sketch and shift: a robust decoder for compressive clustering](https://mlsanity.com/paper/2312.09940/) (2023)
- [Asymmetric compressive learning guarantees with applications to quantized sketches](https://mlsanity.com/paper/2104.10061/) (2021)
- [Learning primal-dual sparse kernel machines](https://mlsanity.com/paper/2108.12199/) (2021)
- [Fitting large mixture models using stochastic component selection](https://mlsanity.com/paper/2110.04776/) (2021)
- [Compressive Independent Component Analysis: Theory and Algorithms](https://mlsanity.com/paper/2110.08045/) (2021)
- [M2M: A general method to perform various data analysis tasks from a differentially private sketch](https://mlsanity.com/paper/2211.14062/) (2022)
- [Batch-less stochastic gradient descent for compressive learning of deep regularization for image denoising](https://mlsanity.com/paper/2310.03085/) (2023)
- [Compressive Meta-Learning](https://mlsanity.com/paper/2508.11090/) (2025)

## Abstract (arXiv)

Learning parameters from voluminous data can be prohibitive in terms of memory and computational requirements. We propose a "compressive learning" framework where we estimate model parameters from a sketch of the training data. This sketch is a collection of generalized moments of the underlying probability distribution of the data. It can be computed in a single pass on the training set, and is easily computable on streams or distributed datasets. The proposed framework shares similarities with compressive sensing, which aims at drastically reducing the dimension of high-dimensional signals while preserving the ability to reconstruct them. To perform the estimation task, we derive an iterative algorithm analogous to sparse reconstruction algorithms in the context of linear inverse problems. We exemplify our framework with the compressive estimation of a Gaussian Mixture Model (GMM), providing heuristics on the choice of the sketching procedure and theoretical guarantees of reconstruction. We experimentally show on synthetic data that the proposed algorithm yields results comparable to the classical Expectation-Maximization (EM) technique while requiring significantly less memory and fewer computations when the number of database elements is large. We further demonstrate the potential of the approach on real large-scale data (over 10 8 training samples) for the task of model-based speaker verification. Finally, we draw some connections between the proposed framework and approximate Hilbert space embedding of probability distributions using random features. We show that the proposed sketching operator can be seen as an innovative method to design translation-invariant kernels adapted to the analysis of GMMs. We also use this theoretical framework to derive information preservation guarantees, in the spirit of infinite-dimensional compressive sensing.