Randomized Rank-Structured Matrix Compression by Tagging

Katherine J. Pearce, Anna Yesypenko, James Levitt, Per-Gunnar Martinsson · 2025

Read Randomized Rank-Structured Matrix Compression by Tagging by Katherine J. Pearce, Anna Yesypenko, James Levitt, Per-Gunnar Martinsson (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-05528.txt.

Description

Katherine Pearce, Anna Yesypenko, James Levitt, and Per-Gunnar Martinsson presented in 2025 a faster way to compress a class of large matrices. Such matrices arise in science problems and share a low-rank block structure. Older methods to compress them can be slow when entries are costly to reach.

Their trick, called tagging, works through products of the matrix with test vectors rather than single entries. It needs only a fixed number of such products plus cheap follow-up work. The cost depends only on the rank and the shape of the problem. Tests on matrices from physics equations showed tagging beat rival methods on both product count and total time.

Catalog record

CREATORKatherine J. Pearce, Anna Yesypenko, James Levitt, Per-Gunnar Martinsson
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE285 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-05528

Browse the full library · About the Tower of Babel