Statistical inference in tensor completion: Optimal uncertainty quantification and statistical-to-computational gaps

This paper presents a simple yet efficient method for statistical inference of tensor linear forms using incomplete and noisy observations. Under the Tucker low-rank tensor model and the missing-at-random assumption, we utilize an appropriate initial estimate along with a debiasing technique followed by a one-step power iteration to construct an asymptotically normal test statistic. This method is suitable for various statistical inference tasks, including constructing confidence intervals, inference under heteroskedastic and sub-exponential noise, and simultaneous testing. We demonstrate that the estimator achieves the Cramér–Rao lower bound on Riemannian manifolds, indicating its optimality in uncertainty quantification. We comprehensively examine statistical-to-computational gaps and investigate the impact of initialization on the minimal conditions regarding sample sizes and signal-to-noise ratios required for accurate inference. Our findings show that, with independent initialization, statistically optimal sample sizes and signal-to-noise ratios are sufficient for accurate inference. Conversely, if only dependent initialization is available, computationally optimal sample sizes and signal-to-noise ratios still guarantee asymptotic normality without the need for data-splitting. We present the phase transition between computational and statistical limits. Numerical simulation results align with the theoretical findings.