Skip to Main content Skip to Navigation
Journal articles

Sketched Clustering via Hybrid Approximate Message Passing

Evan Byrne 1 Antoine Chatalic 2 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, a dataset of T samples is first sketched down to a vector of modest size, from which the centroids are subsequently extracted. Its advantages include 1) reduced storage complexity and 2) centroid extraction complexity independent of T. For the sketching methodology recently proposed by Keriven et al., which can be interpreted as a random sampling of the empirical characteristic function, we propose a sketched clustering algorithm based on approximate message passing. Numerical experiments suggest that our approach is more efficient than the state-of-the-art sketched clustering algorithm “CL-OMPR” (in both computational and sample complexity) and more efficient than k-means++ when T is large.
Complete list of metadata

Cited literature [33 references]  Display  Hide  Download

https://hal.inria.fr/hal-01991231
Contributor : Antoine Chatalic Connect in order to contact the contributor
Submitted on : Friday, July 5, 2019 - 9:53:46 AM
Last modification on : Friday, April 8, 2022 - 4:04:02 PM

File

sc.pdf
Files produced by the author(s)

Identifiers

Citation

Evan Byrne, Antoine Chatalic, Rémi Gribonval, Philip Schniter. Sketched Clustering via Hybrid Approximate Message Passing. IEEE Transactions on Signal Processing, Institute of Electrical and Electronics Engineers, 2019, 67 (17), pp.4556-4569. ⟨10.1109/TSP.2019.2924585⟩. ⟨hal-01991231v2⟩

Share

Metrics

Record views

236

Files downloads

131