Exact Tensor Completion Using t-SVD

By Zemin Zhang, Shuchin Aeron. IEEE Transactions on Signal Processing, 2015

660 citations recorded by the source corpus.

In this paper, we focus on the problem of completion of multidimensional arrays (also referred to as tensors), in particular three-dimensional (3-D) arrays, from limited sampling. Our approach is based on a recently proposed tensor algebraic framework where 3-D tensors are treated as linear operators over the set of 2-D tensors. In this framework, one can obtain a factorization for 3-D data, referred to as the tensor singular value decomposition (t-SVD), which is similar to the SVD for matrices. t-SVD results in a notion of rank referred to as the tubal-rank. Using this approach we consider the problem of sampling and recovery of 3-D arrays with low tubal-rank. We show that by solving a convex optimization problem, which minimizes a convex surrogate to the tubal-rank, one can guarantee exact recovery with high probability as long as number of samples is of the order <inline-formula><tex-math notation="LaTeX">$O(rnk \log (nk))$ </tex-math></inline-formula>, given a tensor of size <inline-formula><tex-math notation="LaTeX">$n\times n\times k$ </tex-math></inline-formula> with tubal-rank <inline-formula><tex-math notation="LaTeX">$r$</tex-math></inline-formula> . The conditions under which this result holds are similar to the incoherence conditions for low-rank matrix completion under random sampling. The difference is that we define incoherence under the algebraic setup of t-SVD, which is different from the standard matrix incoherence conditions. We also compare the numerical performance of the proposed algorithm with some state-of-the-art approaches on real-world datasets.

Subfields: Computational Mathematics, Computational Mechanics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/8c044e3b0b58cef54422e11194ac948acfa08be5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

1. Yimin Wei
2. Liqun Qi
3. Yun Miao
4. Shuicheng Yan
5. Pan Zhou
6. Chao Zhang
7. Jiashi Feng
8. Canyi Lu

In Computational Mechanics

1. Zhouchen Lin
2. Canyi Lu
3. Jiashi Feng
4. Shuicheng Yan
5. Yudong Chen
6. Yimin Wei
7. Yun Miao
8. Pan Zhou

In Signal Processing

1. Zhouchen Lin
2. Yimin Wei
3. Yun Miao
4. Liqun Qi
5. Shuicheng Yan
6. Pan Zhou
7. Chao Zhang
8. Jiashi Feng

Citations in the corpus

• T-Jordan Canonical Form and T-Drazin Inverse Based on the T-Product (2019, methodology): “such as image processing [33, 34, 49, 55, 59, 70], computer vision [20, 64], signal processing [12, 41, 44, 58], low rank tensor recovery and robust tensor PCA [39, 41], data completion and denoising [14, 28, 29, 42, 44, 47, 48, 53, 60, 65, 66, 67, 68, 69]. An approach of linearization is provided b”
• Tensor Robust Principal Component Analysis with a New Tensor Nuclear Norm (2018, methodology): “Third, if the CP rank of A is r , then its tubal rank is at most r [33]. i , where ◦ denotes the outer product, be the CP decomposition of A . i ) .”
• Tensor Factorization for Low-Rank Tensor Completion (2018, methodology): “applied TNN to tensor completion [1], with state-of-the-art video inpainting results achieved, and further analyzed the exact completion conditions of the proposed model in [39].”
• Generalized tensor function via the tensor singular value decomposition based on the T-product (2019, background): “…[9, 33, 36, 45], low rank tensor recovery and robust tensor PCA [31, 33], data completion and denoising [11, 24, 25, 34, 36, 38, 39, 42, 47, 50, 52, 53, 54, 55], since the tensor T-product change problems to block circulant matrices which could be block diagonalizable by the fast Fourier…”
• Tensor Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Tensors via Convex Optimization (2016, background): “Hence, in this section, we first introduce some incoherence conditions of the tensor L0 extended from [27, 4].”