TY - GEN
T1 - Robust low-tubal-rank tensor completion via convex optimization
AU - Jiang, Qiang
AU - Ng, Kwok Po
N1 - Funding Information:
In Figure 4, we give the results obtained by various methods on all 50 images when ρ = 0.7 and γ = 0.3. Our algorithm outperforms the other methods quantitatively for most images. From the example in Figure 3, we see that our recovered images contain slightly sharper edges and fewer artifacts, exhibited in the enlarged views of the corresponding areas in red and blue boxes. 5 Conclusions In this work, we conduct a rigourous study for the RTC problem which aims to learn a low-tubal-rank tensor from partial observations that are arbitrarily corrupted. Our study rests heavily on recently proposed t-SVD algebraic framework, in which we can define the tubal rank and tensor nuclear norm for tensors. Equipped with the new definitions, we show that one can exactly recover a third-order tensor having low tubal rank with high probability and establish a theoretical bound for exact recovery when using a convex optimization algorithm. Numerical experiments verify our theoretical analysis and the real-world applications demonstrate the superiority of our method over other existing approaches. Considering that real data routinely lies in thousands or even billions of dimensions, the computational cost of our method may become expensive. We desire to develop fast algorithms for low-tubal-rank tensor recovery and will explore this important direction in our future work. Acknowledgements This work is supported in part by the Hong Kong RGC GRF projects 12306616, 12200317 and 12300218.
Funding Information:
This work is supported in part by the Hong Kong RGC GRF projects 12306616, 12200317 and 12300218.
PY - 2019/8
Y1 - 2019/8
N2 - This paper considers the problem of recovering multidimensional array, in particular third-order tensor, from a random subset of its arbitrarily corrupted entries. Our study is based on a recently proposed algebraic framework in which the tensor-SVD is introduced to capture the low-tubal-rank structure in tensor. We analyze the performance of a convex program, which minimizes a weighted combination of the tensor nuclear norm, a convex surrogate for the tensor tubal rank, and the tensor `1 norm. We prove that under certain incoherence conditions, this program can recover the tensor exactly with overwhelming probability, provided that its tubal rank is not too large and that the corruptions are reasonably sparse. The number of required observations is order optimal (up to a logarithm factor) when comparing with the degrees of freedom of the low-tubal-rank tensor. Numerical experiments verify our theoretical results and real-world applications demonstrate the effectiveness of our algorithm.
AB - This paper considers the problem of recovering multidimensional array, in particular third-order tensor, from a random subset of its arbitrarily corrupted entries. Our study is based on a recently proposed algebraic framework in which the tensor-SVD is introduced to capture the low-tubal-rank structure in tensor. We analyze the performance of a convex program, which minimizes a weighted combination of the tensor nuclear norm, a convex surrogate for the tensor tubal rank, and the tensor `1 norm. We prove that under certain incoherence conditions, this program can recover the tensor exactly with overwhelming probability, provided that its tubal rank is not too large and that the corruptions are reasonably sparse. The number of required observations is order optimal (up to a logarithm factor) when comparing with the degrees of freedom of the low-tubal-rank tensor. Numerical experiments verify our theoretical results and real-world applications demonstrate the effectiveness of our algorithm.
UR - https://www.ijcai.org/proceedings/2019/
UR - http://www.scopus.com/inward/record.url?scp=85074954432&partnerID=8YFLogxK
U2 - 10.24963/ijcai.2019/368
DO - 10.24963/ijcai.2019/368
M3 - Conference proceeding
AN - SCOPUS:85074954432
T3 - IJCAI International Joint Conference on Artificial Intelligence
SP - 2649
EP - 2655
BT - Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI 2019
A2 - Kraus, Sarit
PB - International Joint Conferences on Artificial Intelligence
T2 - 28th International Joint Conference on Artificial Intelligence, IJCAI 2019
Y2 - 10 August 2019 through 16 August 2019
ER -