Random Matrices and Spectral Clustering Abstract

Theoretical analysis of Spectral Clustering is often based on the theory of random matrices which assumes that all entries of the data matrix (with each row representing a data object) are independent random variables. In practice, however, while the objects may be independent of each other, features of an object are not independent. To address this, we will prove bounds on the singular values of a matrix assuming only that its rows are independent vector-valued random variables (the columns may not be independent) and describe a new clustering algorithm with this limited independence.

In the second part, we address a more theoretical question. We will show a generalization of Azuma’s (martingale) inequality to the case when the random variables are matrices and more generally infinite-dimensional operators.

The first part is joint work with A. Dasgupta, J. Hopcroft and P. Mitra.