Sample Complexity of Low-rank Tensor Recovery from Uniformly Random Entries

Hiroki Hamaguchi, Shin-ichi Tanigawa

We show that a generic tensor $T\in {\mathbb{F}}^{n\times n\times \cdots \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)…