Sublinear Time Algorithms for Structured Matrices

With the rapid growth of large-scale data, it has become increasingly important to design algorithms that can process inputs efficiently without reading or storing them in full, motivating the design of sublinear algorithms. Matrices are a central abstraction in many such settings, arising in recommendation systems, signal and image processing, scientific computing, and modern machine learning. This thesis studies sublinear algorithms for two fundamental matrix problems, low-rank approximation and matrix-vector multiplication, by exploiting structure in important classes of matrices.

Toeplitz Low-Rank Approximation. The first part of the thesis studies Positive Semi Definite (PSD) Toeplitz matrices, a classical structured family that appears in stationary processes, signal processing, and related areas, and their low rank approximation. We show that although the best rank-$k$ approximation to a $n\times n$ PSD Toeplitz matrix need not itself be Toeplitz, there always exists a near-optimal low rank approximation that is itself Toeplitz. We also present sublinear query and sublinear time algorithms running in polynomial in $k$, $\log n$ time to recover such a good Toeplitz low rank approximation given entrywise access to the input matrix, using sparse Fourier recovery and leverage score sampling techniques.

Hankel Low-Rank Approximation. The next part of the thesis focuses on PSD Hankel matrices, which arise in system identification, signal processing, and approximation theory. Beckermann and Townsend showed that $n \times n$ PSD Hankel matrices always exhibit exponential eigenvalue decay and that for $k=O(\log n \log(1/\epsilon))$, the best rank $k$ approximation achieves an $\epsilon$-approximation. We show the existence of a rank $O(\log n \log(1/\epsilon))$ approximation that is itself Hankel and matches the error bound achieved by the best rank $k$ approximation. In addition, we show that the logarithmic dependence on $n$ and $1/\epsilon$ in $k$ is necessary for an $\epsilon$-approximation even without requiring the approximation to remain Hankel. Finally we design a robust sublinear time algorithm for recovering such a low-rank Hankel approximation from entrywise access to the input.

Kernel Matrix-Vector Multiplication. The final part of the thesis studies approximate matrix-vector multiplication for Gaussian kernel matrices, a basic primitive in statistics and machine learning with applications to fast attention in transformers. We introduce a structural model motivated by modern language models, under which the sum of entries of the kernel matrix scales linearly with $n$, and validate this assumption empirically on kernel matrices derived from modern transformer based large language models. Under this model and using techniques from locality-sensitive hashing and fast kernel density estimation, we give a randomized subquadratic-time algorithm for approximate matrix-vector multiplication that works for arbitrary input vectors.