A Geometric View of Adaptive Cross Approximation via Exterior Algebra
Abstract
Adaptive cross approximation (ACA) constructs low-rank CUR approximations from selected rows and columns of a matrix, making it attractive when individual entries are inexpensive to query but forming or repeatedly multiplying by the full matrix is not. Its practical performance, however, is not well explained by existing worst-case bounds, which can be exponentially large and often fail to predict when greedy largest-entry pivoting performs poorly. By viewing the matrix as a cross-gram matrix, we reinterpret the classical determinantal formula for the CUR residual through the lens of exterior algebra. In this representation, each residual entry is a weighted inner product between two (k+1)-blades divided by the normalized volume of the pivot block. The formula separates three effects: the weighted magnitudes of singular-vector rows, their angular geometry, and the conditioning of the selected pivots. From this we recover a classical σk+1-type estimate, characterize when one pivot annihilates or nearly annihilates additional rows and columns, obtain a quasi-optimality estimate for positive-semidefinite matrices, and bound the rank-one update through an explicit angle-based formula. We use this framework to explain the failure of greedy ACA on an asymmetric spiral-kernel example and to motivate a geometry-aware weighted-mass pivoting rule for radial-basis Galerkin stiffness matrices. In the reported experiments, weighted-mass pivoting often reduces the Frobenius residual relative to greedy pivoting and randomly pivoted Cholesky while retaining comparable runtime on parallel hardware.
Related
- Geometric mean quantization via adaptive approximation
- Efficient Low-Rank Approximation of Quaternion Matrices via Adaptive Cross Approximation
- Schreyer Resolutions over the Exterior Algebra
- Adaptive Randomized Pivoting for Tensor Cross Approximation in the T-Product Framework
- Hilbert functions over the exterior algebra and f-vectors in higher rank II: Generalizing Linusson's count to sumsets of f-vectors
BibTeX
@misc{loe2026geometric,
title = {{A Geometric View of Adaptive Cross Approximation via Exterior Algebra}},
author = {Trevor Loe and Longxiu Huang and Deanna Needell},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17947},
eprint = {2609.17947},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17947},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Geometric View of Adaptive Cross Approximation via Exterior Algebra
AU - Trevor Loe
AU - Longxiu Huang
AU - Deanna Needell
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.17947
UR - https://arxiv.org/abs/2609.17947
AB - Adaptive cross approximation (ACA) constructs low-rank CUR approximations from selected rows and columns of a matrix, making it attractive when individual entries are inexpensive to query but forming or repeatedly multiplying by the full matrix is not. Its practical performance, however, is not well explained by existing worst-case bounds, which can be exponentially large and often fail to predict when greedy largest-entry pivoting performs poorly. By viewing the matrix as a cross-gram matrix, we reinterpret the classical determinantal formula for the CUR residual through the lens of exterior algebra. In this representation, each residual entry is a weighted inner product between two (k+1)-blades divided by the normalized volume of the pivot block. The formula separates three effects: the weighted magnitudes of singular-vector rows, their angular geometry, and the conditioning of the selected pivots. From this we recover a classical σ_k+1-type estimate, characterize when one pivot annihilates or nearly annihilates additional rows and columns, obtain a quasi-optimality estimate for positive-semidefinite matrices, and bound the rank-one update through an explicit angle-based formula. We use this framework to explain the failure of greedy ACA on an asymmetric spiral-kernel example and to motivate a geometry-aware weighted-mass pivoting rule for radial-basis Galerkin stiffness matrices. In the reported experiments, weighted-mass pivoting often reduces the Frobenius residual relative to greedy pivoting and randomly pivoted Cholesky while retaining comparable runtime on parallel hardware.
ER -