Let \(A(t) \in \mathbb {R}^{m\times n}\) be a parameter-dependent matrix and suppose we want to compute its low-rank approximation at a finite number of parameter values \(t_1,t_2,...,t_q\). This problem arises in several applications including the compression of a series of images, dynamical systems, and Gaussian process regression, where low-rank approximations are needed for the sequence \(A(t_1), A(t_2),...,A(t_q)\). While existing methods such as dynamical low-rank approximation [6] and random embedding techniques [7] offer solutions, they typically incur a complexity of \(\mathcal {O}(r_iT_{A(t_i)})\) for each parameter \(t_i\), with \(r_i\) as the target rank and \(T_{A(t_i)}\) as the cost of a matrix-vector product with \(A(t)\). We propose an alternative approach using the CUR decomposition, which can accelerate low-rank approximation to an average complexity of \(\mathcal {O}(T_{A(t_i)})\) while addressing key challenges, such as rank-adaptivity and error control, often missing in other methods.

The CUR decomposition [3, 5, 8, 11] approximates a matrix \(A\) using subsets of its rows and columns:

\begin{equation*} A \approx CU^\dagger R, \end{equation*}

where \(C\) and \(R\) are subsets of \(A\)’s columns and rows, and \(U\) is their intersection. This decomposition, in contrast to methods like the truncated SVD, preserves properties such as sparsity and aids in data interpretation by identifying significant columns and rows. For \(A(t)\), recomputing row and column indices for each \(t_i\) is inefficient, as indices derived for one parameter value may still provide useful information for nearby parameters. Building on this insight, we introduce an algorithm, AdaCUR [12], which maximizes the reuse of row and column indices across parameter values.

AdaCUR computes low-rank approximations of parameter-dependent matrices via CUR decomposition:

\begin{equation*} A(t) \approx C(t)U(t)^\dagger R(t), \end{equation*}

where \(C(t)\) and \(R(t)\) are subsets of the columns and rows of \(A(t)\), and \(U(t)\) is their intersection. Starting from an initial CUR decomposition, AdaCUR reuses row and column indices until the error exceeds a specified threshold, at which point the indices are recomputed. To achieve this efficiently and reliably, we rely on a variety of tools from randomized numerical linear algebra [9]. Specifically, we use pivoting on a random sketch [1, 2] to obtain a reliable set of row and column indices, randomized rank estimation [10] to adapt to rank changes across parameter values, and randomized norm estimation [4] to approximate the relative error, ensuring effective error control. The resulting algorithm is efficient, rank-adaptive, and incorporates error control.

Additionally, we present FastAdaCUR, a variation that prioritizes speed over precision. FastAdaCUR achieves linear complexity in \(m\) and \(n\) after an initial index computation phase. Although highly efficient and rank-adaptive, it lacks rigorous error control, as it emphasizes speed over accuracy by only examining a subset of rows and columns of the matrix.

References

• [1]  Y. Dong and P.-G. Martinsson, Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions, Adv. Comput. Math., 49 (2023).

• [2]  J. A. Duersch and M. Gu, Randomized projection for rank-revealing matrix factorizations and low-rank approximations, SIAM Rev., 62 (2020), pp. 661–682.

• [3]  S. Goreinov, E. Tyrtyshnikov, and N. Zamarashkin, A theory of pseudoskeleton approximations, Linear Algebra Appl., 261 (1997), pp. 1–21.

• [4]  S. Gratton and D. Titley-Peloquin, Improved bounds for small-sample estimation, SIAM J. Matrix Anal. Appl., 39 (2018), pp. 922–931.

• [5]  K. Hamm and L. Huang, Perspectives on CUR decompositions, Appl. Comput. Harmon. Anal., 48 (2020), pp. 1088–1099.

• [6]  O. Koch and C. Lubich, Dynamical low-rank approximation, SIAM J. Matrix Anal. Appl., 29 (2007), pp. 434–454.

• [7]  D. Kressner and H. Y. Lam, Randomized low-rank approximation of parameter-dependent matrices, Numer. Lin. Alg. Appl., (2024), p. e2576.

• [8]  M. W. Mahoney and P. Drineas, CUR matrix decompositions for improved data analysis, Proc. Natl. Acad. Sci., 106 (2009), pp. 697–702.

• [9]  P.-G. Martinsson and J. A. Tropp, Randomized numerical linear algebra: Foundations and algorithms, Acta Numer., 29 (2020), p. 403–572.

• [10]  M. Meier and Y. Nakatsukasa, Fast randomized numerical rank estimation for numerically low-rank matrices, Linear Algebra Appl., 686 (2024), pp. 1–32.

• [11]  T. Park and Y. Nakatsukasa, Accuracy and stability of CUR decompositions with oversampling, arXiv:2405.06375, (2024).

• [12]  T. Park and Y. Nakatsukasa, Low-rank approximation of parameter-dependent matrices via CUR decomposition, arXiv:2408.05595, (2024).