For generic planted rank-one matrices in an R-dimensional subspace of m by n matrices, the JLV algorithm is proven to recover them when R is about half of mn, and proven to fail above about 0.71 times mn.
Efficient Tensor Decomposition
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
This chapter studies the problem of decomposing a tensor into a sum of constituent rank one tensors. While tensor decompositions are very useful in designing learning algorithms and data analysis, they are NP-hard in the worst-case. We will see how to design efficient algorithms with provable guarantees under mild assumptions, and using beyond worst-case frameworks like smoothed analysis.
fields
cs.DS 1years
2025 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
Improving the Threshold for Finding Rank-1 Matrices in a Subspace
For generic planted rank-one matrices in an R-dimensional subspace of m by n matrices, the JLV algorithm is proven to recover them when R is about half of mn, and proven to fail above about 0.71 times mn.