Cauchy-Lanczos Algorithm for Effective Dimension Reduction

The aim of dimension reduction techniques is to eliminate unnecessary information from extensive datasets, thereby enhancing the effectiveness of data analysis. Some linear dimension reduction techniques can be formulated using an appropriate pair of symmetric matrices. To identify the dimension of the signal subspace and distinguish between the signal and noise components of the data, one can employ the eigenvalue decomposition of a symmetric matrix. In this paper, we implement the Cauchy interlace theorem within the Lanczos algorithm to compute the eigenvalue decomposition of large symmetric matrices, which we refer to as the Cauchy-Lanczos algorithm (abbreviated as C-Lanczos algorithm). We demonstrate that this method can yield more accurate approximate eigenvalues and eigenvectors compared to the Lanczos algorithm, with only a minor increase in computational cost. Furthermore, we outline the convergence characteristics and provide an error analysis for the C-Lanczos algorithm. A series of experiments are also presented, illustrating the algorithm’s effectiveness in dimension reduction.