Sparse Embedded k-Means Clustering
The k-means clustering algorithm is a ubiquitous tool in data mining and machine learning that shows promising performance. However, its high computational cost has hindered its applications in broad domains. Researchers have successfully addressed these obstacles with dimensionality reduction methods. Recently, [1] develop a state-of-the-art random projection (RP) method for faster k-means clustering. Their method delivers many improvements over other dimensionality reduction methods. For example, compared to the advanced singular value decomposition based feature extraction approach, [1] reduce the running time by a factor of min{n, d} 2 log(d)/k for data matrix X ∈ R n×d with n data points and d features, while losing only a factor of one in approximation accuracy. Unfortunately, they still require O( ndk 2 log(d) ) for matrix multiplication and this cost will be prohibitive for large values of n and d. To break this bottleneck, we carefully build a sparse embedded k-means clustering algorithm which requires O(nnz(X)) (nnz(X) denotes the number of non-zeros in X) for fast matrix multiplication. Moreover, our proposed algorithm improves on [1]'s results for approximation accuracy by a factor of one. Our empirical studies corroborate our theoretical findings, and demonstrate that our approach is able to significantly accelerate k-means clustering, while achieving satisfactory clustering performance.
The authors proposed a sparse embedded k-means clustering algorithm to improve the running time of matrix multiplication of current proposed randomization projection method under sparse setting of data matrix in the literature. In particular, they demonstrated that their algorithms achieve the calculation time of matrix multiplication of order proportional to the number of non-zeroes entries of data matrix. 
I think the sparse embedded k-means clustering algorithm is rather interesting; however, it is not a very surprising improvement given the current results from the paper of C. Boutsidis et al. (2015). More specifically, both papers try to approximate low dimension solution for the original solution of K-means problem. To do that, C. Boutsidis et al. (2015) proposed to multiply the data matrix X with a random matrix having entries $1/\sqrt{d'}$ or $-1/\sqrt{d'}$ where $d'$ is the dimension of the approximation solution. However, their proposed solution does not work work well with sparse setting of data matrix as the calculation of matrix multiplication from their method greatly depends on the number of data points and the number of clusters. To account for that drawback, the authors of current paper proposed to multiply the data matrix with sparse random matrix inspired from diagonal Rademacher matrix. At the high level, it is unsurprisingly will improve the computation of matrix multiplication from C. Boutsidis et al.'s work under sparse setting of data matrix. At the setting of rather dense data matrix, I think both methods may differ slightly in terms of accuracy and matrix multiplication time. In summary, even though the paper is rather interesting, I think the contribution of the paper is not very surprising.
Some minor comments:
(1) Will the condition in Definition 2 hold for any matrix $D$?
(2) It may be better for readers if the authors replace notation $\widehat{D}$ in Lemma 1 with less confusing notation. At the moments, the notations in Lemma 1 look rather similar.
(3) I do not see the clustering accuracy with Random projection method from C. Boutsidis et al.'s work with RCV1 data in the experiment section. I wonder what may happen with that accuracy result?