Tensor Recovery via $*_L$-Spectral k-Support Norm

Unlike traditional tensor decompositions which model low-rankness in the original domain, the recently proposed tensor $*_L$ -Singular Value Decomposition ( $*_L$ –SVD) casts a new light on tensor analysis by exploiting low-rankness in the spectral domain. For convexized rank minimization within the framework of $*_L$ –SVD, the tensor $*_L$ –Tubal Nuclear Norm ( $*_L$ –TNN) outperforms classical tensorial extensions of matrix nuclear norm in many applications. In this paper, we first generalize $*_L$ –TNN to the $*_L$ -Spectral $k$ -Support Norm ( $*_L$ -SpSN- $k$ ) as a new low-rank regularizer, and then adopt it to formulate two estimators for tensor recovery from noisy linear observations. Further, statistical performance of the proposed estimators is analyzed by establishing both deterministic and non-asymptotic upper bounds on the estimation error, which indicates that the proposed tensor Dantzig selector enjoys near-optimal estimation error for tensor compressive sensing and tensor completion. Moreover, proximal operator of the proposed norm is derived and embeded in an efficient algorithm to compute the estimators. Experiments on synthetic datasets verify correctness of the proposed error bounds and image inpainting results demonstrate superiority of the proposed estimators.