Sample and Expand: Discovering Low-rank Submatrices With Quality Guarantees
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918184210137088 |
|---|---|
| author | Ciaperoni, Martino Gionis, Aristides Mannila, Heikki |
| author_facet | Ciaperoni, Martino Gionis, Aristides Mannila, Heikki |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_06456 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sample and Expand: Discovering Low-rank Submatrices With Quality Guarantees Ciaperoni, Martino Gionis, Aristides Mannila, Heikki Data Structures and Algorithms 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. |
| title | Sample and Expand: Discovering Low-rank Submatrices With Quality Guarantees |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.06456 |