Query Efficient Structured Matrix Learning
Noah Amsel, Pratyush Avi, Tyler Chen, Feyza Duman Keles, Chinmay Hegde, Christopher Musco, Cameron Musco, David Persson · 2025
Read Query Efficient Structured Matrix Learning by Noah Amsel, Pratyush Avi, Tyler Chen, Feyza Duman Keles, Chinmay Hegde, Christopher Musco, Cameron Musco, David Persson (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-19290.txt.
Introduction
Noah Amsel and co-authors study, in a 2025 paper, how few probes it takes to learn a structured copy of an unknown matrix. The only access allowed is multiplying the matrix, or its transpose, by chosen vectors. Such learning underlies fast solvers, preconditioners, and operator learning.
Earlier work handled specific families like low-rank matrices one at a time. This study tackles general finite families at once. Classic sketching needs a number of probes growing with the log of the family size, and that is achievable for weaker probes too. Surprisingly, the stronger two-sided probes studied here cannot always do better, the authors show, reshaping expectations for matrix learning.
Catalog record
| CREATOR | Noah Amsel, Pratyush Avi, Tyler Chen, Feyza Duman Keles, Chinmay Hegde, Christopher Musco, Cameron Musco, David Persson |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 131 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-19290
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Query Efficient Structured Matrix Learning Noah Amsel, Pratyush Avi, Tyler Chen, Feyza Duman Keles, Chinmay Hegde, Christopher Musco, Cameron Musco, David Persson Abstract We study the problem of learning a structured approximation (low-rank, sparse, banded, etc.) to an unknown matrix 𝐀 \bm{\mathbf{A}} given access to matrix-vector product (matvec) queries of the form 𝐱 → 𝐀𝐱 \bm{\mathbf{x}}\rightarrow\bm{\mathbf{A}}\bm{\mathbf{x}} and 𝐱 → 𝐀 𝖳 𝐱 \bm{\mathbf{x}}\rightarrow\bm{\mathbf{A}}^{\mathsf{T}}\bm{\mathbf{x}} . This problem is of central importance to algorithms across scientific computing and machine learning, with applications to fast multiplication and inversion for structured matrices, building preconditioners for first-order optimization, and as a model for differential operator learning. Prior work focuses on obtaining query complexity upper and lower bounds for learning specific structured matrix families that commonly arise in applications. We initiate the study of the problem in greater generality, aiming to understand the query complexity of learning approximations from general matrix families. Our main result focuses on finding a near-optimal approximation to 𝐀 \bm{\mathbf{A}} from any finite-sized family of matrices, ℱ \mathcal{F} . Standard results from matrix sketching show that O ( log | ℱ | ) O(\log|\mathcal{F}|) matvec queries suffice in this setting. This bound can also be achieved, and is optimal, for vector-matrix-vector queries of the form 𝐱 , 𝐲 → 𝐱 𝖳 𝐀𝐲 \bm{\mathbf{x}},\bm{\mathbf{y}}\rightarrow\bm{\mathbf{x}}^{\mathsf{T}}\bm{\mathbf{A}}\bm{\mathbf{y}} , which have been widely studied in work on rank- 1 1 matrix sensing. Surprisingly, we show that, in the matvec model, it is possible to obtain a nearly quadratic improvement in complexity, to O ~ ( log | ℱ | ) \tilde{O}(\sqrt{\log|\mathcal{F}|}) . Further, we prove that this bound is tight up to log-log factors. Via covering number arguments, our result extends to well-studied infinite families. As an example, we establish that a near-optimal approximation from any linear matrix family of dimension q q can be learned with O ~ ( q ) \tilde{O}(\sqrt{q}) matvec queries, improving on an O ( q ) O(q) bound achievable via sketching techniques and vector-matrix-vector queries. 1 Introduction What can we learn about an unknown matrix \bm{\mathbf{A}} from multiplying it by a few vectors? This basic question has been central to numerical linear algebra for decades, underlying work on Krylov subspace methods [ Saad, 2003 , Saad, 2011 ] , matrix sketching [ Woodruff, 2014 , Drineas and Mahoney, 2016 ] , randomized numerical linear algebra [ Weiße et al., 2006 , Martinsson and Tropp, 2020 ] , and more. In its most general form, the task is to interact with an n\times n matrix \bm{\mathbf{A}} in an adaptive way, issuing matrix-vector product queries (“matvec queries”) of the form: \displaystyle\bm{\mathbf{x}}\rightarrow\bm{\mathbf{A}}\bm{\mathbf{x}}\hskip 20.00003pt\text{or}\hskip 20.00003pt\bm{\mathbf{x}}\rightarrow\bm{\mathbf{A}}^{\mathsf{T}}\bm{\mathbf{x}}, where \bm{\mathbf{x}}\in\mathbb{R}^{n} can be chosen to be any vector. We consider the setting where we can issue multiple matvec queries \bm{\mathbf{x}}_{1},\ldots,\bm{\mathbf{x}}_{m} , and each \bm{\mathbf{x}}_{i} can be chosen adaptively depending on the results of the previous queries, \bm{\mathbf{x}}_{1},\ldots,\bm{\mathbf{x}}_{i-1} . Understanding the matvec query complexity of linear algebraic problems is critical in applications where \bm{\mathbf{A}} is only accessible as an implicit operator (algorithms that work in this setting are called “matrix-free”) or when the goal is to avoid explicit operations on the entries of \bm{\mathbf{A}} to take computational advantage of the natural parallelism of matrix-vector multiplication. In recent years, we have seen a flurry of success in proving better upper and lower bounds (often matching) on the matvec query complexity of central problems like linear system solving [ Braverman et al., 2020 ] , trace estimation [ Meyer et al., 2021 , Woodruff et al., 2022 , Epperly et al., 2024 , Chen et al., 2024 ] , eigenvalue estimation [ Simchowitz et al., 2018 , Chen et al., 2021 , Braverman et al., 2022 , Musco et al., 2025 , Bhattacharjee et al., 2025 ] , matrix function computation [ Chewi et al., 2024 ] , and much more [ Sun et al., 2019 , Meyer et al., 2025 ] . 1.1 Matrix Approximation One of the most important problems studied in the matvec query model is that of learning a near-optimal approximation to \bm{\mathbf{A}} from a given “hypothesis class” of structured matrices, \mathcal{F} . For example, \mathcal{F} could be all rank- k matrices or all tridiagonal matrices. We are interested in this problem in the agnostic learning setting, where \bm{\mathbf{A}} is not assumed to lie in \mathcal{F} , nor to be generated from some “true” matrix in \mathcal{F} , e.g., by adding i.i.d. noise. Formally, we consider: Problem 1 . For an unknown \bm{\mathbf{A}}\in\mathbb{R}^{n\times n} and a matrix family \mathcal{F}\subset\mathbb{R}^{n\times n} (a hypothesis class), find \bm{\mathbf{\tilde{B}}}\in\mathcal{F} satisfying \displaystyle\|\bm{\mathbf{A}}-\bm{\mathbf{\tilde{B}}}\|_{\mathsf{F}}\leq\gamma\cdot\inf_{\bm{\mathbf{B}}\in\mathcal{F}}\|\bm{\mathbf{A}}-\bm{\mathbf{B}}\|_{\mathsf{F}} for some approximation factor \gamma\geq 1 , using as few matvec queries to \bm{\mathbf{A}} and \bm{\mathbf{A}}^{\mathsf{T}} as possible. 1 1 1 We assume \bm{\mathbf{A}} is square for simplicity of notation. This is without loss of generality, since the rectangular case can always be handled by padding the smaller dimension with all zeros. In other words, our goal is to find an approximation, \bm{\mathbf{\tilde{B}}} , from the class \mathcal{F} that is competitive with the best possible approximation to \bm{\mathbf{A}} in \mathcal{F} . We measure error with respect to the Frobenius norm, which is a popular choice. However, other matrix norms have also been considered [ Kressner et al., 2019 , Musco and Musco, 2015 ] . The problem is interesting in several possible regimes for \gamma : when \gamma is close to 1 (i.e., \gamma=1+\epsilon for some small \epsilon ), when \gamma is a constant, or even when \gamma is allowed to grow slowly in n or other problem parameters [ Amsel et al., 2025b ] . 1 arises in dozens of applications where the goal is to efficiently obtain an explicit surrogate for an implicit operator. Examples include when \bm{\mathbf{A}} is the Hessian matrix of a large-scale optimization problem, for which matvecs can be computed much more efficiently than realizing the matrix [ Pearlmutter, 1994 , Dauphin et al., 2015 ] , when \bm{\mathbf{A}} is the inverse of another matrix and we wish to develop a fast solver [ Lin et al., 2011 , Martinsson, 2016 ] , and when \bm{\mathbf{A}} is the solution operator of a differential equation [ Boullé and Townsend, 2023 ] . For these applications, prior work studies query complexity for a wide variety of structured families, ranging from hierarchically structured matrices, to sparse matrices, to butterfly matrices, and more. 1 is also relevant when the goal is to replace an already explicit \bm{\mathbf{A}} with a structured surrogate that can be stored or operated on more efficiently. The matvec query model is relevant in this setting because, on modern hardware, matvecs are an inherently efficient way to access \bm{\mathbf{A}} . A familiar setting is when \mathcal{F} is the class of rank- k matrices for some parameter k . For this family, 1 captures the problem of finding a near-optimal rank- k approximation, for which the matvec query complexity has been studied extensively [ Musco and Musco, 2015 , Bakshi et al., 2022 , Bakshi and Narayanan, 2023 , Meyer et al., 2024 ] . We provide a more detailed summary of the large and growing body of related work on structured matrix approximation in the matvec query model in Section 1.3 . Importantly, essentially all prior work on the