PaperlayerView exact revision on arXiv

Source-linked AI summary

Guaranteed Tensor Recovery Fused Low-rankness and Smoothness

Hailin Wang, Jiangjun Peng, Wenjin Qin, Jianjun Wang, Deyu Meng

arXiv:2302.02155v1cs.LGcs.AIcs.CVstat.ML

TL;DR

Tensor recovery methods combining low-rankness and smoothness lacked theoretical exact-recovery guarantees. This paper introduces t-CTV, a single regularizer that fuses both priors, and proves guarantees for tensor completion and TRPCA. Experiments report improved recovery, including workable color-image inpainting with 99.5% missing pixels.

  • Problem

    Joint low-rankness-and-smoothness tensor recovery models lacked theoretical exact-recovery guarantees, unlike pure low-rank models.

  • Method

    The paper introduces t-CTV, a single high-order t-SVD-based regularizer that simultaneously encodes low-rankness and smoothness without a balancing parameter.

  • Results

    The method provides exact-recovery guarantees for tensor completion and TRPCA and improves recovery accuracy across visual tensor tasks, including at 99.5% missing pixels.

  • Takeaways & Limitations

    The proposed fused regularizer offers a theoretically guaranteed approach for joint low-rank-and-smooth tensor recovery in the studied tasks.

  • Takeaways & Limitations

    The proof requires specialized high-order t-SVD analysis, including difference transformations and low-rankness properties of gradient tensors.

Abstract

from arXiv · show

The tensor data recovery task has thus attracted much research attention in recent years. Solving such an ill-posed problem generally requires to explore intrinsic prior structures underlying tensor data, and formulate them as certain forms of regularization terms for guiding a sound estimate of the restored tensor. Recent research have made significant progress by adopting two insightful tensor priors, i.e., global low-rankness (L) and local smoothness (S) across different tensor modes, which are always encoded as a sum of two separate regularization terms into the recovery models. However, unlike the primary theoretical developments on low-rank tensor recovery, these joint L+S models have no theoretical exact-recovery guarantees yet, making the methods lack reliability in real practice. To this crucial issue, in this work, we build a unique regularization term, which essentially encodes both L and S priors of a tensor simultaneously. Especially, by equipping this single regularizer into the recovery models, we can rigorously prove the exact recovery guarantees for two typical tensor recovery tasks, i.e., tensor completion (TC) and tensor robust principal component analysis (TRPCA). To the best of our knowledge, this should be the first exact-recovery results among all related L+S methods for tensor recovery. Significant recovery accuracy improvements over many other SOTA methods in several TC and TRPCA tasks with various kinds of visual tensor data are observed in extensive experiments. Typically, our method achieves a workable performance when the missing rate is extremely large, e.g., 99.5%, for the color image inpainting task, while all its peers totally fail in such challenging case.

1 INTRODUCTION

Tensor recovery addresses degraded multidimensional data by exploiting low-rankness and smoothness, but conventional joint models lacked exact-recovery guarantees. This work introduces t-CTV, a single regularizer with theoretical guarantees and stronger empirical recovery, including at 99.5% missing pixels.

  • Problem: Tensor recovery reconstructs unknown multidimensional data from observations degraded by information loss or noise.These degradations correspond to tensor completion and tensor robust principal component analysis.
  • Existing priors: Low-rankness captures global correlations, while smoothness captures local continuity between adjacent tensor elements.Existing visual-tensor methods commonly combine these priors through separate regularization terms.
  • Research gap: Joint low-rankness-and-smoothness models improved recovery but lacked theoretical exact-recovery guarantees and depended strongly on a balancing parameter.Pure low-rank models had established exact-recovery theory, unlike the related joint models.
  • Proposed method: The proposed t-CTV regularizer encodes low-rankness and smoothness simultaneously as one term under the high-order t-SVD framework.Its single-term formulation removes the conventional balancing parameter between separate priors.
  • Theory: Exact-recovery guarantees are proved for t-CTV-based tensor completion and tensor robust principal component analysis under mild tensor incoherence assumptions.The authors describe these as the first theoretical exact-recovery guarantees among related joint low-rankness-and-smoothness studies.
  • Experiments: 99.5% missing pixels still yielded workable color-image inpainting, while competing methods largely failed in the same extreme case.Experiments also report stronger recovery than baseline low-rank and joint low-rank-plus-smoothness methods across visual tensor tasks.

2 RELATED WORKS

Prior tensor-recovery work developed low-rank methods and later combined low-rankness with total variation for visual data. The paper positions t-CTV as a fused alternative that avoids separate low-rank and smoothness regularizers and their trade-off parameter.

  • Recovery tasks: Tensor completion recovers a low-rank tensor from partial entries, whereas TRPCA recovers tensors from grossly corrupted observations.These are presented as two common tensor recovery tasks.
  • Recovery tasks: TRPCA models corruption with an L1-norm noise term and a positive trade-off parameter.The corruption component is denoted by E in the stated model.
  • Low-rank recovery: Low-rank tensor recovery has used Tucker-based methods, SNN, and t-SVD-based frameworks because tensor rank is not uniquely defined.The t-SVD framework avoids matricization and provides an optimality property for low-rank representation.
  • Smoothness modeling: Visual tensor methods commonly model smoothness with total variation, including anisotropic and isotropic forms based on neighbor differences.TV variants are adapted to the type of visual data being restored.
  • Joint priors: Existing joint methods typically sum low-rank and smoothness regularization terms in visual tensor restoration.Examples combine STV or TV-1 with low-rank formulations such as matrix factorization or SNN.
  • Proposed direction: t-CTV fuses both priors under high-order t-SVD, providing exact-recovery guarantees for the considered TC and TRPCA models without a conventional trade-off parameter.The fused formulation is presented as an alternative to previous separate L+S terms.

3 HIGH-ORDER T-SVD FRAMEWORK

The high-order t-SVD framework represents tensors through transform-domain slice operations, enabling tensor products, decompositions, rank notions, nuclear norms, and optimal low-rank approximation.

  • Transform and tensor product: An invertible multilinear transform maps a tensor into a transform domain, where tensor operations can be computed through face-wise matrix products and inverse transformation.The framework accommodates transforms such as DFT and DCT.
  • t-SVD decomposition: The t-SVD decomposes any order-d tensor into orthogonal tensors and an f-diagonal singular value tensor.The decomposition is written using the transform-based tensor-tensor product.
  • Rank and nuclear norm: The t-SVD rank counts the nonzero singular-value tubes, while the tensor nuclear norm provides a corresponding low-rank surrogate.The rank is defined as the cardinality of indices whose singular-value tubes are nonzero.
  • Thresholding: Tensor singular value thresholding applies soft thresholding to transform-domain singular values before reconstructing the tensor.This operation is defined directly from the t-SVD factors and the inverse transform.
  • Optimality: The rank-k t-SVD truncation is the best Frobenius-norm approximation among tensors with t-SVD rank k, extending low-rank approximation directly to tensors.The framework also compares this tensor approximation with rank-k approximations of unfolding matrices.

4 TENSOR CORRELATED TOTAL VARIATION

Tensor correlated total variation (t-CTV) is a gradient-domain regularizer designed to encode low-rankness and smoothness together. Its construction links low-rank gradient tensors with small discrete derivatives, while its geometry resembles both TNN and TV constraints.

  • Gradient modeling: Gradient tensors are formed by applying a mode-specific first-order difference operator, with smoothness directions selected according to the tensor data type.Images use spatial directions, while HSIs and color videos can additionally use spectral or temporal directions.
  • Fused prior: Existing approaches typically sum separate low-rank and smoothness regularizers, whereas t-CTV fuses both priors into one term on correlated gradient tensors.The proposed formulation reflects the observed coexistence of low-rankness and smoothness in visual tensor data.
  • Low-rankness encoding: Constraining the TNN of gradient tensors indirectly promotes low-rankness in the original tensor because their t-SVD ranks satisfy R − 1 ≤ rank_t-SVD(G_k) ≤ R.Here R is the t-SVD rank of the original tensor and G_k is its gradient tensor.
  • Smoothness encoding: Because t-CTV is defined in the gradient domain, it controls discrete first-order derivative energy and therefore promotes smoothness similarly to total variation.The t-CTV and TV norms are compatible up to rank-dependent bounds and both decrease as tensors become smoother.
  • Geometric interpretation: The t-CTV manifold resembles the TV manifold while sharing characteristics with the TNN manifold, indicating joint constraints on smoothness and low-rankness.The comparison is illustrated using a 2×2×2 tensor manifold construction.
  • Empirical role: Although t-CTV is not the unique encoding of either prior, the paper reports better joint low-rank and smooth tensor recovery than pure-L, pure-S, and existing L+S models.The stated comparison is deferred to the experiments.

5 TENSOR RECOVERY VIA T-CTV MINIMIZATION

The t-CTV regularizer jointly represents tensor low-rankness and smoothness, supporting exact-recovery guarantees for tensor completion and TRPCA under stated conditions. Its theoretical sampling bound exploits the interaction between both priors, while TRPCA recovery also admits a universal trade-off parameter.

  • Tensor completion: The t-CTV tensor-completion model targets exact recovery under Bernoulli sampling and gradient tensor incoherence conditions.Theorem 4 states uniqueness with high probability under a stated sampling bound.
  • Model formulation: t-CTV uses one regularizer to promote tensor low-rankness and smoothness simultaneously under the high-order t-SVD framework.The regularizer is constructed from tensor nuclear norms imposed on related gradient tensors.
  • Tensor completion: t-CTV tensor completion requires sampling complexity approximately O(µRn(1)n3 · · · nd log2(n(1)ℓ)/ℓ), differing from pure low-rank complexity by a logarithmic factor.The bound is presented for tensors with t-SVD rank R.
  • Main theoretical comparison: The t-CTV lower bound is a product interaction of low-rankness and smoothness, and is rigorously lower than pure-L, pure-S, and linear-combination L+S bounds for jointly structured tensors.Lower rank and smoothness ratios imply a lower information bound for t-CTV.
  • TRPCA: The t-CTV TRPCA model exactly recovers a jointly low-rank and smooth tensor with sparse noise under incoherence and uniformly distributed support assumptions.Theorem 6 provides high-probability uniqueness under stated parameter conditions.
  • TRPCA: TRPCA uses the universal trade-off parameter λ = 1/pn(1)ℓ, making the model parameter-free and easier to implement.The parameters ρr and ρs determine the tensor rank and noise sparsity, respectively.

6 OPTIMIZATION ALGORITHMS

The paper solves both t-CTV recovery models with ADMM, using auxiliary variables and multiplier updates to separate tensor differences, missing entries, and sparse corruption. The algorithms have stated per-iteration complexities, and their convergence is justified by an equivalent two-block ADMM formulation.

  • ADMM formulation: The t-CTV tensor-completion and TRPCA models are optimized using the Alternating Direction Method of Multipliers framework.The TRPCA formulation replaces the missing-entry auxiliary variable with a sparse component and an ℓ1 penalty.
  • Tensor completion: For tensor completion, ADMM alternates updates of T, gradient auxiliaries Gk, missing-entry compensation K, and Lagrange multipliers.The penalty parameter is increased geometrically through µt+1 = ρµt.
  • Tensor completion: FFT diagonalizes the difference operators, enabling an efficient solution of the tensor update through the convolution theorem.The difference operation is treated as linear under the tensor-tensor product.
  • Complexity: Each algorithm has per-iteration complexity O(n1 · · · nd log(n1 · · · nd) + n1n2(n3 · · · nd)2 + n(1)n2(2)n3 · · · nd).The TRPCA algorithm has the same order because soft-thresholding costs O(n1 · · · nd).
  • Convergence: Although the methods use multi-block ADMM, separable linear constraints permit an equivalent standard two-block form with convergence inherited from two-block ADMM theory.The stated convergence covers residuals, objective values, and variables.

7 EXPERIMENTAL RESULTS

Experiments on synthetic and visual tensors evaluate t-CTV for exact recovery, phase transitions, inpainting, video recovery, hyperspectral imaging, and denoising. Across these settings, the reported results show accurate recovery, broader recovery regions, and strong performance under severe missingness, structured masks, and noise.

  • Synthetic simulations: t-CTV-TC achieves accurate recovery with correct rank estimation and RelErr≤10^-5 across tested synthetic tensors and DFT, DCT, and DOT transforms.The tests vary tensor dimensions, t-SVD ranks, and sampling quantities.
  • Synthetic simulations: t-CTV-TRPCA recovers synthetic tensors with accurate rank and sparsity estimates and tiny errors, verifying the stated exact-recovery guarantees.The experiments use varying dimensions, ranks, and sparse-tensor settings.
  • Phase transitions: t-CTV-TC recovers more phase-transition cases than TNN and TNN+TV while avoiding TNN+TV’s trade-off-parameter tuning.The TC phase transitions vary t-SVD rank and sampling rate, with success defined by average RelErr below 0.05.
  • Phase transitions: 32.87% correct area ratio gives t-CTV-TRPCA the best phase-transition recovery among the compared methods, while remaining parameter-free and theoretically guaranteed.This exceeds the reported TNN and TNN+TV baselines in the tested phase-transition experiment.
  • Visual data inpainting: The proposed t-CTV method achieves the best average color-image inpainting performance across evaluated metrics and sampling rates, with stronger advantages at low sampling rates.Its average runtime is in the same order of magnitude as several competing methods and faster than several others.
  • Visual data inpainting: At 0.5% sampling, with 99.5% of pixels missing, t-CTV retains workable color-image recovery while competing methods fail to a large extent.The experiments also test 5%, 2%, and 1% sampling rates.
  • Visual data inpainting: t-CTV handles structured missing masks such as dead lines, wave lines, star patterns, and text patterns, outperforming competing methods visually.The reported comparison notes that several pure low-rank methods become invalid for whole-row or whole-column missing regions.
  • Visual data recovery: t-CTV leads competing methods on color-video PSNR across tested sampling levels and on detailed recovery results at 10% sampling.The experiment uses ten color-video sequences.

8 CONCLUSION

The conclusion presents t-CTV as a single regularizer that combines low-rankness and smoothness and supports exact-recovery theory for tensor completion and robust PCA. It also reports lower sampling complexity and workable recovery at 0.5% sampling, while identifying broader tasks and theories as future work.

  • Contribution: t-CTV encodes low-rankness and smoothness in one concise regularization term and yields theoretical exact-recovery guarantees for TC and TRPCA.The paper identifies this as its first theoretical exact-recovery result for the related L+S-prior modeling line.
  • Conclusion: The proposed L+S modeling has a lower sampling complexity bound than conventional low-rankness-only or smoothness-only models.Experiments across practical visual tensor data are reported as validating this claim.
  • Conclusion: At 0.5% sampling, t-CTV obtains an acceptable recovery effect while competing methods fail in the reported extreme case.The conclusion presents this as evidence of the regularizer’s reliability and potential usefulness.
  • Future work: Future work will test t-CTV on outlier detection and background extraction and develop targeted theory and extensions under other matrix or tensor transformations.These directions are stated as planned further investigations.
Loading 2302.02155v1…