Performance-complexity trade-off in large dimensional spectral clustering

The big data revolution comes along with the challenging need to parse, mine, compress large amount of large dimensional data. Many modern machine learning algorithms (including state-of-the-art deep neural networks) are designed to work with compressed, quantized, or even binarized data/features so that they can run on low-power IoT devices.In this talk, we will focus on the theoretical analysis of spectral clustering method that aims to find possible clusters from a given data matrix in an unsupervised manner, by exploring the informative eigenstructure (e.g., the dominant eigenvector) of the data matrix. Random matrix analysis reveals the surprising fact that very little change occurs in the informative eigenstructure even under drastic sparsification and/or quantization, and consequently that very little downstream performance loss occurs with very aggressively uniformed and non-uniformed, sparsified and/or quantized spectral clustering. The present study is based on a spiked model analysis of nonlinear random matrices and may be of independent research interest. We expect that our analysis opens the door to improved analysis of computationally efficient methods for large dimensional machine learning and neural network models more generally.