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

In this article, we develop methods for estimating a low rank tensor from noisy observations on a subset of its entries to achieve both statistical and computational efficiencies. There have been a lot of recent interests in this problem of noisy tensor completion. Much of the attention has been focused on the fundamental computational challenges often associated with problems involving higher order tensors, yet very little is known about their statistical performance. To fill in this void, in this article, we characterize the fundamental statistical limits of noisy tensor completion by establishing minimax optimal rates of convergence for estimating a $k$ th order low rank tensor under the general $\ell _{p}$ ( $1\le p\le 2$ ) norm which suggest significant room for improvement over the existing approaches. Furthermore, we propose a polynomial-time computable estimating procedure based upon power iteration and a second-order spectral initialization that achieves the optimal rates of convergence. Our method is fairly easy to implement and numerical experiments are presented to further demonstrate the practical merits of our estimator.In this article, we develop methods for estimating a low rank tensor from noisy observations on a subset of its entries to achieve both statistical and computational efficiencies. There have been a lot of recent interests in this problem of noisy tensor completion. Much of the attention has been focused on the fundamental computational challenges often associated with problems involving higher order tensors, yet very little is known about their statistical performance. To fill in this void, in this article, we characterize the fundamental statistical limits of noisy tensor completion by establishing minimax optimal rates of convergence for estimating a $k$th order low rank tensor under the general $\ell _{p}$ ($1\le p\le 2$) norm which suggest significant room for improvement over the existing approaches. Furthermore, we propose a polynomial-time computable estimating procedure based upon power iteration and a second-order spectral initialization that achieves the optimal rates of convergence. Our method is fairly easy to implement and numerical experiments are presented to further demonstrate the practical merits of our estimator.

摘要来源：OpenAlex 索引摘要（稿件版本未注明）

笔记与分组

分类依据与纠错

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

代码、数据与补充材料

噪声观测下兼具统计最优性与计算效率的低秩张量补全

原文摘要

同方向的基础文献

相关领域论文

Bootstrap inference in factor-augmented regressions with weak factors

Testing Conditional Distribution Equality Using Generative Models

Propensity score with factor loadings: evaluating the effect of the Paris Agreement on the returns of European stocks

Estimating Causal Treatment Effects in Placebo-Controlled Randomized Clinical Trials When High Placebo Response is Anticipated

Two Gaussians, Too Many: A bootstrap-based approach to assess identifiability in non-Gaussian structural vector autoregressions

Associating High-Dimensional Longitudinal Datasets through an Efficient Cross-Covariance Decomposition