Scalable graph-based clustering with nonnegative relaxation for large hyperspectral image

Hyperspectral image (HSI) clustering is very important in remote sensing applications. However, most graph-based clustering models are not suitable for dealing with large HSI due to their computational bottlenecks: the construction of the similarity matrix W, the eigenvalue decomposition of the graph Laplacian matrix L, and k-means or other discretization procedures. To solve this problem, we propose a novel approach, scalable graph-based clustering with nonnegative relaxation (SGCNR), to cluster the large HSI. The proposed SGCNR algorithm first constructs an anchor graph and then adds the nonnegative relaxation term. With this, the computational complexity can be reduced to O(nd\log m+nK²+nKc+K³), compared with traditional graph-based clustering algorithms that need at least O(n²d+n²K) or O(n²d+n³), where n, d, m, K, and c are, respectively, the number of samples, features, anchors, classes, and nearest neighbors. In addition, the SGCNR algorithm can directly obtain the clustering indicators, without resort to k-means or other discretization procedures as traditional graph-based clustering algorithms have to do. Experimental results on several HSI data sets have demonstrated the efficiency and effectiveness of the proposed SGCNR algorithm.