Close to optimal column approximations with a single SVD

2023/08/17 by Alexander Osinsky, Osinsky, Alexander · 2 citations
Computer Science · Engineering · Mathematics · #Digital Image Processing Techniques #FOS: Mathematics #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques #Tensor decomposition and applications

paper · pdf · doi:10.48550/arxiv.2308.09068

openalex publication_date 2023/08/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The best column approximation in the Frobenius norm with r columns has an error at most √(r+1) times larger than the truncated singular value decomposition. Reaching this bound in practice involves either expensive random volume sampling or at least r executions of singular value decomposition. In this paper it will be shown that the same column approximation bound can be reached with only a single SVD (which can also be replaced with approximate SVD). As a corollary, it will be shown how to find a highly nondegenerate submatrix in r rows of size N in just O(Nr²) operations, which mostly has the same properties as the maximum volume submatrix.

Cited by

• Interpolatory Dynamical Low-Rank Approximation: Theoretical Foundations and Algorithms
• Scientific Applications Leveraging Randomized Linear Algebra

Related

• Row-aware Randomized SVD with applications
• A Precise Performance Analysis of the Randomized Singular Value Decomposition
• Beyond Symmetry: Best Submatrix Selection for the Sparse Truncated SVD
• Fast monte-carlo algorithms for finding low-rank approximations
• Robust SVD Made Easy: A fast and reliable algorithm for large-scale data analysis