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.
Type de document :
Communication dans un congrès
Asilomar Conference on Signals, Systems, and Computers, Oct 2017, Pacific Grove, California, United States. Proceedings of the Asilomar Conference on Signals, Systems, and Computers
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01650160
Contributeur : Rémi Gribonval <>
Soumis le : mardi 28 novembre 2017 - 11:53:12
Dernière modification le : mercredi 16 mai 2018 - 11:24:14

Fichier

Asilomar17.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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. Proceedings of the Asilomar Conference on Signals, Systems, and Computers. 〈hal-01650160〉

Partager

Métriques

Consultations de la notice

678

Téléchargements de fichiers

97