Efficient Approximation of Structured Linear Operators using Randomized One-Sided Queries

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\le 3$ dimensions including Poisson’s equation in balls and constant coefficient equations on tori. In $d$ spatial dimensions, our algorithm uses $\mathcal{O}(\log ({\epsilon }^{-1}){\log }^d({\epsilon }^{-1}{\delta }^{-1\mathrm{/}2}))$ non-adaptive randomized queries to produce an $\epsilon$-accurate approximation in Hilbert-Schmidt norm with probability $1-\delta$. This implies the error decreases as $\mathcal{O}(\exp (-c{q}^{1\mathrm{/}(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.