Tensor Completion Using Spectral $(k,p)$ -Support Norm

In this paper, the goal is to reconstruct a tensor, i.e., a multi-dimensional array, when only subsets of its entries are observed. For well-posedness, the tensor is assumed to have a low-Tucker-rank structure. To estimate the underlying tensor from its partial observations, we first propose an estimator based on a newly defined balanced spectral (k, p)-support norm. To efficiently compute the estimator, we come up with a scalable algorithm for the minimization of the spectral (k, p)-support norm. Instead of directly solving the primal problem which involves full SVD in each iteration, the proposed algorithm benefits from the Lagrangian dual through minimizing the dual norm of the (k, p)-support norm which only computes the first k leading singular values and singular vectors in each iteration. To explore the statistical performance of the proposed estimator, upper bounds on the sample complexity and estimation error are then established. Simulation studies confirm that the error bounds can predict the scalable behavior of the estimation error. Experimental results on synthetic and real datasets demonstrate that the spectral (k, p)-support norm based method outperforms the nuclear norm based ones.