Lanczos Vectors versus Singular Vectors for Effective Dimension Reduction

作     者：Chen, Jie Saad, Yousef 

作者机构：Univ Minnesota Dept Comp Sci & Engn Minneapolis MN 55455 USA 

出 版 物：《IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING》 (IEEE Trans Knowl Data Eng)

年 卷 期：2009年第21卷第8期

页      面：1091-1103页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：US National Science Foundation [DMS-0810938, DMS 0528492] Minnesota Supercomputing Institute Direct For Mathematical & Physical Scien Division Of Mathematical Sciences Funding Source: National Science Foundation 

主　　题：Dimension reduction SVD Lanczos algorithm information retrieval latent semantic indexing face recognition PCA eigenfaces 

摘      要：This paper takes an in-depth look at a technique for computing filtered matrix-vector (mat-vec) products which are required in many data analysis applications. In these applications, the data matrix is multiplied by a vector and we wish to perform this product accurately in the space spanned by a few of the major singular vectors of the matrix. We examine the use of the Lanczos algorithm for this purpose. The goal of the method is identical with that of the truncated singular value decomposition (SVD), namely to preserve the quality of the resulting mat-vec product in the major singular directions of the matrix. The Lanczos-based approach achieves this goal by using a small number of Lanczos vectors, but it does not explicitly compute singular values/vectors of the matrix. The main advantage of the Lanczos-based technique is its low cost when compared with that of the truncated SVD. This advantage comes without sacrificing accuracy. The effectiveness of this approach is demonstrated on a few sample applications requiring dimension reduction, including information retrieval and face recognition. The proposed technique can be applied as a replacement to the truncated SVD technique whenever the problem can be formulated as a filtered mat-vec multiplication.