Low-Rank Tensor Recovery with Euclidean-Norm-Induced Schatten-p
  Quasi-Norm Regularization
  The nuclear norm and Schatten-$p$ quasi-norm are popular rank proxies in
low-rank matrix recovery. Unfortunately, computing the nuclear norm or
Schatten-$p$ quasi-norm of a tensor is NP-hard, which is a pity for low-rank
tensor completion (LRTC) and tensor robust principal component analysis
(TRPCA). In this paper, we propose a new class of tensor rank regularizers
based on the Euclidean norms of the CP component vectors of a tensor and show
that these regularizers are monotonic transformations of tensor Schatten-$p$
quasi-norm. This connection enables us to minimize the Schatten-$p$ quasi-norm
in LRTC and TRPCA implicitly. The methods do not use the singular value
decomposition and hence scale to big tensors. Moreover, the methods are not
sensitive to the choice of initial rank and provide an arbitrarily sharper rank
proxy for low-rank tensor recovery compared to nuclear norm. On the other hand,
we study the generalization abilities of LRTC with Schatten-$p$ quasi-norm
regularization and LRTC with our regularizers. The theorems show that a
relatively sharper regularizer leads to a tighter error bound, which is
consistent with our numerical results. Numerical results on synthetic data and
real data demonstrate the effectiveness and superiority of our methods compared
to baseline methods.
