Tensor robust PCA (TRPCA) and tensor completion based on tensor nuclear norm under linear transform

Introduction

In [1], we propose a new tensor nuclear norm induced by the tensor-tensor product (t-product) [2] and apply it to tensor robust PCA (TRPCA) with exact recovery guarantee in theory. We also apply this tensor nuclear norm for tensor completion and provide the theoretical recovery guarantee in [3]. The original t-product [2] uses the discrete Fourier transform and uses the fast Fourier transform (FFT) for efficient computing. It is further generlaized to the t-product under arbitrary invertible linear transform in [4].

In [5], we show that if the linear transform satisfies where , then we can define a more general tensor nuclear norm induced by the t-product under this linear transform. We then apply this generalized tensor nuclear norm for tensor completion [5] and tensor robust PCA (TRPCA) [6] under linear transform and provide the exact recovery guarantee in theory. Intuitively, our works, [5] and [6], can be regarded as extensions of our former work [3] and [1], respectively. Howver, we restrict the linear transform to be a real matrix in [5][6] whie [3][1] uses the complex discrete Fourier transform. This makes some key differences in the proofs of the recovery guarantee.

We provide the codes for the following models:

1. Tensor completion based on tensor nuclear norm under linear transform [5]
   

   

2. Tensor robust PCA (TRPCA) based on tensor nuclear norm under linear transform [6]
   

   

Related Toolboxes

• Tensor-Tensor Product Toolbox
• Tensor robust principal component analysis
• Tensor completion by tensor nuclear norm minimization
• A Library of ADMM for Sparse and Low-rank Optimization

References

1. Canyi Lu, Jiashi Feng, Yudong Chen, Wei Liu, Zhouchen Lin, Shuicheng Yan. Tensor Robust Principal Component Analysis with A New Tensor Nuclear Norm. TPAMI. 2019
2. Misha E.Kilmer, Carla D. Martin. Factorization strategies for third-order tensors. Linear Algebra and its Applications, 435(3):641–658, 2011
3. Canyi Lu, Jiashi Feng, Zhouchen Lin, Shuicheng Yan. Exact Low Tubal Rank Tensor Recovery from Gaussian Measurements. International Joint Conference on Artificial Intelligence (IJCAI). 2018
4. Eric Kernfeld, Misha Kilmer, Shuchin Aeron. Tensor-Tensor Products with Invertible Linear Transforms. Linear Algebra and its Applications. 2015.
5. Canyi Lu, Xi Peng, Yunchao Wei. Low-Rank Tensor Completion With a New Tensor Nuclear Norm Induced by Invertible Linear Transforms. IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), 2019
6. Canyi Lu, Pan Zhou. Exact Recovery of Tensor Robust Principal Component Analysis under Linear Transforms. arXiv preprint arXiv:1907.08288. 2019
7. Canyi Lu, Jiashi Feng, Yudong Chen, Wei Liu, Zhouchen Lin, Shuicheng Yan. Tensor Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Tensors via Convex Optimization. CVPR, 2016