A Single-Pass Algorithm for Efficiently Recovering Sparse Cluster Centers of High-dimensional Data

Learning a statistical model for high-dimensional data is an important topic in machine learning. Although this problem has been well studied in the supervised setting, little is known about its unsupervised counterpart. In this work, we focus on the problem of clustering high-dimensional data with sparse centers. In particular, we ad-dress the following open question in unsuper-vised learning: “is it possible to reliably clus-ter high-dimensional data when the number of samples is smaller than the data dimensionali-ty? ” We develop an efficient clustering algorith-m that is able to estimate sparse cluster centers with a single pass over the data. Our theoreti-cal analysis shows that the proposed algorithm is able to accurately recover cluster centers with only O(s log d) number of samples (data points), provided all the cluster centers are s-sparse vec-tors in a d dimensional space. Experimental re-sults verify both the effectiveness and efficiency of the proposed clustering algorithm compared to the state-of-the-art algorithms on several bench-mark datasets