In Latent Semantic Indexing (LSI), a collection of documents is often pre-processed to form a sparse term-document matrix, followed by a computation of a low-rank approximation to the data matrix. A multilevel framework based on hypergraph coarsening is presented which exploits the hypergraph that is canonically associated with the sparse term-document matrix representing the data. The main goal is to reduce the cost of the matrix approximation without sacrificing accuracy. Because coarsening by multilevel hypergraph techniques is a form of clustering, the proposed approach can be regarded as a hybrid of factorization-based LSI and clustering-based LSI. Experimental results indicate that our method achieves good improvement of the retrieval performance at a reduced cost

In the past decade, a number of nonlinear dimensionality reduction methods using an affinity graph have been developed for manifold learning. This paper explores a multilevel framework with the goal of reducing the cost of unsupervised manifold learning and preserving the embedding quality at the same time. An application to spectral clustering is also presented. Experimental results indicate that our multilevel approach is an appealing alternative to standard techniques.

A method is presented to partition a given set of data entries embedded in Euclidean space by recursively bisecting clusters into smaller ones. The initial set is subdivided into two subsets whose centroids are farthest from each other, and the process is repeated recursively on each subset. An approximate algorithm is proposed to solve the original integer programming problem which is NP-hard. Experimental evidence shows that the clustering method often outperforms a standard spectral clustering method, albeit at a slightly higher computational cost. The paper also discusses improvements of the standard K-means algorithm. Specifically, the clustering quality resulting from the K-means technique can be significantly enhanced by using the proposed algorithm for its initialization.

Dimension reduction techniques have been successfully applied to face recognition and text information retrieval. The process can be time-consuming when the data set is large. This paper presents a multilevel framework to reduce the size of the data set, prior to performing dimension reduction. The algorithm exploits nearest-neighbor graphs. It recursively coarsens the data by finding a maximal matching level by level. The coarsened data at the lowest level is then projected using a known linear dimensionality reduction method. The same linear mapping is performed on the original data set, and on any new test data. The methods are illustrated on two applications: Eigenfaces (face recognition) and Latent Semantic Indexing (text mining). Experimental results indicate that the multilevel techniques proposed here offer a very appealing cost to quality ratio. 1