Low-Rank Approximation of Parameter-Dependent Matrices via CUR Decomposition
Taejun Park, Yuji Nakatsukasa · SIAM Journal on Scientific Computing · 2025
Abstract. A low-rank approximation of a parameter-dependent matrix [Formula: see text] is an important task in the computational sciences appearing, for example, in dynamical systems and compression of a series of images. In this work, we introduce AdaCUR, an efficient algorithm for computing a low-rank approximation of parameter-dependent matrices via CUR decomposition. The key idea for this algorithm is that for nearby parameter values, the column and row indices for the CUR decomposition can often be reused. AdaCUR is rank-adaptive, provides error control, and has complexity that compares favorably against existing methods. A faster algorithm, FastAdaCUR, is also given that prioritizes speed over accuracy, is rank-adaptive, and has complexity that is at most linear in the number of rows or columns, but without error control.