Euclidean-Norm-Induced Schatten-p Quasi-Norm Regularization for Low-Rank Tensor Completion and Tensor Robust Principal Component Analysis
This work provides a more effective and scalable method for low-rank tensor recovery, which is crucial for applications dealing with large-scale tensor data, by addressing the computational challenges of Schatten-p quasi-norms. It is an incremental improvement for researchers and practitioners in tensor decomposition and machine learning.
This paper introduces a new class of tensor rank regularizers derived from the Euclidean norms of CP component vectors, which are shown to be monotonic transformations of tensor Schatten-p quasi-norms. This approach allows for implicit minimization of Schatten-p quasi-norms in low-rank tensor completion (LRTC) and tensor robust principal component analysis (TRPCA), offering a sharper rank proxy than the nuclear norm and scaling to large tensors. The study also proves that for d-order tensors, p=1/d yields a tighter error bound for LRTC compared to p > 1/d.
The nuclear norm and Schatten-$p$ quasi-norm are popular rank proxies in low-rank matrix recovery. However, computing the nuclear norm or Schatten-$p$ quasi-norm of a tensor is hard in both theory and practice, hindering their application to 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 via the component vectors. The method scales to big tensors and provides an arbitrarily sharper rank proxy for low-rank tensor recovery compared to the nuclear norm. On the other hand, we study the generalization abilities of LRTC with the Schatten-$p$ quasi-norm regularizer and LRTC with the proposed regularizers. The theorems show that a relatively sharper regularizer leads to a tighter error bound, which is consistent with our numerical results. Particularly, we prove that for LRTC with Schatten-$p$ quasi-norm regularizer on $d$-order tensors, $p=1/d$ is always better than any $p>1/d$ in terms of the generalization ability. We also provide a recovery error bound to verify the usefulness of small $p$ in the Schatten-$p$ quasi-norm for TRPCA. Numerical results on synthetic data and real data demonstrate the effectiveness of the regularization methods and theorems.