Accuracy and Stability of CUR decompositions with Oversampling
arXiv:2405.06375 · doi:10.1137/24M1660346
Abstract
This work investigates the accuracy and numerical stability of CUR decompositions with oversampling. The CUR decomposition approximates a matrix using a subset of columns and rows of the matrix. When the number of columns and the rows are the same, the CUR decomposition can become unstable and less accurate due to the presence of the matrix inverse in the core matrix. Nevertheless, we demonstrate that the CUR decomposition can be implemented in a numerical stable manner and illustrate that oversampling, which increases either the number of columns or rows in the CUR decomposition, can enhance its accuracy and stability. Additionally, this work devises an algorithm for oversampling motivated by the theory of the CUR decomposition and the cosine-sine decomposition, whose competitiveness is illustrated through experiments.
arXiv comment31 pages, 4 figures
References in corpus (4)
- The GNAT method for nonlinear model reduction: effective implementation and application to computational fluid dynamics and turbulent flows
- A New Selection Operator for the Discrete Empirical Interpolation Method -- improved a priori error bound and extensions
- Practical sketching algorithms for low-rank matrix approximation
- Randomized low-rank approximation for symmetric indefinite matrices