Robust Tensor Completion via Reflective Convolution Nuclear Norm Minimization

Weiguo Zhou; Feng Zhang; Wenjin Qin; Jianwen Huang

cs.CVOct 4, 2026

Robust Tensor Completion via Reflective Convolution Nuclear Norm Minimization

Authors: Weiguo Zhou, Feng Zhang, Wenjin Qin, Jianwen Huang

Organizations: School of Mathematics and Statistics, Southwest University, Chongqing, 400715, China · College of Artificial Intelligence and Advanced Interdisciplinary Sciences, Chongqing Normal University, Chongqing, 401331, China

Abstract

Robust tensor completion recovers multidimensional data from partial observations corrupted by sparse gross errors. Existing convolutional low-rank models typically construct translated copies using circular continuation, which introduces artificial wrap-around neighborhoods for finite nonperiodic data. We propose reflective convolution nuclear norm minimization (RCNNM), which replaces circular shifts with endpoint-nonrepeating reflection. The resulting lifting has nonuniform entry multiplicities and satisfies a weighted Gram identity that supports both the recovery analysis and the optimization method. Under random sampling and sparse corruption, we establish high-probability exact recovery of the underlying tensor and sparse errors, together with stability under bounded dense perturbations. We further develop a two-block ADMM with a closed-form entrywise tensor update, while singular-value thresholding is implemented through the smaller right Gram matrix. Experiments on synthetic tensors, BSDS color images, and CAVE multispectral images show that RCNNM consistently improves over its circular-lifting counterpart, with the clearest gains near image boundaries. In particular, average boundary-PSNR improvements reach 3.26 dB while global reconstruction quality remains competitive.

Figures & tables

Figure 1: Empirical phase-transition results. Each grid value is the fraction of successful recoveries over 10 independent trials as a function of lifted rank $r$ and corruption probability $\gamma$ , shown for different sampling probabilities $p$ . A trial is counted as successful when $\mathrm{RSE}<10^{-2}$ .

Figure 2: Kernel-size sensitivity on Flower with

\mathrm{SR}=0.4

and

\gamma=0.1

under random missing. PSNR, SSIM, and running time are shown for

[k,k,3]

kernels with

k=1,\ldots,9

; the selected setting

k=7

is highlighted.

Figure 3: Parameter selection and PSNR sensitivity. (a) Optimal

\lambda

over the

(\gamma,\mathrm{SR})

grid. (b) PSNR versus

\mathrm{SR}

and

\lambda

\gamma=0.20

. (c) PSNR versus

\gamma

and

\lambda

\mathrm{SR}=0.80

Panel of Figure 4 — Figure 4: Convergence behavior of RCNNM at $\mathrm{SR}=0.3$ and $\gamma=0.1$ . PSNR and RSE are shown versus iteration under random-valued and salt-and-pepper corruption.

Table 5

Figure 5: Visual comparison on three representative BSDS images at $\mathrm{SR}=0.6$ and $\gamma=0.1$ . From top to bottom: Bear with random missing, Butterfly with scratch missing, and Flower with grid missing. Values are PSNR/SSIM.

$\gamma$	Missing	$\mathrm{SR}$	TNN	SNN	LNOP	FTNN	TTNN	NCRTC	GTNLN	CNNM	RCNNM
0.1	Random	0.4	22.16/0.752	22.53/0.829	22.35/0.688	22.35/0.763	22.86/0.781	23.81/0.845	25.83/0.861	26.36 / 0.876	26.66 / 0.879
		0.6	24.87/0.849	24.48/0.834	24.74/0.794	25.05/0.854	25.54/0.863	26.48/0.868	27.82 /0.909	27.70/ 0.910	28.19 / 0.915
		0.8	27.40/0.909	26.36/0.865	27.07/0.872	27.57/0.912	28.06/0.915	28.64/0.881	29.70 / 0.938	29.43/0.937	29.96 / 0.940
	Scratch	0.4	21.58/0.828	8.29/0.164	15.56/0.327	8.55/0.158	8.70/0.166	8.39/0.164	27.00 / 0.891	26.53/0.888	27.25 / 0.895
		0.6	25.00/0.846	18.09/0.361	25.28/0.813	24.39/0.800	25.10/0.824	25.33/0.664	28.62/ 0.923	28.99 /0.913	29.47 / 0.915
		0.8	27.35/0.908	25.37/0.664	27.04/0.871	26.84/0.871	27.55/0.888	27.69/0.762	29.74/ 0.940	30.30 /0.935	30.86 / 0.938

Table 3: Mean global reconstruction results on five BSDS color images. Each method entry reports PSNR/SSIM; PSNR is in dB.

Panel of Figure 6 — Figure 6: Boundary-region comparison on Goose (top) and House (bottom). The enlarged boundary regions correspond to the central one-third segment of each image edge. Values are PSNR/BPSNR in dB; BPSNR is computed on the five-pixel boundary strip.

Pattern	$\mathrm{SR}$	TNN	SNN	LNOP	FTNN	TTNN	NCRTC	GTNLN	CNNM	RCNNM
Random	0.5	28.05/0.4910	29.48/0.5899	30.26 /0.7705	29.21/0.6906	29.33/0.7146	26.55/0.7653	29.03/0.8329	29.97/ 0.8678	30.97 / 0.8840
	0.6	26.70/0.4051	30.31/0.6354	31.09 /0.7903	23.27/0.2450	30.16/0.7428	27.77/0.7994	31.09 /0.8665	30.89/ 0.8872	31.33 / 0.8985
	0.7	25.50/0.3470	31.22/0.6742	31.82/0.8070	22.18/0.2128	31.38/0.7170	29.18/0.8224	32.30 / 0.9047	31.40/0.8805	32.24 / 0.8896
Scratch	0.5	24.34/0.4045	25.04/0.3340	26.13/0.6120	24.28/0.2452	24.97/0.5186	23.63/0.4485	23.44/0.5113	29.17 / 0.8416	29.63 / 0.8573
	0.6	25.26/0.4140	27.56/0.4367	27.20/0.6409	24.31/0.2255	29.98/0.6725	25.71/0.5126	28.08/0.7119	30.22 / 0.8256	30.85 / 0.8523
	0.7	26.65/0.4578	30.40/0.5843	28.26/0.6713	23.86/0.2104	32.06 /0.8135	28.66/0.6456	30.36/0.7712	31.54/ 0.8528	31.70 / 0.8504

Table 5: Mean global reconstruction results on three CAVE multispectral images with

\gamma=0.2

. Each method entry reports PSNR/SSIM; PSNR is in dB.

Explore similar work

Apr 18, 2026

Inductive Convolution Nuclear Norm Minimization for Tensor Completion with Arbitrary Sampling

The recently established Convolution Nuclear Norm Minimization (CNNM) addresses the problem of 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.

Wei Li, Yuyang Li, Kaile Du +2

The authors are with the School of Automation, Southeast University, Nanjing, China 210018.

Tensor Completion Tensor Decomposition Nuclear Norm Minimization

Ask PDF

May 5, 2026

Low Rank Tensor Completion via Adaptive ADMM

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

School of Computer Science and Engineering, Constructor University, Bremen, Germany

Tensor Completion Nuclear Norm Minimization Alternating Direction Method of Multipliers Low-Rank Approximation

Ask PDF

Jun 17, 2026

Low-Rank Tensor Completion Based on Fractional Regularization with Ky Fan p-k Norm

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.

Shan Fan, Feng Zhang, Jianjun Wang +2

School of Mathematics and Statistics, Southwest University, Chongqing 400715, China · School of Mathematical Sciences/Research Center for Image and Vision Computing, University of Electronic Science and Technology of China, Chengdu 611731, China · Faculty of Computer Science and Control Engineering, Shenzhen University of Advanced Technology, Shenzhen 518055, China

Tensor Completion Nonconvex Optimization Low-Rank Approximation

Ask PDF