Quasi-optimal hierarchically semi-separable matrix approximation

2025/05/22 by Amsel, Noah, Chen, Tyler, Keles, Feyza Duman +4 · 1 citation
#65F55 #68W20 #68W25 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Numerical Analysis (math.NA)

paper · doi:10.48550/arxiv.2505.16937

Abstract

We present a randomized algorithm for producing a quasi-optimal hierarchically semi-separable (HSS) approximation to an N× N matrix A using only matrix-vector products with A and A^T. We prove that, using O(k log(N/k)) matrix-vector products and O(N k² log(N/k)) additional runtime, the algorithm returns an HSS matrix B with rank-k blocks whose expected Frobenius norm error 𝔼[‖A - B‖_F²] is at most O(log(N/k)) times worse than the best possible approximation error by an HSS rank-k matrix. In fact, the algorithm we analyze in a simple modification of an empirically effective method proposed by [Levitt & Martinsson, SISC 2024]. As a stepping stone towards our main result, we prove two results that are of independent interest: a similar guarantee for a variant of the algorithm which accesses A's entries directly, and explicit error bounds for near-optimal subspace approximation using projection-cost-preserving sketches. To the best of our knowledge, our analysis constitutes the first polynomial-time quasi-optimality result for HSS matrix approximation, both in the explicit access model and the matrix-vector product query model.

Cited by

• A recursive butterfly factorization with optimality guarantees

Related

• Fixed-sparsity matrix approximation from matrix-vector products
• Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time
• On the best approximation of the hierarchical matrix product
• Low-Rank Approximation with 1/ε^1/3 Matrix-Vector Products
• Optimal Column-Based Low-Rank Matrix Reconstruction