Using the left Gram matrix to cluster high dimensional data
This provides a computationally efficient solution for clustering high-dimensional data, such as in genomics, without requiring dimension reduction or parameter specification.
The authors tackled the problem of clustering high-dimensional data (P >> N) by proposing an algorithm based on the normalized left Gram matrix, which avoids preprocessing and hyperparameter tuning. The algorithm outperformed 14 other methods on 32 benchmark datasets, achieving the most accurate cluster estimates more than twice as often as its closest competitors.
For high dimensional data, where P features for N objects (P >> N) are represented in an NxP matrix X, we describe a clustering algorithm based on the normalized left Gram matrix, G = XX'/P. Under certain regularity conditions, the rows in G that correspond to objects in the same cluster converge to the same mean vector. By clustering on the row means, the algorithm does not require preprocessing by dimension reduction or feature selection techniques and does not require specification of tuning or hyperparameter values. Because it is based on the NxN matrix G, it has a lower computational cost than many methods based on clustering the feature matrix X. When compared to 14 other clustering algorithms applied to 32 benchmarked microarray datasets, the proposed algorithm provided the most accurate estimate of the underlying cluster configuration more than twice as often as its closest competitors.