Low-Tubal-Rank Tensor Completion Using Alternating Minimization

DOI10.1109/TIT.2019.2959980MaRDI QIDQ5123815zbMATH OpenOpenAlexFDO

Authors Xiaoyang Liu, Shuchin Aeron, Vaneet Aggarwal, Xiaodong Wang

Publication date 29 September 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.01690

zbMATH Keywords

alternating minimization methodlow-rank tensor approximationtensor completion

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Matrix completion problems (15A83) Estimation in multivariate analysis (62H12) Numerical methods for low-rank matrix approximation; matrix compression (65F55) Applications of mathematical programming (90C90)

Abstract: The low-tubal-rank tensor model has been recently proposed for real-world multidimensional data. In this paper, we study the low-tubal-rank tensor completion problem, i.e., to recover a third-order tensor by observing a subset of its elements selected uniformly at random. We propose a fast iterative algorithm, called {em Tubal-Alt-Min}, that is inspired by a similar approach for low-rank matrix completion. The unknown low-tubal-rank tensor is represented as the product of two much smaller tensors with the low-tubal-rank property being automatically incorporated, and Tubal-Alt-Min alternates between estimating those two tensors using tensor least squares minimization. First, we note that tensor least squares minimization is different from its matrix counterpart and nontrivial as the circular convolution operator of the low-tubal-rank tensor model is intertwined with the sub-sampling operator. Second, the theoretical performance guarantee is challenging since Tubal-Alt-Min is iterative and nonconvex in nature. We prove that 1) Tubal-Alt-Min guarantees exponential convergence to the global optima, and 2) for an $nimesnimesk$ tensor with tubal-rank $rlln$, the required sampling complexity is $O(n{r}^{2}klo{g}^{3}n)$ and the computational complexity is $O(n^{2}r{k}^{2}lo{g}^{2}n)$. Third, on both synthetic data and real-world video data, evaluation results show that compared with tensor-nuclear norm minimization (TNN-ADMM), Tubal-Alt-Min improves the recovery error dramatically (by orders of magnitude). It is estimated that Tubal-Alt-Min converges at an exponential rate $10^{-0.4423extIter}$ where $extIter$ denotes the number of iterations, which is much faster than TNN-ADMM's $10^{-0.0332extIter}$, and the running time can be accelerated by more than $5$ times for a $200imes200imes20$ tensor.

Recommendations

• Tensor completion and low-\(n\)-rank tensor recovery via convex optimization
• Low tubal rank tensor completion based on singular value factors
• Tensor completion using total variation and low-rank matrix factorization
• Low-rank matrix completion using alternating minimization
• Low-CP-rank tensor completion via practical regularization
• Low-rank tensor completion by Riemannian optimization
• Tensor \(N\)-tubal rank and its convex relaxation for low-rank tensor recovery
• Tensor Factorization for Low-Rank Tensor Completion
• Recovering low CP/Tucker ranked tensors, with applications in tensor completion
• Alternating direction method of multipliers for generalized low-rank tensor recovery

Cited in

(17)

• Tensor \(N\)-tubal rank and its convex relaxation for low-rank tensor recovery
• Robust tensor recovery with nonconvex and nonsmooth regularization
• Tensor completion via a generalized transformed tensor t-product decomposition without t-SVD
• Low-CP-rank tensor completion via practical regularization
• Low tubal rank tensor recovery using the Bürer-Monteiro factorisation approach. Application to optical coherence tomography
• Regularized high dimension low tubal-rank tensor regression
• One-bit tensor completion via transformed tensor singular value decomposition
• Tensor completion based on triple tubal nuclear norm
• Stable als approximation in the TT-format for rank-adaptive tensor completion
• Parallel matrix factorization for low-rank tensor completion
• Proximal gradient algorithm for nonconvex low tubal rank tensor recovery
• Variants of alternating least squares tensor completion in the tensor train format
• Low tubal rank tensor completion based on singular value factors
• Iterative tensor eigen rank minimization for low-rank tensor completion
• A regularized low tubal-rank model for high-dimensional time series data
• Robust completion for rank-1 tensors with noises
• Low tubal-rank tensor recovery with adversarial sparse noises

This page was built for publication: Low-Tubal-Rank Tensor Completion Using Alternating Minimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5123815)