Efficient Algorithms for Constructing an Interpolative Decomposition

2021/05/14 by Rishi Advani, Advani, Rishi, Sean O'Hagan +1
Computer Science · Engineering · Mathematics · #65F55 #FOS: Mathematics #G.1.3 #Medical Image Segmentation Techniques #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques #Statistical and numerical algorithms

paper · pdf · doi:10.48550/arxiv.2105.07076

openalex publication_date 2021/05/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Low-rank approximations are essential in modern data science. The interpolative decomposition provides one such approximation. Its distinguishing feature is that it reuses columns from the original matrix. This enables it to preserve matrix properties such as sparsity and non-negativity. It also helps save space in memory. In this work, we introduce two optimized algorithms to construct an interpolative decomposition along with numerical evidence that they outperform the current state of the art.

Citations

• The Approximation of One Matrix by Another of Lower Rank
• A randomized algorithm for the decomposition of matrices
• Gradient-based learning applied to document recognition
• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions
• Random Projections and Dimension Reduction

Related

• Structure-Aware Analyses and Algorithms for Interpolative Decompositions
• Robust Blockwise Random Pivoting: Fast and Accurate Adaptive Interpolative Decomposition
• Block Discrete Empirical Interpolation Methods
• Interpolative Decomposition Butterfly Factorization
• Adaptive Parallelizable Algorithms for Interpolative Decompositions via Partially Pivoted LU