Spectral Methods: Algorithms and Applications

Yale University, New Haven CT

Investigators

Abstract

Abstract -------- Problems in many areas where the input data is a matrix have been tackled by Spectral Methods which use low-rank approximations to the input matrix. In the important application area of Clustering, only known proofs that the methods succeed have to make the unrealistic assumption that all entries of the matrix are statistically independent. This research removes this important impediment to the wider use of the method by developing the theory and algorithms that work under limited independence, a much more realistic assumption. To illustrate, in one example - document-term matrices - this research assumes only that the documents are statistically independent, not the terms in each document. The research also generalize the methods developed for limited independence to deal with matrix-valued random variables which are of interest in several areas and to date have no substantial work on them. The PI and supported students will extend the applications of spectral-like methods to tensors - multi-dimensional arrays. It is expected that the research here will be one of the key bridges between theory and practice in this area, thus leading to a broad transfer of theoretical developments into practice in time.