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

DOI10.48550/arXiv.2610.07513MaRDI QIDQ7367834arXivFDO

Authors Esther Gallmeier, Samuel E. Otto

Publication date 5 October 2026

Published in arXiv

Tldr We extend a fixed-sparsity matrix approximation algorithm to use randomized one-sided queries for approximating structured linear operators with local row-space information, achieving query complexity of O(log^d(ε^-1 δ^-1/2) log(ε^-1)) for Hilbert-Schmidt integral operators on d-dimensional spaces.

Full work available at URL https://doi.org/10.48550/arXiv.2610.07513

arXiv classification

math.NA

This page was built for publication: Efficient Approximation of Structured Linear Operators using Randomized One-Sided Queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7367834)