Title: K-means Algorithm over Compressed Binary Data,
Abstract: We consider a network of binary-valued sensors with a fusion center. The
fusion center has to perform K-means clustering on the binary data transmitted
by the sensors. In order to reduce the amount of data transmitted within the
network, the sensors compress their data with a source coding scheme based on
binary sparse matrices. We propose to apply the K-means algorithm directly over
the compressed data without reconstructing the original sensors measurements,
in order to avoid potentially complex decoding operations. We provide
approximated expressions of the error probabilities of the K-means steps in the
compressed domain. From these expressions, we show that applying the K-means
algorithm in the compressed domain enables to recover the clusters of the
original domain. Monte Carlo simulations illustrate the accuracy of the
obtained approximated error probabilities, and show that the coding rate needed
to perform K-means clustering in the compressed domain is lower than the rate
needed to reconstruct all the measurements.