A class of multistep sparse matrix strategies for concept decomposition matrix approximation

ABSTRACT

In information retrieval, text documents are usually modeled as a term-document matrix which has high dimensional and space vectors. To reduce the high dimensions, one of the various dimensionality reduction methods, concept decomposition, has been developed by [3]. This method is based on document clustering techniques and least-square matrix approximation to approximate the matrix of vectors. Gao and Zhang [4] have indicated that the retrieval accuracy from the concept decomposition can be comparable to that from Latent Semantic Indexing. However the numerical computation is expensive. In this paper we presented a class of multistep spare matrix strategies for concept decomposition matrix approximation. In this approach, a series of simple sparse matrices are used to approximate the decompositions. Our numerical experiments show the advantage of such an approach in terms of storage costs and query time compared with other approaches while maintaining comparable retrieval quality.

REFERENCES

• 1: Chung-Min Chen , Ned Stoffel , Mike Post , Chumki Basu , Devasis Bassu , Clifford Behrens, Telcordia LSI Engine: Implementation and Scalability Issues, Proceedings of the 11th International Workshop on research Issues in Data Engineering, p.51, April 01-02, 2001
• 2: Edmond Chow, A Priori Sparsity Patterns for Parallel Sparse Approximate Inverse Preconditioners, SIAM Journal on Scientific Computing, v.21 n.5, p.1804-1822, April 2000 [doi>10.1137/S106482759833913X]
• 3: Inderjit S. Dhillon , Dharmendra S. Modha, Concept decompositions for large sparse text data using clustering, Machine Learning, v.42 n.1/2, p.143-175, Jan. 2001 [doi>10.1023/A:1007612920971]
• 4: J. Gao and J. Zhang. Text retrieval using sparsified concept decomposition matrix. Book Chapter of Computational and Information Science, vol. 3314, pp. 523--529, 2005
• 5: A. Kontostathis, W. M. Pottenger, and B. D. Davison. Identifcation of critical values in Latent Semantic Indexing (LSI). Book chapter of Foundations of Data Mining and Knowledge Discovery, pp.333--346, 2005.
• 6: Kai Wang , Jun Zhang, MSP: A Class of Parallel Multistep Successive Sparse Approximate Inverse Preconditioning Strategies, SIAM Journal on Scientific Computing, v.24 n.4, p.1141-1156, 2002 [doi>10.1137/S1064827502400832]
• 7: C. Shen and D. Williams. Approximate Matrix Decomposition Technniques in Information Retrieval, In Proceedings of World Congress on Engineering and Computer Science 2007, pp. 347--352, 2007.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

Keywords:
concept decomposition matrix, least-squares, multistep, sparse matrix approximation, term-document matrix