Kronecker-Structured Video Completion with Cross-Fitted Self-Supervised Residual Learning

Qi Qi; Yanfei Wang; Yanjun Cui; Jun-e Feng

cs.CVOct 26, 2026

Kronecker-Structured Video Completion with Cross-Fitted Self-Supervised Residual Learning

Authors: Qi Qi, Yanfei Wang, Yanjun Cui, Jun-e Feng

Organizations: Mathematical Research Center, Shandong University, Jinan 250100, China · School of Mathematics, Shandong University, Jinan 250100, China · Dartmouth College, Hanover, NH 03755, USA · Semi-tensor Product of Matrices: Theory and Applications, School of Mathematics and Systems Science, Liaocheng University, Liaocheng 252000, China

Abstract

Tube-wise video completion reconstructs temporal trajectories at spatial locations unobserved in every frame. We propose a two-stage framework combining regularized masked Kronecker product decomposition (KPD) with cross-fitted self-supervised residual learning. First, we estimate a compact structural backbone directly from observed entries using cyclic component-wise least-squares updates, spatial and temporal factor regularization, and regularizer-optimal scale balancing. The exact updates yield a nonincreasing objective. Second, we address the mismatch between in-sample fitting errors and the prediction errors encountered at missing tubes. We partition observed tubes into folds and construct residual targets using backbone models fitted without the corresponding target tubes. A lightweight 3-D convolutional neural network then predicts corrections from the backbone, visible residual context, observation mask, and local detail features. Exact data consistency preserves observed measurements. Experiments include ablations, sensitivity analysis, grayscale and RGB video completion, and structured missing patterns. Our method achieves the highest mean PSNR and SSIM at the higher tested sampling rates on the grayscale benchmark. On eight selected DAVIS RGB sequences, it achieves the highest mean missing-region PSNR and full-frame SSIM and the lowest mean missing-tube temporal-gradient MAE at every evaluated sampling rate.

Figures & tables

Panel of Figure 1 — Fig. 1: Fidelity–storage tradeoff of four low-rank representation families on the three development sequences (Akiyo, Foreman, and Mobile): (a) average approximation PSNR and (b) average approximation SSIM versus the normalized storage ratio in ( 18 ). For each method, the sequence-level curves are averaged only over the storage interval shared by all three videos. Stars mark the $K=4$ KPD-backbone operating point used in the completion experiments.

Fig. 2: Proposed structure–residual video-completion framework. Stage I fits a compact KPD backbone directly to the observed entries. Stage II constructs cross-fitted residual supervision, predicts the missing-tube correction with a lightweight 3-D CNN, and applies exact data consistency to obtain

\widehat{\mathcal{X}}

Parameter	23-video grayscale	DAVIS 360p RGB
KPD rank $K$	$4$	$12$
Masked KPD sweeps $S$	$12$	same
Spatial penalty $\lambda_{s}$	$5\times 10^{-3}$	same
Temporal penalty $\lambda_{t}$	$5\times 10^{-2}$	same
Tikhonov $\lambda_{0}$	$10^{-5}$	same
Cross-fitting folds $F$	$5$	same

TABLE I: Fixed hyperparameter configurations for the grayscale and DAVIS RGB benchmarks. Parameters marked as “same” use the grayscale setting.

Method	Akiyo	Foreman	Mobile	Val. MAE $\downarrow$	Avg. PSNR $\uparrow$	Avg. SSIM $\uparrow$
KPD	22.989/0.5589	19.348/0.4286	16.002/0.3591	0.092783	19.446	0.4488
Simple	24.801/0.6565	25.462/0.7554	19.050/0.5687	0.056637	23.104	0.6602
Direct	26.280/0.7282	25.539/0.7670	20.464/0.6998	0.049610	24.095	0.7317
CrossFit	26.972/0.7465	25.771/0.7859	20.397/0.6936	0.047503	24.380	0.7420

TABLE II: Residual-supervision ablation at

\mathrm{SR}=0.2

and

K=4

. Sequence entries are full-video PSNR/frame-wise full-frame SSIM; validation MAE is averaged over the three development sequences. Best and second-best results are bold and underlined.

Fig. 3: Stage-wise visual ablation at $\mathrm{SR}=0.3$ : ground truth, observed input, KPD backbone, simple residual propagation, and CrossFit reconstruction. A common ROI is enlarged within each sequence.

Input	Val. MAE $\downarrow$	PSNR $\uparrow$	SSIM $\uparrow$	$\Delta$ PSNR
B	0.092944	19.360	0.4561	–
BR	0.060328	22.354	0.6447	+2.994
BRM	0.050618	23.944	0.7073	+1.590
FULL	0.047503	24.380	0.7420	+0.436

TABLE III: Residual-network input ablation on the three development sequences at

\mathrm{SR}=0.2

. PSNR is computed over the full reconstructed video and SSIM is averaged frame-wise over the full frames.

Method	SR=0.1		SR=0.2		SR=0.3		SR=0.4		SR=0.5		Avg. Time (s) $\downarrow$
Method	PSNR $\uparrow$	SSIM $\uparrow$	PSNR $\uparrow$	SSIM $\uparrow$	PSNR $\uparrow$	SSIM $\uparrow$	PSNR $\uparrow$	SSIM $\uparrow$	PSNR $\uparrow$	SSIM $\uparrow$	Avg. Time (s) $\downarrow$
DRO-TFF [ 40 ]	15.091	0.1628	18.804	0.3365	22.227	0.5120	24.787	0.6381	27.010	0.7389	7.79
HLRTF [ 35 ]	20.887	0.4819	23.626	0.6408	25.565	0.7290	26.987	0.7757	28.425	0.8209	7.17
KBR [ 30 ]	17.867	0.3324	21.009	0.5127	24.428	0.6759	27.880	0.8134	30.010	0.8993	154.21
LRTFR [ 39 ]	21.793	0.5238	24.549	0.6893	26.419	0.7784	28.011	0.8378	29.597	0.8807	7.38
OTLRM [ 41 ]	19.805	0.4408	24.052	0.6616	25.194	0.7195	26.664	0.7809	28.653	0.8436	80.91

TABLE IV: Average PSNR/SSIM on the 23-video benchmark at five tube sampling rates, with mean wall-clock time per sequence. Best and second-best values are bold and underlined.

Panel of Figure 8 — Fig. 4: Visual comparison at $\mathrm{SR}=0.3$ on Foreman and Mobile. Common frames and ROIs show detail recovery in both sequences.

Fig. 5: Sensitivity on the three grayscale development sequences at $\mathrm{SR}=0.2$ : (a) KPD rank, (b) cross-fitting folds, (c) optimization steps, (d) spatial regularization, and (e) temporal regularization. Stars mark the selected settings.

Panel of Figure 10 — Fig. 6: Qualitative RGB comparison on DAVIS 2017 at $\mathrm{SR}=0.3$ for three representative sequences: Bear, Drift-chicane, and Cows. Each row uses fixed ROIs across methods. PSNR values are computed over the missing tubes of the full sequence.

Fig. 7: Mean PSNR, SSIM, and missing-tube temporal-gradient MAE (T-MAE) versus sampling rate for (a) the 23-video grayscale benchmark and (b) eight selected DAVIS 360p RGB sequences. Thick lines identify Ours. T-MAE measures the error in frame-to-frame intensity differences at missing tubes ( 73 ). DAVIS curves use per-sequence measurements; grayscale curves use the recorded benchmark statistics.

Method	(a) Representative sequences ( $\mathrm{SR}=0.3$ )			(b) Mean over eight sequences
Method	Bear	Drift-chicane	Cows	$\mathrm{SR}=0.2$	$\mathrm{SR}=0.3$	$\mathrm{SR}=0.4$
DRO-TFF [ 40 ]	22.96 / 0.652 0.05461	23.36 / 0.428 0.00883	19.78 / 0.527 0.06434	20.65 / 0.419 0.05233	23.25 / 0.615 0.04917	24.04 / 0.701 0.04842
HLRTF [ 35 ]	24.11 / 0.733 0.05164	29.51 / 0.846 0.00777	21.86 / 0.640 0.06312	23.95 / 0.640 0.04856	25.26 / 0.740 0.04419	25.94 / 0.791 0.04177
KBR [ 30 ]	25.99 / 0.811 0.04833	27.95 / 0.750 0.00707	24.29 / 0.765 0.05631	25.06 / 0.691 0.04038	27.34 / 0.814 0.03505	28.81 / 0.882 0.03024
LRTFR [ 39 ]	24.01 / 0.732 0.05276	28.31 / 0.792 0.00766	23.40 / 0.724 0.05933	24.06 / 0.664 0.04876	24.89 / 0.744 0.04687	25.58 / 0.806 0.04511
OTLRM [ 41 ]	22.85 / 0.699 0.06662	29.54 / 0.847 0.00808	20.97 / 0.612 0.08274	24.69 / 0.685 0.04926	25.16 / 0.736 0.04853	25.97 / 0.795 0.04510

TABLE V: DAVIS 360p RGB reconstruction results. (a) Three representative sequences at

\mathrm{SR}=0.3

; (b) mean results over eight selected sequences. Each entry reports missing-region PSNR (dB) / full-frame SSIM on the first line and missing-tube temporal-gradient MAE on the second line. Best and second-best results for each metric are bold and underlined, respectively.

Panel of Figure 13 — Fig. 8: Structured-mask RGB visual comparisons on Coastguard and Container: (a) contiguous block and (b) distributed grid missingness. The observed input, reconstructions, and ground truth are shown with common regions of interest for each video and mask.

Method	Mask	Coastguard	Container
DRO-TFF [ 40 ]	Block	15.52 / 0.9447	19.57 / 0.9456
DRO-TFF [ 40 ]	Grid	20.35 / 0.9408	16.69 / 0.9028
HLRTF [ 35 ]	Block	15.97 / 0.9473	20.81 / 0.9639
HLRTF [ 35 ]	Grid	7.46 / 0.8076	4.84 / 0.7848
KBR [ 30 ]	Block	19.74 / 0.9658	23.32 / 0.9762
KBR [ 30 ]	Grid	16.54 / 0.8941	14.89 / 0.9216

TABLE VI: Structured-mask RGB completion on Coastguard and Container (about

6\%

missing tubes). Each result reports missing-region PSNR (dB) / full-frame SSIM. Best and second-best values for each video and mask are bold and underlined, respectively.

Appendix figures & tables22 assets

Supplementary material from the paper’s appendix.

Appendix

Rank $K$	Conv3D kernel $(t,h,w)$	Missing PSNR $\uparrow$	Full SSIM $\uparrow$
$4$	$3\times 3\times 3$	27.1250	0.8510
$4$	$3\times 5\times 5$	27.1250	0.8500
$8$	$3\times 3\times 3$	27.3964	0.8589
$8$	$3\times 5\times 5$	26.7135	0.8393
$12$	$3\times 3\times 3$	27.6069	0.8638
$12$	$3\times 5\times 5$	26.8058	0.8408

Appendix

TABLE I: Rank and spatial-kernel sensitivity on Blackswan (

360\times 640\times 50

, RGB;

\mathrm{SR}=0.3

). The hidden width and training budget are fixed at

h=12

and

1200

steps.

Fig. 1: Missing-region PSNR versus KPD rank for two spatial convolutional kernel sizes on the designated development sequence. All other settings are fixed as in Table I .

Rank $K$	Width $h$	Missing PSNR $\uparrow$	Full SSIM $\uparrow$	Time (s)
$12$	$12$	27.6069	0.8638	832.7
$12$	$24$	27.7573	0.8722	833.5
$12$	$32$	27.8172	0.8734	833.3
$16$	$12$	27.5599	0.8616	1088.5
$20$	$12$	27.6258	0.8626	1344.0
$24$	$12$	27.5880	0.8610	1594.7

Appendix

TABLE II: KPD-rank and CNN-width sensitivity on Blackswan at

\mathrm{SR}=0.3

, with a

3\times 3\times 3

kernel and

1200

steps. Reported runtimes are measured end to end for each video (seconds).

Setting	Steps	Spatial patch	Missing PSNR $\uparrow$	Full SSIM $\uparrow$
A0	1200	$48\times 48$	27.8172	0.8734
S2	2400	$48\times 48$	28.2571	0.8884
P64	2400	$64\times 64$	28.6947	0.8976
P96	2400	$96\times 96$	28.7211	0.8997
S3	3600	$48\times 48$	28.8627	0.9027
C1	3600	$64\times 64$	28.8469	0.9018

Appendix

TABLE III: Training-budget and patch-size study on Blackswan at

\mathrm{SR}=0.3

;

K=12

h=32

, and a

3\times 3\times 3

kernel are fixed. All patches have temporal length

16

Fig. 2: Sensitivity to the optimization budget at three training-patch sizes on the development sequence. Curves connect only the evaluated configurations.

Method	Median time (s)
DRO-TFF	98.2
HLRTF	62.6
KBR	2851.5
LRTFR	45.4
OTLRM	434.1
TNN	926.1

Appendix

TABLE IV: Median wall-clock time (seconds) per reconstructed RGB video in the comparison of eight selected sequences. Times are measured using the original CPU/GPU implementations.

Sequence	DRO-TFF	HLRTF	KBR	LRTFR	OTLRM	TNN	SALTS	S 2 NTNN	Ours
bear	18.49	23.21	24.59	23.40	22.46	22.72	24.88	24.31	26.85
drift-chicane	21.87	28.12	23.38	27.24	28.95	26.86	27.33	28.78	29.89
cows	16.16	20.98	22.75	22.61	20.79	19.85	22.80	23.21	24.47
dog	24.78	25.32	29.07	24.47	26.83	23.83	28.55	29.43	29.97
camel	17.06	21.85	22.39	22.68	22.45	20.75	23.93	24.15	24.50
kite-surf	25.26	27.22	30.52	26.92	28.83	26.33	30.33	29.71	30.88

Appendix

TABLE V: Missing-region PSNR (dB) on the eight selected DAVIS RGB sequences at

\mathrm{SR}=0.2