Improving the Threshold for Finding Rank-1 Matrices in a Subspace

Abstract

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.

37 pages