Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.17947 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912346380697600 |
|---|---|
| author | Dastidar, Jeshu Weicht, Tait Wein, Alexander S. |
| author_facet | Dastidar, Jeshu Weicht, Tait Wein, Alexander S. |
| contents | We consider a basic computational task of finding $s$ planted rank-1 $m \times n$ matrices in a linear subspace $\mathcal{U} \subseteq \mathbb{R}^{m \times n}$ where $\dim(\mathcal{U}) = R \ge s$. The work of Johnston-Lovitz-Vijayaraghavan (FOCS 2023) gave a polynomial-time algorithm for this task and proved that it succeeds when ${R \le (1-o(1))mn/4}$, under minimal genericity assumptions on the input. Aiming to precisely characterize the performance of this algorithm, we improve the bound to ${R \le (1-o(1))mn/2}$ and also prove that the algorithm fails when ${R \ge (1+o(1))mn/\sqrt{2}}$. Numerical experiments indicate that the true breaking point is $R = (1+o(1))mn/\sqrt{2}$. Our work implies new algorithmic results for tensor decomposition, for instance, decomposing order-4 tensors with twice as many components as before. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_17947 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improving the Threshold for Finding Rank-1 Matrices in a Subspace Dastidar, Jeshu Weicht, Tait Wein, Alexander S. Data Structures and Algorithms We consider a basic computational task of finding $s$ planted rank-1 $m \times n$ matrices in a linear subspace $\mathcal{U} \subseteq \mathbb{R}^{m \times n}$ where $\dim(\mathcal{U}) = R \ge s$. The work of Johnston-Lovitz-Vijayaraghavan (FOCS 2023) gave a polynomial-time algorithm for this task and proved that it succeeds when ${R \le (1-o(1))mn/4}$, under minimal genericity assumptions on the input. Aiming to precisely characterize the performance of this algorithm, we improve the bound to ${R \le (1-o(1))mn/2}$ and also prove that the algorithm fails when ${R \ge (1+o(1))mn/\sqrt{2}}$. Numerical experiments indicate that the true breaking point is $R = (1+o(1))mn/\sqrt{2}$. Our work implies new algorithmic results for tensor decomposition, for instance, decomposing order-4 tensors with twice as many components as before. |
| title | Improving the Threshold for Finding Rank-1 Matrices in a Subspace |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.17947 |