# Sketch and shift: a robust decoder for compressive clustering

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 38 references that are in the map.
- First posted on arXiv 15 Dec 2023.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Kernel Mean Embedding of Distributions: A Review and Beyond](https://mlsanity.com/paper/1605.09522/) (2016)
- [DeepCore: A Comprehensive Library for Coreset Selection in Deep Learning](https://mlsanity.com/paper/2204.08499/) (2022)
- [A Tutorial on Kernel Density Estimation and Recent Advances](https://mlsanity.com/paper/1704.03924/) (2017)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [The Sliding Frank-Wolfe Algorithm and its Application to Super-Resolution Microscopy](https://mlsanity.com/paper/1811.06416/) (2018)
- [Sketching for Large-Scale Learning of Mixture Models](https://mlsanity.com/paper/1606.02838/) (2016)
- [Compressive Statistical Learning with Random Feature Moments](https://mlsanity.com/paper/1706.07180/) (2017)
- [Compressive K-means](https://mlsanity.com/paper/1610.08738/) (2016)
- [On Convergence of Epanechnikov Mean Shift](https://mlsanity.com/paper/1711.07441/) (2017)
- [Mean Nystr"om Embeddings for Adaptive Compressive Learning](https://mlsanity.com/paper/2110.10996/) (2021)
- [Convergence Analysis of Mean Shift](https://mlsanity.com/paper/2305.08463/) (2023)
- [Revisiting RIP guarantees for sketching operators on mixture models](https://mlsanity.com/paper/2312.05573/) (2023)
- [Blind Source Separation Using Mixtures of Alpha-Stable Distributions](https://mlsanity.com/paper/1711.04460/) (2017)
- [Recovery and convergence rate of the Frank-Wolfe Algorithm for the m-EXACT-SPARSE Problem](https://mlsanity.com/paper/1905.10443/) (2019)
- [Projected gradient descent for non-convex sparse spike estimation](https://mlsanity.com/paper/2005.05920/) (2020)
- [Compressive Clustering with an Optical Processing Unit](https://mlsanity.com/paper/2206.05928/) (2022)

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

- [Weighted quantization using MMD: From mean field to mean shift via gradient flows](https://mlsanity.com/paper/2502.10600/) (2025)

## Abstract (arXiv)

Compressive learning is an emerging approach to drastically reduce the memory footprint of large-scale learning, by first summarizing a large dataset into a low-dimensional sketch vector, and then decoding from this sketch the latent information needed for learning. In light of recent progress on information preservation guarantees for sketches based on random features, a major objective is to design easy-to-tune algorithms (called decoders) to robustly and efficiently extract this information. To address the underlying non-convex optimization problems, various heuristics have been proposed. In the case of compressive clustering, the standard heuristic is CL-OMPR, a variant of sliding Frank-Wolfe. Yet, CL-OMPR is hard to tune, and the examination of its robustness was overlooked. In this work, we undertake a scrutinized examination of CL-OMPR to circumvent its limitations. In particular, we show how this algorithm can fail to recover the clusters even in advantageous scenarios. To gain insight, we show how the deficiencies of this algorithm can be attributed to optimization difficulties related to the structure of a correlation function appearing at core steps of the algorithm. To address these limitations, we propose an alternative decoder offering substantial improvements over CL-OMPR. Its design is notably inspired from the mean shift algorithm, a classic approach to detect the local maxima of kernel density estimators. The proposed algorithm can extract clustering information from a sketch of the MNIST dataset that is 10 times smaller than previously.