A sublinear-time randomized algorithm for column and row subset selection based on strong rank-revealing QR factorizations

2024/02/21 by Alice Cortinovis, Lexing Ying, Cortinovis, Alice +1 · 1 citation
Computer Science · #65F30 (Primary) 15A23 (Secondary) #FOS: Mathematics #Face and Expression Recognition #Machine Learning and Algorithms #Numerical Analysis (math.NA) #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.2402.13975

openalex publication_date 2024/02/21 · openalex created_date 2024/02/24 · openalex updated_date 2026/07/28

Abstract

In this work, we analyze a sublinear-time algorithm for selecting a few rows and columns of a matrix for low-rank approximation purposes. The algorithm is based on an initial uniformly random selection of rows and columns, followed by a refinement of this choice using a strong rank-revealing QR factorization. We prove bounds on the error of the corresponding low-rank approximation (more precisely, the CUR approximation error) when the matrix is a perturbation of a low-rank matrix that can be factorized into the product of matrices with suitable incoherence and/or sparsity assumptions.

Cited by

• A new cross approximation for Tucker tensors and its application in Tucker-Anderson Acceleration

Related

• Randomized strong rank-revealing QR for column subset selection and low-rank matrix approximation
• Randomized algorithms for low-rank matrix factorizations: sharp\n performance bounds
• Efficient QR-based Column Subset Selection through Randomized Sparse Embeddings
• Blocked rank-revealing QR factorizations: How randomized sampling can be used to avoid single-vector pivoting
• New Subset Selection Algorithms for Low Rank Approximation: Offline and Online