Sample and Expand: Discovering Low-Rank Submatrices with Quality Guarantees
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.
Cite
Text
Ciaperoni et al. "Sample and Expand: Discovering Low-Rank Submatrices with Quality Guarantees." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2025. doi:10.1007/978-3-032-06096-9_5Markdown
[Ciaperoni et al. "Sample and Expand: Discovering Low-Rank Submatrices with Quality Guarantees." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2025.](https://mlanthology.org/ecmlpkdd/2025/ciaperoni2025ecmlpkdd-sample/) doi:10.1007/978-3-032-06096-9_5BibTeX
@inproceedings{ciaperoni2025ecmlpkdd-sample,
title = {{Sample and Expand: Discovering Low-Rank Submatrices with Quality Guarantees}},
author = {Ciaperoni, Martino and Gionis, Aristides and Mannila, Heikki},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2025},
pages = {78-95},
doi = {10.1007/978-3-032-06096-9_5},
url = {https://mlanthology.org/ecmlpkdd/2025/ciaperoni2025ecmlpkdd-sample/}
}