Matrices are ubiquitous mathematical structures arising throughout computer science. We study fast algorithms for several central problems involving matrices, including eigenvalue approximation, spectral approximation, and low-rank approximation. In particular, we focus on \textit{sublinear time} or \textit{sublinear query} algorithms that can scale to very large matrices. Throughout this thesis, we focus on developing algorithms with theoretical bounds and demonstrate applicability of these algorithms on real world datasets. We first present a simple randomized algorithm for approximating \textit{all} the eigenvalues of a bounded entry matrix to small additive error by querying a small random submatrix of the input matrix. We next give the first sublinear query deterministic algorithms to \textit{spectrally} approximate a positive semidefinite (PSD) matrix $\mathbf{A}$ with entries drawn from the set $\{-1,0,1\}$ -- i.e., to output a matrix $\tilde{\mathbf{A}}$ such that the spectral norm of $\mathbf{A} - \tilde{\mathbf{A}}$ is small. Finally, we present a generalization to the Nystr\"{o}m method for low-rank approximations of general symmetric matrices. We comparatively study this generalized Nystr\"{o}m method and other sublinear algorithms to compute low-rank approximation of similarity matrices arising in natural language processing (NLP) tasks.
For the final thesis, we propose to extend our results on deterministic spectral approximation algorithms to a wider class of PSD matrices with entries in $\{-2,-1,0,1,2\}$. We further propose to empirically analyze eigenvalue approximation of symmetric matrices with sketching algorithms. Specifically, we plan to study sketching algorithms that use a sublinear number of matrix-vector products. This study will complement our work on algorithms that read a sublinear number of entries of the input matrix. We believe such a study will help us make progress on understanding eigenvalue approximation in both the sketching and sampling algorithmic regimes.
Advisor: Cameron Musco