PhD Dissertation Proposal Defense: Rajarshi Bhattacharjee, Query Efficient Algorithms for Matrix Spectrum Approximation
Content
Speaker
Abstract
Approximating the eigenvalues and eigenvectors of a matrix is a core problem in numerical linear algebra, underpinning a wide range of applications in scientific computing, machine learning, and data science. The rapid growth of data has pushed traditional algorithms for these tasks to their computational limits. This thesis develops and analyzes algorithms for several key problems related to eigenvalue and eigenvector estimation, with a central focus on \textit{query-efficient methods} that minimize access to the input matrix and scale to large matrices.
The first matrix access model we consider is the entrywise query model. Here, the query complexity is measured as the number of individual entries of the input matrix that an algorithm reads. Our first contribution in this model is an algorithm that approximates all eigenvalues to within a prescribed additive error by randomly sampling a small principal submatrix. For future work, we propose to study how to approximate eigenvectors based on similar random sampling based techniques. We also study deterministic algorithms for
matrix sparsification in this model, which select only a small subset of entries from the matrix while preserving spectral information.
The second matrix access model we consider is the matrix–vector query model, where the input matrix is accessed only through matrix–vector products. The query complexity is measured as the number of such matrix-vector products used by an algorithm. In this model, we design fast algorithms for spectral density estimation by leveraging eigenvalue
deflation. Our analysis significantly improves on the error bounds of prior work in the natural case that the matrix has eigenvalue decay, without sacrificing query complexity. We also show that the popular Stochastic Lanczos Quadrature (SLQ) algorithm nearly achieves the optimal query complexity bound. Though the version of SLQ we analyze uses a single starting vector, another version of SLQ with a starting block often outperforms the single vector version in practice. Thus, in future work, we also propose to study the effectiveness of block SLQ over single vector SLQ for spectral density estimation.