Sample Complexity of Low-rank Tensor Recovery from Uniformly Random Entries
<|reference_start|>Sample Complexity of Low-rank Tensor Recovery from Uniformly Random Entries: We show that a generic tensor $T\in \mathbb{F}^{n\times n\times \dots\times n}$ of order $k$ and CP rank $d$ can be uniquely recovered from $n\log n+dn\log \log n +o(n\log \log n) $ uniformly random entries with high probability if $d$ and $k$ are constant and $\mathbb{F}\in \{\mathbb{R},\mathbb{C}\}$. The bound is tight up to the coefficient of the second leading term and improves on the existing $O(n^{\frac{k}{2}}{\rm polylog}(n))$ upper bound for order $k$ tensors. The bound is obtained by showing that the projection of the Segre variety to a random axis-parallel linear subspace preserves $d$-identifiability with high probability if the dimension of the subspace is $n\log n+dn\log \log n +o(n\log \log n) $ and $n$ is sufficiently large.<|reference_end|>
@article{hamaguchi2024sample,
    title={Sample Complexity of Low-rank Tensor Recovery from Uniformly Random
  Entries},
    author={Hiroki Hamaguchi and Shin-ichi Tanigawa},
    journal={arXiv preprint arXiv:2408.03504},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.03504},
    primaryClass={math.CO cs.IT math.AG math.IT math.PR}
}