Sample and Expand: Discovering Low-rank Submatrices With Quality Guarantees

2025/06/06 by Ciaperoni, Martino, Gionis, Aristides, Mannila, Heikki
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2506.06456

Abstract

The problem of approximating a matrix by a low-rank one has been extensively studied. This problem assumes, however, that the whole matrix has a low-rank structure. This assumption is often false for real-world matrices. We consider the problem of discovering submatrices from the given matrix with bounded deviations from their low-rank approximations. We introduce an effective two-phase method for this task: first, we use sampling to discover small nearly low-rank submatrices, and then they are expanded while preserving proximity to a low-rank approximation. An extensive experimental evaluation confirms that the method we introduce compares favorably to existing approaches.

Citations

• LoRA: Low-Rank Adaptation of Large Language Models
• Recent Developments in Boolean Matrix Factorization
• Targeted matrix completion
• Finding approximately rank-one submatrices with the nuclear norm and l1 norm
• An Improved Approximation Algorithm for the Column Subset Selection Problem

Related

• Low-rank Approximation of a Matrix: Novel Insights, New Progress, and Extensions
• Tighter Low-rank Approximation via Sampling the Leveraged Element
• On Recovering the Best Rank-r Approximation from Few Entries
• Learning-Based Low-Rank Approximations
• New Subset Selection Algorithms for Low Rank Approximation: Offline and Online