PhD Thesis 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 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. We also show how to approximate eigenvectors based on similar random sampling based techniques. Finally, we 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. The first method we present combines a Chebyshev polynomial moment matching method with a deflation step that approximately projects off the largest magnitude eigendirections of the matrix. 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 same optimal query complexity bound.
Advisor:
Cameron Musco