Efficient Approximation of Structured Linear Operators using Randomized One-Sided Queries
Abstract
Approximating linear operators on high-dimensional spaces using only forward operator-vector product queries is a common but challenging task in scientific computing and machine learning arising when access to the adjoint action is experimentally unavailable or difficult to construct computationally. Existing query-efficient methods with polylogarithmic query complexity in the error tolerance rely on self-adjointness or access to the adjoint operator, while existing adjoint-free methods based on global low-order regularity have polynomial query complexity. We show that a priori local row-space information can be exploited for query-efficient, adjoint-free operator approximation, and that this information can be supplied by local high-order regularity estimates. Our approach first extends the fixed-sparsity matrix approximation algorithm of (Amsel et al., SIMAX, 2026) to approximating a matrix by one whose rows lie in prescribed subspaces, providing a general template for exploiting local row-space structure from forward queries alone. We then apply this framework to Hilbert-Schmidt integral operators with asymptotically smooth kernels. We establish asymptotic smoothness for Green's functions of canonical second-order elliptic PDEs in d≤ 3 dimensions including Poisson's equation in balls and constant coefficient equations on tori. In d spatial dimensions, our algorithm uses 𝒪(log(ε−1)logd(ε−1δ−1/2)) non-adaptive randomized queries to produce an ε-accurate approximation in Hilbert-Schmidt norm with probability 1−δ. This implies the error decreases as 𝒪( exp(− c q1/(d+1)) ) in the query count q, which we observe in numerical experiments using tens to hundreds of queries to approximate solution operators of one-dimensional variable-coefficient second-order elliptic equations.
Related
- Quantitative decomposition and approximation for quasi-local operators
- Linear-Time Bilevel Clipping operators for Structured Sparsity in Neural Networks
- Rotating-wave approximation for spin-boson models with structured fields
- Approximation Theory of Laplacian-Based Neural Operators for Reaction-Diffusion System
- Quantitative approximation theorem of neural operators for the Dirichlet-to-Neumann map
BibTeX
@misc{gallmeier2026efficient,
title = {{Efficient Approximation of Structured Linear Operators using Randomized One-Sided Queries}},
author = {Esther Gallmeier and Samuel E. Otto},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.07513},
eprint = {2610.07513},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.07513},
}
RIS
TY - UNPB
TI - Efficient Approximation of Structured Linear Operators using Randomized One-Sided Queries
AU - Esther Gallmeier
AU - Samuel E. Otto
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.07513
UR - https://arxiv.org/abs/2610.07513
AB - Approximating linear operators on high-dimensional spaces using only forward operator-vector product queries is a common but challenging task in scientific computing and machine learning arising when access to the adjoint action is experimentally unavailable or difficult to construct computationally. Existing query-efficient methods with polylogarithmic query complexity in the error tolerance rely on self-adjointness or access to the adjoint operator, while existing adjoint-free methods based on global low-order regularity have polynomial query complexity. We show that a priori local row-space information can be exploited for query-efficient, adjoint-free operator approximation, and that this information can be supplied by local high-order regularity estimates. Our approach first extends the fixed-sparsity matrix approximation algorithm of (Amsel et al., SIMAX, 2026) to approximating a matrix by one whose rows lie in prescribed subspaces, providing a general template for exploiting local row-space structure from forward queries alone. We then apply this framework to Hilbert-Schmidt integral operators with asymptotically smooth kernels. We establish asymptotic smoothness for Green's functions of canonical second-order elliptic PDEs in d≤ 3 dimensions including Poisson's equation in balls and constant coefficient equations on tori. In d spatial dimensions, our algorithm uses 𝒪(log(ε^−1)log^d(ε^−1δ^−1/2)) non-adaptive randomized queries to produce an ε-accurate approximation in Hilbert-Schmidt norm with probability 1−δ. This implies the error decreases as 𝒪( exp(− c q^1/(d+1)) ) in the query count q, which we observe in numerical experiments using tens to hundreds of queries to approximate solution operators of one-dimensional variable-coefficient second-order elliptic equations.
ER -