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

2025/04/24 by Dastidar, Jeshu, Weicht, Tait, Wein, Alexander S. · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2504.17947

Abstract

We consider a basic computational task of finding s planted rank-1 m × n matrices in a linear subspace U ⊆ ℝ^{m × n} where dim(U) = R ≥ s. The work of Johnston-Lovitz-Vijayaraghavan (FOCS 2023) gave a polynomial-time algorithm for this task and proved that it succeeds when R ≤ (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 ≤ (1-o(1))mn/2 and also prove that the algorithm fails when R ≥ (1+o(1))mn/√(2). Numerical experiments indicate that the true breaking point is R = (1+o(1))mn/√(2). Our work implies new algorithmic results for tensor decomposition, for instance, decomposing order-4 tensors with twice as many components as before.

Cited by

• Tensor decomposition beyond uniqueness, with an application to the minrank problem

Related

• Finding a low-rank basis in a matrix subspace
• Overcomplete Tensor Decomposition via Koszul-Young Flattenings
• On the equivalence between low rank matrix completion and tensor rank
• Ruling Out Low-rank Matrix Multiplication Tensor Decompositions with Symmetries via SAT
• Tensor decomposition beyond uniqueness, with an application to the minrank problem