Skip to Main content Skip to Navigation
Conference papers

Sketched Clustering via Hybrid Approximate Message Passing

Evan Byrne 1 Rémi Gribonval 2 Philip Schniter 1
2 PANAMA - Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio
Inria Rennes – Bretagne Atlantique , IRISA-D5 - SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE
Abstract : In sketched clustering, the dataset is first sketched down to a vector of modest size, from which the cluster centers are subsequently extracted. The goal is to perform clustering more efficiently than with methods that operate on the full training data, such as k-means++. For the sketching methodology recently proposed by Keriven, Gribonval, et al., which can be interpreted as a random sampling of the empirical characteristic function, we propose a cluster recovery algorithm based on simplified hybrid generalized approximate message passing (SHyGAMP). Numerical experiments suggest that our approach is more efficient than the state-of-the-art sketched clustering algorithms (in both computational and sample complexity) and more efficient than k-means++ in certain regimes.
Document type :
Conference papers
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-01650160
Contributor : Rémi Gribonval <>
Submitted on : Tuesday, November 28, 2017 - 11:53:12 AM
Last modification on : Thursday, January 7, 2021 - 4:34:26 PM

File

Asilomar17.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01650160, version 1

Citation

Evan Byrne, Rémi Gribonval, Philip Schniter. Sketched Clustering via Hybrid Approximate Message Passing. Asilomar Conference on Signals, Systems, and Computers, Oct 2017, Pacific Grove, California, United States. ⟨hal-01650160⟩

Share

Metrics

Record views

1436

Files downloads

318