Quaternion Nonlinear Transform-Induced Nuclear Norm for Low-Rank Tensor Completion
Authors: Biswarup Karmakar, Ratikanta Behera
Organizations: Department of Computational and Data Sciences, Indian Institute of Science, Bangalore, 560012, India
Abstract
Tensor completion has emerged as a powerful framework for recovering missing data in multidimensional signals by exploiting low-rank tensor structures. Among existing approaches, linear transform-based tensor nuclear norm (TNN) methods have achieved considerable success by enforcing low-rankness on transformed frontal slices. However, the low-rank structure revealed by linear transforms remains inherently limited. To better capture intrinsic correlations, nonlinear transform-based TNN (NTTNN) models have been proposed, significantly enhancing low-rank representation through composite transforms. Despite their effectiveness, existing NTTNN methods are restricted to real-valued tensors and fail to model quaternion-valued data, which are essential for preserving inter-channel dependencies in color images and videos. Extending nonlinear TNN models to the quaternion domain is challenging due to the non-commutativity of quaternion multiplication and the complexity of quaternion singular value decomposition. To address the limitations encountered in prior works, we propose a quaternion nonlinear transform-induced tensor nuclear norm (QNTTNN) via a real embedding of quaternions, enabling tractable nuclear norm definitions and efficient optimization. Building upon QNTTNN, we formulate a quaternion tensor completion model and develop a proximal alternating minimization algorithm with rigorous convergence guarantees. Extensive experiments on benchmark color video inpainting datasets validate the superior performance of the proposed method over existing approaches.
The recently established Convolution Nuclear Norm Minimization (CNNM) addresses the problem of \textit{tensor completion with arbitrary sampling} (TCAS), which involves restoring a tensor from a subset of its entries sampled in an arbitrary manner. Despite its promising performance, the optimization procedure of CNNM needs performing Singular Value Decomposition (SVD) multiple times, which is computationally expensive and hard to parallelize. To address the issue, we reformulate the optimization objective of CNNM from the perspective of convolution eigenvectors. By introducing pre-learned convolution eigenvectors which are shared among different tensors, we propose a novel method called Inductive Convolution Nuclear Norm Minimization (ICNNM), which bypasses the SVD step so as to decrease significantly the computational time. In addition, due to the extra prior knowledge encoded in the pre-learned convolution eigenvectors, ICNNM also outperforms CNNM in terms of recovery performance. Extensive experiments on video completion, prediction and frame interpolation verify the superiority of ICNNM over CNNM and several other competing methods.
We consider a novel algorithm, for the completion of partially observed low-rank tensors, as a generalization of matrix completion. The proposed low-rank tensor completion (TC) method builds on the conventional nuclear norm (NN) minimization-based low-rank TC paradigm, by leveraging the alternating direction method of multipliers (ADMM) optimization framework. To that extend the original NN minimization problem is reformulated into multiple subproblems, which are then solved iteratively via closed-form proximal operators, making use of over-relaxation and an adaptive penalty parameter update scheme, to further speed up convergence and improve the overall performance of the method. Simulation results demonstrate the superior performance of the new method in terms of normalized mean square error (NMSE), compared to the conventional state-of-the-art (SotA) techniques, including NN minimization approaches, as well as a mixture of the latter with a matrix factorization approach, while its convergence can be significantly improved by initializing the algorithm with the solution of the SotA.
Niclas Führling, Getuar Rexhepi, Giuseppe Thadeu Freitas de Abreu
This paper addresses low-rank tensor completion (LRTC) by proposing a novel nonconvex surrogate, namely the ratio of the tensor nuclear norm to the tensor Ky Fan p-k norm (TNPK), to accurately approximate the tensor tubal rank. The TNPK possesses appealing properties, including scale invariance, parameter flexibility, and the existence of closed-form solutions under specific choices of p and k. With specific parameter settings of p and k, it reduces to the ratio of the tensor nuclear norm to the tensor Ky Fan k norm (TNK) or the ratio of the tensor nuclear norm to the tensor Frobenius norm (TNF). We construct a LRTC model and, under the tensor null space property (NSP), prove that low-rank tensors are local minimizers of the proposed model. Moreover, we derive the proximal operator of the Ky Fan p-k inverse-norm and further develop an efficient alternating direction method of multipliers (ADMM) algorithm with guaranteed subsequential convergence under mild conditions. Extensive experiments on synthetic and real-world datasets validate the superior performance of our method against state-of-the-art competitors.