Statistically optimal and computationally efficient low rank tensor completion from noisy entries (Q2656588)

Let \(\mathbf{T} \in \mathbb{R}^{d_1 \times \dots \times d_k}\) be a \(k\)-th order tensor. For a given sample size \(n\), the authors study the problem of recovering \(\mathbf{T}\) from observations of a subset of its entries. Particularly, they assume that \(n\) independent copies \((Y_i, \omega_i)_{1 \leq i \leq n}\) of \((Y, \omega)\) can be observed, where \[ Y = T(\omega) + \xi. \] In this, it is assumed that \(\omega\) is uniformly sampled from \(\{1, \ldots, d_1\} \times \dots \times \{1, \ldots, d_k\}\) and that it is stochastically independent of the centered, sub-Gaussian random variable \(\xi\) which describes the measurement error. Under the additional assumption that \(\mathbf{T}\) is of low rank (and that \(n\) may be much smaller than \(\prod_{j=1}^k d_j\)), the authors establish minimax optimal rates of convergence (as \(n \to \infty\)) for estimating \(\mathbf{T}\) under \(\ell_p\) loss, where \(p \in [1, 2]\). Furthermore, a polynomial-time computable estimating procedure based upon power iteration and a second-order spectral initialization is proposed. The authors prove that the corresponding estimator achieves the optimal rates of convergence. Besides these theoretical contributions, the authors also present some numerical results.