Accuracy and stability of CUR decompositions with oversampling

Journal article

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 rows is 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 numerically stable manner and illustrate that oversampling, which increases the number of either 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.

Authors: Park, T; Nakatsukasa, Y

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Society for Industrial and Applied Mathematics
• Journal: SIAM Journal on Matrix Analysis and Applications
• Volume: 46
• Issue: 1
• Pages: 780-810
• Publication date: 2025-03-26
• Acceptance date: 2024-12-11
• DOI: 10.1137/24m1660346
• EISSN: 1095-7162
• ISSN: 0895-4798
• Language: English
• Keywords: CUR decomposition; low-rank approximation; stability analysis; oversampling