PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Esther Gallmeier, Samuel E. Otto

arXiv:2610.07513v1math.NAcs.NA

TL;DR

Forward-only operator approximation is challenging when adjoint access is unavailable, and existing query-efficient methods rely on self-adjointness or adjoint queries. This paper exploits a priori local row spaces, supplied by kernel regularity, to approximate structured operators from randomized forward queries. For asymptotically smooth integral operators, it establishes Hilbert-Schmidt error guarantees with stretched-exponential decay in the query budget.

  • Problem

    Query-efficient approximation of non-self-adjoint operators is limited when only forward queries are available and constructing or querying the adjoint is difficult.

    Source: §1 · pp. 3, 5

  • Method

    The paper extends randomized matrix approximation to prescribed row subspaces and uses asymptotic smoothness to construct local row spaces for discretized integral operators.

    Source: §1 · p. 4, §1.1 · p. 6

  • Results

    The resulting adjoint-free algorithm has Hilbert-Schmidt error guarantees with stretched-exponential decay in query count, and the paper reports numerical evidence for one-dimensional non-self-adjoint elliptic solution operators.

    Source: §5 · p. 61

  • Takeaways & Limitations

    A priori local row-space information can make adjoint-free operator approximation query-efficient, and local high-order regularity can supply that information.

    Source: §1 · p. 5, §5 · p. 61

    Asymptotic smoothness is a sufficient assumption rather than an essential one, and establishing it for broader non-self-adjoint and variable-coefficient elliptic operators remains future work.

    Source: §5 · p. 62

Abstract

from arXiv · show

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

1 Introduction

Forward-only operator approximation matters when adjoints are unavailable, but existing query-efficient methods rely on self-adjointness or adjoint access. The paper uses a priori local row spaces, supplied by kernel regularity, to extend randomized matrix approximation to Hilbert-Schmidt integral operators.

1 Introduction

  • The paper targets non-self-adjoint Hilbert-Schmidt operators accessible only through forward queries, a setting arising when constructing or querying an adjoint is difficult.Such operator approximations serve as surrogates in inverse problems, design optimization, and solver acceleration.Source: §1 · p. 3

1.1 Our Contributions and Roadmap

  • The paper generalizes fixed-sparsity approximation to matrices whose rows lie in prescribed low-dimensional subspaces, using forward queries alone.This extends the algorithm in [16]; localized kernel information can supply the row spaces after discretization.Source: §1 · p. 4, §1.1 · p. 6

1 Introduction

  • Existing query-efficient approaches for elliptic solution operators rely on self-adjointness or queries to the adjoint, while global regularity approaches yield algebraic rates.The cited methods use sparse Cholesky or randomized SVD, and their non-self-adjoint extensions require adjoint access.Source: §1 · pp. 4–5

1.1 Our Contributions and Roadmap

  • Asymptotically smooth kernels yield exponentially accurate polynomial approximations on admissible domains and low-dimensional subspaces for discretized operator rows.The paper verifies this regularity for Poisson Green functions on unit balls in dimensions 1–3 and constant-coefficient elliptic operators on flat tori under stated assumptions.Source: §1 · p. 5, §1.1 · p. 6
  • Algorithm 2 projects the operator onto a finite-element space, constructs local row subspaces, and applies Algorithm 1 for an ε-accurate Hilbert-Schmidt approximation with probability at least 1 − δ.The row-subspace dimension is O(log^(d+1)(ε^-1)) for spatial dimension d.Source: §1.1 · p. 6

2 Adjoint-Free Matrix Approximation in Fixed Row Subspaces

The section generalizes fixed-sparsity matrix approximation to prescribed row subspaces. Gaussian forward queries and row-wise least squares approximate the best row-wise projection, with query cost governed by the subspace dimension and approximation tolerance.

2 Adjoint-Free Matrix Approximation in Fixed Row Subspaces

  • The target is the matrix formed by orthogonally projecting each row of A onto its prescribed subspace, which is the nearest feasible matrix in Frobenius norm.The algorithm approximates this row-wise projection using only forward matrix-vector products.Source: §2 · pp. 6–7
  • For row subspaces of dimension at most k, O(k/ε) non-adaptive Gaussian matrix-vector queries suffice in expectation for a near-optimal approximation.The approximation is compared with the best matrix whose rows lie in the prescribed subspaces.Source: §2 · pp. 7, 9
  • The algorithm forms Gaussian sketches Z = AG and solves independent row-wise least-squares problems to estimate each row’s coefficients in its prescribed subspace.The resulting rows are assembled from the estimated coefficients and the subspace bases.Source: §2 · p. 7
  • The prescribed subspaces generalize fixed sparsity, which is recovered when each subspace is spanned by known canonical basis vectors.The framework requires a priori row-space information, not coordinate sparsity itself.Source: §2 · p. 7
  • Increasing subspace dimensions can reduce row residuals but raises the query requirement, so accurate low-dimensional row spaces are essential for query efficiency.The varying row spaces mean the resulting approximation need not be low-rank, even when local slices admit exponentially convergent approximations.Source: §2 · pp. 9–10

3 Approximating Asymptotically Smooth Integral Operators

This section uses forward queries and local row-space structure to approximate asymptotically smooth integral operators in Hilbert-Schmidt norm, stating a query-efficiency guarantee. It establishes L2-asymptotic smoothness for Green functions of Poisson and constant-coefficient elliptic operators on a flat torus, including unit-ball Poisson Green functions in dimensions 2 and 3, and examines approximation errors in one-dimensional numerical examples.

3 Approximating Asymptotically Smooth Integral Operators

  • For possibly non-self-adjoint operators with off-diagonal smoothness on a bounded domain, Algorithm 2 achieves ε-accurate Hilbert-Schmidt approximation using only polylogarithmically many forward queries in ε⁻¹, implying stretched-exponential convergence in query count.The operators may have algebraic singular-value decay, and the algorithm does not access adjoint queries.Source: §3 · pp. 10, 15
  • The algorithm discretizes the operator with piecewise-constant finite elements, builds low-dimensional row subspaces from local polynomial approximations on hierarchical partitions, and recovers the approximation using Gaussian forward queries.The rowwise matrix-recovery step produces an approximation whose rows lie in the prescribed subspaces.Source: §3 · pp. 11–12

3.1 Discussion on Asymptotic Smoothness

  • The paper formulates asymptotic smoothness in L2 by bounding separated-domain derivative norms against kernel norms on enlarged neighborhoods, aligning the condition with Hilbert-Schmidt error analysis and interior elliptic regularity.The condition captures off-diagonal smoothing while permitting low-regularity or singular behavior on the diagonal.Source: §3.1 · p. 17

3.1.1 Green’s Functions for Poisson Equation

  • The Dirichlet Poisson Green functions on the unit ball are L2-asymptotically smooth in dimensions 2 and 3.The verification uses smoothness away from the Green function’s singularities on separated domains.Source: §3.1.1 · pp. 17–18
  • The Poisson Green function is L2-asymptotically smooth; for d ≥4 it remains smooth off the diagonal but is not globally square-integrable.Source: §3.1.1 · p. 20

3.1.2 Green’s Functions for Constant-Coefficient Elliptic Operators on a Flat Torus

  • For d ≤3, under the stated Green-function assumptions, constant-coefficient elliptic operators on a flat torus have kernels L2-asymptotically smooth in y.Higher-order Caccioppoli estimates, iterated over nested domains, bound derivatives of harmonic functions with analytic growth; the argument assumes standard off-diagonal Green-function properties.Source: §3.1.2 · pp. 22, 24

3.2 Numerical Examples

  • Observed errors follow root-exponential decay in the constant-coefficient test; variable tests show slower convergence with higher ellipticity ratios or advection, but little sensitivity to coefficient regularity.At stronger advection, error plateaus align with ranges where the rounded polynomial degree remains unchanged; the nondifferentiable coefficient converges comparably to polynomial, entire, and analytic examples.Source: Figure 2 · p. 25, Figure 3 · p. 26, §3.2 · pp. 27–28

4 Proof of Main Theorem 2

Section 4 proves Theorem 2 by developing row-wise approximation spaces for the rows of A_h, using finite-element discretization, local polynomial approximation, and hierarchical η-admissible decompositions. It then applies the randomized row-space approximation algorithm and combines its error with the row-wise estimate.

4 Proof of Main Theorem 2

  • The operator error is split into finite-element discretization and algorithmic matrix-approximation errors, with the discretization term bounded using projection estimates under the stated regularity conditions.The proof uses piecewise-constant finite elements and lifts local L2 approximation estimates to the Hilbert-Schmidt norm.Source: §4 · p. 28, §4.1 · p. 31

4.1 Finite Element Approximation

  • The finite-element projection estimate is established locally on mesh cells and summed over the partition to obtain a global L2 estimate, which is then lifted to a Hilbert-Schmidt discretization bound.The stated discretization result assumes ρ ∈ (0, 1) and ρ < s − d/2.Source: §4.1 · pp. 29, 31

4.2 Locally Exponentially Convergent Separable Polynomial Approximations

  • On η-admissible domains, asymptotically smooth kernels admit exponentially accurate polynomial approximations, so degree O(log(ε′^-1)) yields approximation spaces of dimension O(log^d(ε′^-1)).The L2-orthogonal projection onto polynomials of total degree at most m achieves the local approximation accuracy.Source: §4.2 · pp. 33, 37, 38

4.3 Hierarchical η-Admissible Decomposition

  • The hierarchical partition recursively subdivides cubes until each slab is η-admissible or reaches the mesh scale, leaving larger distant cubes admissible and refining cubes near the slab.Admissible cubes are maximal dyadic cubes satisfying admissibility, with diameters comparable up to constants to their distance from the fixed subdomain.Source: §4.3 · pp. 38–40

4.3.1 Overlap Bound for Admissible Cubes

  • Enlarged admissible domains have uniformly bounded overlap, quantified by K_W,adm depending only on d and η.The bound applies to the enlarged domains used in local approximation estimates.Source: §4.3.1 · p. 44, §4.3.2 · p. 50

4.3.2 Overlap Bound for Terminal Non-admissible Cubes

  • Enlarged admissible domains also have uniformly bounded overlap with terminal non-admissible domains, quantified by K_W,non depending only on d and η.The terminal non-admissible blocks lie near the diagonal, so this case is treated separately.Source: §4.3.2 · pp. 47, 50

4.3 Hierarchical η-Admissible Decomposition

  • The decomposition has logarithmically many admissible domains in the inverse mesh size, uniformly bounded terminal non-admissible domains, and uniformly bounded overlap of enlarged admissible domains.These geometric estimates support the row-wise approximation spaces constructed next.Source: §4.3 · p. 41, §4.3.2 · p. 50

4.4 Row Space Construction for Ah

  • Each row space combines coordinate vectors for terminal non-admissible regions with local polynomial coefficient vectors on admissible cubes, yielding controlled dimension and prescribed row-approximation accuracy.Algorithm 4 orthonormalizes these vectors by QR; choosing polynomial degree above a logarithmic threshold in inverse error tolerance controls local approximation error.Source: §4.4 · pp. 50–51
  • The constructed subspaces combine local polynomial spaces on admissible domains with coordinate vectors near terminal non-admissible regions, yielding bounded row-wise projection error and dimension.The dimension bound is uniform across rows and depends on the stated geometric and approximation parameters.Source: §4.4 · pp. 51, 52, 54, 55
  • The terminal non-admissible region intersects a bounded number of mesh cells and corresponding finite elements, controlling the coordinate vectors added to each row subspace.Under the stated finite-element assumption, the mesh-cell and finite-element counts agree.Source: §4.4 · pp. 52, 55

4.5 Proof of Theorem 2

  • Theorem 2 follows by applying Algorithm 1 to the row subspaces and combining its randomized approximation bound with the row-wise estimate to obtain a probability guarantee of at least 1 − δ.The proof uses q ≥ 2k + 1 queries, where k bounds the row-subspace dimensions.Source: §4.5 · pp. 57, 58, 59, 61

5 Concluding Remarks and Outlook

The paper presents a randomized row-subspace matrix approximation method and applies it to adjoint-free approximation of asymptotically smooth integral operators. Its outlook identifies practical constraints and broader settings for future work.

5 Concluding Remarks and Outlook

  • The algorithm achieves Hilbert-Schmidt error guarantees with polylogarithmic query complexity in inverse tolerance, equivalent to stretched-exponential error decay with query budget.The authors report numerical evidence for this behavior on one-dimensional non-self-adjoint elliptic solution operators.Source: §5 · p. 61
  • Polynomial bases for outer admissible domains are shared across multiple row subspaces, creating redundant computation and storage.The authors suggest reorganizing parallel computation across hierarchical-partition levels rather than row by row.Source: §5 · p. 61, Figure 8 · p. 61
  • Gaussian queries at one resolution cannot be reused on finer or coarser meshes, complicating efforts to identify a suitable discretization mesh.The authors also note that practitioners may not know the constants governing the exponential-convergence regime.Source: §5 · p. 61
  • The authors propose investigating query models beyond arbitrary Gaussian inputs when such inputs are impractical or physically inadmissible.The open question is which admissible query models still permit query-efficient approximation.Source: §5 · p. 62
  • Observed convergence is slower for stronger advection and poorer ellipticity, motivating study of coefficient-informed preconditioning for difficult operators.The text presents preconditioning as a possible route to more effective adjoint-free approximation, not an established result.Source: §5 · p. 62
  • Asymptotic smoothness is sufficient, not essential, for obtaining the local row-space information required by the framework.The authors suggest extending the analysis to broader elliptic solution operators and other kernel structures that yield accurate low-dimensional local row spaces.Source: §5 · p. 62

A.1 Proof of Corollary 2

The proof of Corollary 2 chooses parameters to meet Theorem 2's hypotheses, then applies that theorem to obtain the stated approximation guarantee.

A.1 Proof of Corollary 2

  • The corollary assumes a finite-element mesh size and a polynomial degree for each admissible cube restricted to a convex component of Ω.The stated setup also includes parameters ρ and s with ρ < s − d/2.Source: §A.1 · p. 66
  • The proof defines ε_q from the query count q and parameters, then uses q > q_0 to ensure ε_q < ε_0.The supplied passage gives the definition only in a fragmented form.Source: §A.1 · p. 67
  • The argument checks that the polynomial degree parameter m_0 meets the lower bound required by Theorem 2.The bound's expression is incomplete in the supplied passage.Source: §A.1 · p. 67
  • The proof concludes that Algorithm 2 constructs an ε_q-approximation with probability at least 1 − δ.This follows after establishing that the parameter choices satisfy Theorem 2's hypotheses.Source: §A.1 · p. 67

A.2 Finite Element Discretization

This appendix gives a cell-count lemma for quasi-uniform meshes and begins its proof using cell geometry and mesh regularity.

A.2 Finite Element Discretization

  • Lemma 15 states a bound on the number of cells in a quasi-uniform mesh sequence.The bound itself is not legible in the supplied passage.Source: §A.2 · p. 67
  • The proof introduces ρ_X as the diameter of the largest ball inscribed in a mesh cell X.It then invokes shape regularity and quasi-uniformity in deriving the bound.Source: §A.2 · p. 68
  • The proof states a lower bound on every mesh cell's volume in terms of K_mesh and h.The formula is fragmented in the supplied passage.Source: §A.2 · p. 68

A.3 Reference Discretization & Error Measurement for Section 3.2

The appendix describes reference discretizations for the numerical experiments and explains how their reported errors relate to continuous Hilbert-Schmidt error. It uses a fine reference mesh and reports a matrix Frobenius-error ratio as a numerical proxy.

A.3 Reference Discretization & Error Measurement for Section 3.2

  • The reference discretization uses a piecewise-constant space on a reference mesh, whose L2-orthonormal basis makes its prolongation an isometry and defines an orthogonal projection.For variable-coefficient problems, the reference solution operator is approximated with continuous piecewise-linear finite elements.Source: §A.3 · p. 68
  • For the constant-coefficient problem, the reference matrix is constructed directly from the known Green's function; for variable-coefficient problems, it uses a finite-element approximation.The constant-coefficient matrix uses exact evaluation of the Green's-function integrals.Source: §A.3 · p. 68
  • The algorithm applies Gaussian piecewise-constant forcings to the reference operator and projects each resulting solution onto the coarse piecewise-constant space.The returned operator approximation is formed from the coarse-mesh matrix approximation and prolongation operators.Source: §A.3 · pp. 68–69
  • The continuous error bound combines the reported relative error with reference projection and discretization errors.For the constant-coefficient experiment, the reference discretization error vanishes when Green's-function integrals are evaluated exactly.Source: §A.3 · p. 69
  • The experiments report the relative Frobenius error against the reference matrix as a numerical proxy for continuous relative Hilbert-Schmidt error.Reference meshes contain 16,384 elements for the constant-coefficient experiment and 8,192 for variable-coefficient experiments, at least four times the finest algorithm mesh.Source: §A.3 · p. 69
Loading 2610.07513v1…