# Query Efficient Structured Matrix Learning

arXiv: https://arxiv.org/abs/2507.19290 · HTML: https://mlsanity.com/paper/2507.19290/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 33 of its 82 references that are in the map.
- First posted on arXiv 25 Jul 2025.

## Builds on (most cited first, 30 of 33)

- [PyHessian: Neural Networks Through the Lens of the Hessian](https://mlsanity.com/paper/1912.07145/) (2019)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [A Mathematical Guide to Operator Learning](https://mlsanity.com/paper/2312.14688/) (2023)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [Hutch++: Optimal Stochastic Trace Estimation](https://mlsanity.com/paper/2010.09649/) (2020)
- [Equilibrated adaptive learning rates for non-convex optimization](https://mlsanity.com/paper/1502.04390/) (2015)
- [Learning elliptic partial differential equations with randomized linear algebra](https://mlsanity.com/paper/2102.00491/) (2021)
- [Elliptic PDE learning is provably data-efficient](https://mlsanity.com/paper/2302.12888/) (2023)
- [Analysis of stochastic Lanczos quadrature for spectrum approximation](https://mlsanity.com/paper/2105.06595/) (2021)
- [Query lower bounds for log-concave sampling](https://mlsanity.com/paper/2304.02599/) (2023)
- [Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Law](https://mlsanity.com/paper/1804.01221/) (2018)
- [Optimal Sketching for Trace Estimation](https://mlsanity.com/paper/2111.00664/) (2021)
- [The gradient complexity of linear regression](https://mlsanity.com/paper/1911.02212/) (2019)
- [Sublinear Time Spectral Density Estimation](https://mlsanity.com/paper/2104.03461/) (2021)
- [Querying a Matrix through Matrix-Vector Products](https://mlsanity.com/paper/1906.05736/) (2019)
- [Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems](https://mlsanity.com/paper/2006.14015/) (2020)
- [Operator learning without the adjoint](https://mlsanity.com/paper/2401.17739/) (2024)
- [Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products](https://mlsanity.com/paper/2202.05120/) (2022)
- [Optimal query complexity for estimating the trace of a matrix](https://mlsanity.com/paper/1405.7112/) (2014)
- [Stochastic diagonal estimation: probabilistic bounds and an improved algorithm](https://mlsanity.com/paper/2201.10684/) (2022)
- [Optimal Query Complexities for Dynamic Trace Estimation](https://mlsanity.com/paper/2209.15219/) (2022)
- [A Tight Analysis of Hutchinson's Diagonal Estimator](https://mlsanity.com/paper/2208.03268/) (2022)
- [Operator learning for hyperbolic partial differential equations](https://mlsanity.com/paper/2312.17489/) (2023)
- [Sample Efficient Toeplitz Covariance Estimation](https://mlsanity.com/paper/1905.05643/) (2019)
- [On the Unreasonable Effectiveness of Single Vector Krylov Methods for Low-Rank Approximation](https://mlsanity.com/paper/2305.02535/) (2023)
- [Fixed-sparsity matrix approximation from matrix-vector products](https://mlsanity.com/paper/2402.09379/) (2024)
- [Sharper Bounds for Chebyshev Moment Matching, with Applications](https://mlsanity.com/paper/2408.12385/) (2024)
- [Improved Spectral Density Estimation via Explicit and Implicit Deflation](https://mlsanity.com/paper/2410.21690/) (2024)
- [Krylov Methods are (nearly) Optimal for Low-Rank Approximation](https://mlsanity.com/paper/2304.03191/) (2023)
- [Near-optimal hierarchical matrix approximation from matrix-vector products](https://mlsanity.com/paper/2407.04686/) (2024)

## Abstract (arXiv)

We study the problem of learning a structured approximation (low-rank, sparse, banded, etc.) to an unknown matrix A given access to matrix-vector product (matvec) queries of the form x rightarrow Ax and x rightarrow ATx. 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 A from any finite-sized family of matrices, F. Standard results from matrix sketching show that O(log|F|) matvec queries suffice in this setting. This bound can also be achieved, and is optimal, for vector-matrix-vector queries of the form x,yrightarrow xTAy, which have been widely studied in work on rank-1 matrix sensing. Surprisingly, we show that, in the matvec model, it is possible to obtain a nearly quadratic improvement in complexity, to tildeO(√log|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 can be learned with tildeO(√q) matvec queries, improving on an O(q) bound achievable via sketching techniques and vector-matrix-vector queries.