An iterative Jacobi-like algorithm to compute a few sparse approximate eigenvectors

In this paper, we describe a new algorithm that approximates the extreme eigenvalue/eigenvector pairs of a symmetric matrix. The proposed algorithm can be viewed as an extension of the Jacobi eigenvalue method for symmetric matrices diagonalization to the case where we want to approximate just a few extreme eigenvalues/eigenvectors. The method is also particularly well-suited for the computation of sparse approximations of the eigenvectors. In fact, we show that in general, our method provides a trade-off between the sparsity of the computed approximate eigenspaces and their accuracy. We provide theoretical results that show the linear convergence of the proposed method. Finally, we show experimental numerical results for sparse low-rank approximations of random symmetric matrices and show applications to graph Fourier transforms, and the sparse principal component analysis in image classification experiments. These applications are chosen because, in these cases, there is no need to perform the eigenvalue decomposition to high precision to achieve good numerical results.

Cristian Rusu · 2021