PaperlayerView exact revision on arXiv

Source-linked AI summary

Framelet Representation of Tensor Nuclear Norm for Third-Order Tensor Completion

Tai-Xiang Jiang, Michael K. Ng, Xi-Le Zhao, Ting-Zhu Huang

arXiv:1909.06982v2eess.IVcs.CV

TL;DR

Tensor completion requires effective low-rank modeling despite the difficulty of defining tensor rank and the limitations of Fourier-based transformed representations. The paper replaces the Fourier transform in the t-SVD framework with a redundant framelet transform, formulates convex completion and RPCA models, and solves them using convergent ADMM algorithms. Experiments on videos, multispectral images, MRI, and color images show that the proposed method outperforms many state-of-the-art methods quantitatively and visually.

  • Problem

    Tensor completion needs computable low-rank representations, but tensor rank lacks an exact unique definition and Fourier-based transformed tensors may not be sufficiently low-rank.

  • Method

    The paper replaces the Fourier transform in the t-SVD framework with a redundant framelet transform and minimizes the resulting framelet-based tensor nuclear norm using convex ADMM models.

  • Results

    The proposed method outperforms many state-of-the-art methods quantitatively and visually on MRI, videos, color images, and multispectral images.

  • Takeaways & Limitations

    Framelet redundancy provides a tensor nuclear norm representation that the paper reports as effective for multidimensional data recovery.

Abstract

from arXiv · show

The main aim of this paper is to develop a framelet representation of the tensor nuclear norm for third-order tensor completion. In the literature, the tensor nuclear norm can be computed by using tensor singular value decomposition based on the discrete Fourier transform matrix, and tensor completion can be performed by the minimization of the tensor nuclear norm which is the relaxation of the sum of matrix ranks from all Fourier transformed matrix frontal slices. These Fourier transformed matrix frontal slices are obtained by applying the discrete Fourier transform on the tubes of the original tensor. In this paper, we propose to employ the framelet representation of each tube so that a framelet transformed tensor can be constructed. Because of framelet basis redundancy, the representation of each tube is sparsely represented. When the matrix slices of the original tensor are highly correlated, we expect the corresponding sum of matrix ranks from all framelet transformed matrix frontal slices would be small, and the resulting tensor completion can be performed much better. The proposed minimization model is convex and global minimizers can be obtained. Numerical results on several types of multi-dimensional data (videos, multispectral images, and magnetic resonance imaging data) have tested and shown that the proposed method outperformed the other testing methods.

I. INTRODUCTION

The paper addresses tensor completion by replacing Fourier-based transformations in the t-SVD framework with a redundant framelet transform. It develops convex optimization models and ADMM algorithms, with experiments showing improved recovery across multiple multidimensional data types.

  • Motivation: Tensor completion is challenging because tensor rank lacks an exact unique definition, while CP-rank computation is NP-hard.The paper focuses on computable tensor multi-rank and tubal-rank induced by the t-SVD framework.
  • Existing framework: The conventional tensor nuclear norm applies the DFT along tensor tubes and relaxes the sum of ranks of transformed frontal slices.The transformed tensor is formed through a mode-3 DFT, and its frontal-slice ranks define the tensor multi-rank.
  • Proposed representation: The proposed method replaces the Fourier transform with a redundant framelet transform, yielding sparsely represented tubes and potentially lower transformed multi-rank.The paper motivates this design by expecting smaller sums of matrix ranks when tensor slices are highly correlated.
  • Optimization: Framelet-based tensor nuclear norm models are formulated for low-rank tensor completion and tensor RPCA as convex problems solvable by ADMM with guaranteed convergence.The approach is designed for non-invertible framelet transforms while retaining global minimizers and a theoretical convergence guarantee.

B. Framelet

The paper defines tight wavelet frames and their discrete framelet transform, which is redundant but admits exact reconstruction through the UEP property.

  • A tight wavelet frame consists of dilations and shifts of selected framelet functions forming a tight frame of L2(R).
  • The inverse framelet transform satisfies W^T Wv = v, ensuring exact reconstruction of the original signal.The transform is redundant because WW^T u ≠ u.

III. MAIN RESULTS

The main results replace the Fourier transform with a framelet transform in the t-SVD framework and formulate tensor recovery models optimized by ADMM.

  • The paper replaces the Fourier transform with a framelet transform and constructs a framelet representation of the tensor nuclear norm.
  • Framelet redundancy is intended to produce transformed data with lower multi-rank, supporting low-rank tensor completion and tensor RPCA models.
  • ADMM-based algorithms are proposed to optimize the models, with the paper reporting guaranteed convergence and tests on multiple multidimensional data types.

A. From DFT to The Framelet Transform

The paper moves from DFT-based t-SVD to framelet transformation, defining framelet multi-rank and framelet TNN to obtain lower-rank transformed representations.

  • A. From DFT to The Framelet Transform: The t-SVD of a third-order tensor can be computed through the DFT, whose transformed frontal-slice ranks define the tensor multi-rank.The DFT implementation uses circular convolution and can be accelerated with FFT.
  • A. From DFT to The Framelet Transform: Figure 2 compares singular-value distributions from original, Fourier-, DCT-, and framelet-transformed tensors using SVD on frontal slices.
  • A. From DFT to The Framelet Transform: The proposed framelet transform replaces the Fourier transform along the third mode while retaining exact reconstruction through W^T W = I.
  • A. From DFT to The Framelet Transform: Framelet-based multi-rank is the vector of ranks of all frontal slices in the framelet-transformed tensor.
  • A. From DFT to The Framelet Transform: A large proportion of singular values for the framelet-transformed video lies in [0, 10^-2] compared with the original, Fourier-, and DCT-transformed data.
  • A. From DFT to The Framelet Transform: The framelet representation of TNN sums the nuclear norms of all framelet-transformed frontal slices and is a convex envelope of the ℓ1 norm of framelet-based multi-rank.

C. Tensor Completion via Minimizing F-TNN

Tensor completion is formulated by minimizing the convex framelet-based tensor nuclear norm subject to agreement with observed entries, and solved using ADMM.

  • C. Tensor Completion via Minimizing F-TNN: The completion model minimizes the framelet-based TNN while constraining the reconstructed tensor to match observed entries on Ω.The feasible set is Φ = {X ∈ R^(n1×n2×n3), X_Ω = O_Ω}.
  • C. Tensor Completion via Minimizing F-TNN: An auxiliary tensor V is introduced with the constraint V = XW, converting the model into an unconstrained ADMM formulation.
  • C. Tensor Completion via Minimizing F-TNN: The V-update decomposes into wn3 subproblems solved by singular value thresholding.
  • C. Tensor Completion via Minimizing F-TNN: The X-update uses the framelet UEP property W^T W X^(3) = X^(3) together with projection onto observed entries.
  • C. Tensor Completion via Minimizing F-TNN: Algorithm 1 alternates V, X, and multiplier updates until convergence, then outputs the reconstructed tensor.
  • C. Tensor Completion via Minimizing F-TNN: The proposed objective is convex, and the ADMM algorithm has theoretically guaranteed convergence.The reported per-iteration complexity is O(wn1n2n3(n3 + min(n1, n2))).

D. Tensor Robust Principal Components Analysis

The tensor RPCA model uses F-TNN to characterize the low-rank component and applies ADMM to solve the resulting optimization problem with theoretically guaranteed convergence.

  • The proposed tensor RPCA model adopts F-TNN to characterize the low-rank component while separating a sparse component from observed data.
  • An auxiliary variable and framelet transform matrix reformulate the model for ADMM-based optimization.The framelet transform matrix is constructed from n filters and l levels, with w = (n − 1)l + 1.
  • ADMM alternately updates the model variables and corresponding multipliers.
  • Each iteration updates V, L, and E through singular-value-related, least-squares, and soft-thresholding subproblems, respectively.Updating E uses the tensor soft-thresholding operator Softτ(·) = sign(·) max(|·| − τ, 0).
  • The tensor RPCA algorithm costs O(wn1n2n3(n3+min(n1, n2))) per iteration and has theoretically guaranteed convergence.

IV. NUMERICAL EXPERIMENTS

The experiments evaluate tensor completion and RPCA methods on multidimensional data using reconstruction metrics averaged across frontal slices, under specified framelet and optimization settings.

  • Experiments evaluate tensor completion on MRI, MSI, and video data using PSNR, SSIM, and FSIM metrics.
  • The experimental materials include algorithmic procedures for tensor RPCA based on initialized framelet transforms, alternating updates, convergence checks, and maximum-iteration limits.
  • Because the data are third-order tensors, the reported PSNR, SSIM, and FSIM values are means over all frontal slices.
  • The framelet system uses piece-wise cubic B-splines, with decomposition level l = 4 generally and l = 2 for MSI data.The tensor completion settings use β = 1, tmax = 100, and ϵ = 10^-2; RPCA uses β = 5, tmax = 200, and ϵ = 10^-3.

A. Tensor Completion

The tensor completion experiments compare F-TNN with matrix-, Tucker-rank-, TNN-, partial-TNN-, and DCTNN-based methods on MRI data, where F-TNN achieves the strongest reported results.

  • The comparison includes LRMC, HaLRTC, TMac, TNN, PSTNN, DCTNN, and the proposed F-TNN method.
  • MRI completion uses 142 × 178 × 121 brain data with sampling rates of 10%, 20%, and 30%.
  • The proposed method achieves the highest indices across MRI sampling rates, while TMac and DCTNN alternately rank second.
  • The margins over the second-best MRI results exceed 1.3dB for PSNR and 0.03 for both SSIM and FSIM.
  • At 10% sampling, F-TNN accurately reconstructs MRI structure, while at 30% sampling all methods perform well and F-TNN and TMac recover white matter visually best.

2) MSI Data:

MSI experiments evaluate completion across 32 CAVE images and show that F-TNN provides the strongest quantitative and visual results, particularly for spectral preservation at low sampling.

  • The MSI experiments use 32 CAVE images of size 512 × 512 × 31 with sampling rates of 5%, 10%, and 20%.
  • F-TNN achieves the best average quantitative performance, while DCTNN obtains the second-best metrics.
  • Sampling rates above 20% are omitted because all methods achieve very high, closely matched performance there.
  • At sampling rate 0.05, pseudo-color visualizations compare incomplete inputs, method outputs, and ground truths for beads, cd, and clay.
  • The MSI visualizations use bands 1, 2, and 31 as red, green, and blue channels, respectively.
  • F-TNN visually preserves image structure and spectral information better than competing methods in the illustrated MSI cases.DCTNN shows spectral distortion on beads, while TMac produces artifacts on clay.

3) Video Data:

Across nine videos and multiple sampling rates, F-TNN achieved the strongest reported quantitative completion results and performed especially well on dynamic content in “news”.

  • Video completion results: F-TNN obtained the best average MPSNR, MSSIM, and MFSIM across nine videos at different sampling rates.
  • Video completion results: At a 30% sampling rate, DCTNN ranked second behind the proposed method.
  • Visual comparisons: On “news”, the proposed method recovered both newscasters and the dynamic screen more effectively than the compared methods.
  • Video completion results: At a 10% sampling rate, the proposed method achieved the highest PSNR, SSIM, and FSIM on all videos.

1) Color Image Recovery:

For color-image recovery from salt-and-pepper noise, the proposed method achieved the best reported metrics and preserved image structure and details in visual comparisons.

  • Color image recovery: The proposed method achieved the best averaged PSNR, SSIM, and FSIM values for color-image noise levels ranging from 5% to 10%.
  • Color image recovery: All tensor-based methods removed salt-and-pepper noise, whereas MRPCA produced unsatisfactory recovery results.
  • Visual comparisons: Residual images showed that the proposed method preserved the structure and details of the “airplane” and “watch” color images.
  • Optimization: The proposed ADMM algorithms solve the convex framelet-based models with guaranteed convergence.
Loading 1909.06982v2…