Matrix–vector algorithms, particularly Krylov subspace methods, are widely viewed as the most effective algorithms for solving large systems of linear equations. This paper establishes lower bounds on the worst-case number of matrix–vector products needed by such an algorithm to approximately solve a general linear system. The first main result is that, for any matrix–vector algorithm which is allowed the use of randomization and can perform products with both a matrix and its transpose, $\Omega(\kappa \log(1/\varepsilon))$ matrix–vector products are necessary to solve a linear system with condition number $\kappa$ to accuracy $\varepsilon$, matching an upper bound for conjugate gradient on the normal equations. The second main result is that one-sided algorithms, which lack access to the transpose, must use $n$ matrix–vector products to solve an $n \times n$ linear system, even when the problem is perfectly conditioned. Both main results include explicit constants that match known upper bounds up to a factor of four. These results rigorously demonstrate the limitations of matrix–vector algorithms and confirm the optimality of widely used Krylov subspace algorithms.

We study the problem of computing a rank-\(k\) approximation of a matrix using randomized block Krylov iteration. Prior work has shown that, for block size \(b = 1\) or \(b = k\), a \((1+\varepsilon)\)-factor approximation to the best rank-\(k\) approximation can be obtained after \(\tilde{O}(k/\sqrt{\varepsilon})\) matrix-vector products with the target matrix. On the other hand, when \(b\) is between \(1\) and \(k\), the best known bound on the number of matrix-vector products scales with \(b(k-b)\), which could be as large as \(O(k^2)\). Nevertheless, in practice, the performance of block Krylov methods is often optimized by choosing a block size \(1 \ll b \ll k\). We address this theory-practice gap by proving that randomized block Krylov iteration produces a \((1+\varepsilon)\)-factor approximate rank-\(k\) approximation using \(\tilde{O}(k/\sqrt{\varepsilon})\) matrix-vector products for any block size \(1 \le b \le k\). Our analysis relies on new bounds for the minimum singular value of a random block Krylov matrix, which may be of independent interest. Similar bounds are central to recent breakthroughs on faster algorithms for sparse linear systems [Peng & Vempala 2021; SODA 2021; Nie, STOC 2022].

Subspace-based signal processing techniques, such as the Estimation of Signal Parameters via Rotational Invariant Techniques (ESPRIT) algorithm, are popular methods for spectral estimation. These algorithms can achieve the so-called super-resolution scaling under low noise conditions, surpassing the well-known Nyquist limit. However, the performance of these algorithms under high-noise conditions is not as well understood. Existing state-of-the-art analysis indicates that ESPRIT and related algorithms can be resilient even for signals where each observation is corrupted by statistically independent, mean-zero noise of size$\mathcal{O}(1)$, but these analyses only show that the error$\epsilon$decays at a slow rate$\epsilon=\widetilde{\mathcal{O}}(n^{-1/2})$with respect to the cutoff frequency$n$(i.e., the maximum frequency of the measurements). In this work, we prove that under certain assumptions, the ESPRIT algorithm can attain a significantly improved error scaling$\epsilon=\widetilde{\mathcal{O}}(n^{-3/2})$, exhibiting noisy super-resolution scaling beyond the Nyquist limit$\epsilon=\mathcal{O}(n^{-1})$given by the Nyquist-Shannon sampling theorem. We further establish a theoretical lower bound and show that this scaling is optimal. Our analysis introduces novel matrix perturbation results, which could be of independent interest.

This paper presents new quadrature rules for functions in a reproducing kernel Hilbert space using nodes drawn by a sampling algorithm known as randomly pivoted Cholesky. The resulting computational procedure compares favorably to previous kernel quadrature methods, which either achieve low accuracy or require solving a computationally challenging sampling problem. Theoretical and numerical results show that randomly pivoted Cholesky is fast and achieves comparable quadrature error rates to more computationally expensive quadrature schemes based on continuous volume sampling, thinning, and recombination. Randomly pivoted Cholesky is easily adapted to complicated geometries with arbitrary kernels, unlocking new potential for kernel quadrature.