Bias-variance Tradeoff in Tensor Estimation

We study denoising of a third-order tensor when the ground-truth tensor is not necessarily Tucker low-rank. Specifically, we observe Y=X^+Z R^p₁ p₂ p₃, where X^ is the ground-truth tensor, and Z is the noise tensor. We propose a simple variant of the higher-order tensor SVD estimator X. We show that uniformly over all user-specified Tucker ranks (r₁, r₂, r₃), \| X - X^* \| ₅² = O (κ² \ r₁r₂r₃+₊=₁^{3 p₊ r₊ \} \; + \; ξ (ₑ_₁, r₂, r₃) ²) with high probability. Here, the bias term ξ (ₑ䃑, ₑ䃒, ₑ䃓) corresponds to the best achievable approximation error of X^ over the class of tensors with Tucker ranks (r₁, r₂, r₃) ; κ² quantifies the noise level; and the variance term κ² \r₁r₂r₃+₊=₁^{3 p₊ r₊\} scales with the effective number of free parameters in the estimator X. Our analysis achieves a clean rank-adaptive bias--variance tradeoff: as we increase the ranks of estimator X, the bias ξ (r₁, r₂, r₃) decreases and the variance increases. As a byproduct we also obtain a convenient bias-variance decomposition for the vanilla low-rank SVD matrix estimators.