Sketched Clustering via Hybrid Approximate Message Passing

Evan Byrne (1) , Rémi Gribonval (2) , Philip Schniter (1)

1 OSU - Ohio State University [Columbus]
2 PANAMA - Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio

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.

Domaines: Traitement du signal et de l'image [eess.SP]

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⟩