Source-linked AI summary
Novel methods for multilinear data completion and de-noising based on tensor-SVD
Zemin Zhang, Gregory Ely, Shuchin Aeron, Ning Hao, Misha Kilmer
TL;DR
The paper addresses completion and de-noising of multilinear data from limited samples and sparse corruptions. It develops t-SVD-based compression, TNN-penalized completion, and tensor robust PCA, reporting superior video recovery and de-noising performance over existing matrix-based approaches.
Problem
The paper studies how to recover multilinear data from limited samples and remove sparse corruptions while representing its structural complexity effectively.
Method
The authors use t-SVD, tensor multi-rank, TNN-penalized completion, and tensor robust PCA for multilinear data recovery and de-noising.
Results
The proposed methods show superior video completion and de-noising performance over existing methods, including matrix robust PCA.
Takeaways & Limitations
The t-SVD-based methods apply to multilinear data when that data is compressible in the t-SVD representation.
Takeaways & Limitations
There is no clear convex relaxation for tensor tubal-rank.
Abstract
from arXiv · showhide
In this paper we propose novel methods for completion (from limited samples) and de-noising of multilinear (tensor) data and as an application consider 3-D and 4- D (color) video data completion and de-noising. We exploit the recently proposed tensor-Singular Value Decomposition (t-SVD)[11]. Based on t-SVD, the notion of multilinear rank and a related tensor nuclear norm was proposed in [11] to characterize informational and structural complexity of multilinear data. We first show that videos with linear camera motion can be represented more efficiently using t-SVD compared to the approaches based on vectorizing or flattening of the tensors. Since efficiency in representation implies efficiency in recovery, we outline a tensor nuclear norm penalized algorithm for video completion from missing entries. Application of the proposed algorithm for video recovery from missing entries is shown to yield a superior performance over existing methods. We also consider the problem of tensor robust Principal Component Analysis (PCA) for de-noising 3-D video data from sparse random corruptions. We show superior performance of our method compared to the matrix robust PCA adapted to this setting as proposed in [4].
1. Introduction
The paper targets recovery of multilinear data from limited measurements, exploiting low structural complexity while addressing representational losses in existing higher-order approaches. It uses t-SVD, tensor multi-rank, and Tensor Nuclear Norm for completion and recovery.
- The paper studies robust recovery of multilinear signals or tensors from limited sampling and measurements.
- Existing methods characterize higher-order data complexity through flattening, vectorization, or decompositions such as HOSVD, Tucker-3, and CANDECOMP.
- Low-rank assumptions constrain hypothesis-space complexity, making recovery feasible with measurements proportional to rank under observation constraints.
- Higher-order extensions of matrix SVD can lose representation optimality because they vectorize multilinear data.
- The proposed approach exploits tensor-SVD, tensor multi-rank, and Tensor Nuclear Norm as a convex relaxation for completion and recovery.
- The paper evaluates t-SVD representation, TNN-penalized video completion, and tensor robust PCA for video de-noising.
2. Brief overview of t-SVD
The t-SVD framework treats tensors through tube-based multiplication and Fourier-domain matrix SVDs, yielding tensor complexity measures for approximation and recovery. It also provides a Tensor Nuclear Norm relaxation, while tensor tubal-rank lacks a clear convex relaxation.
- t-product: A third-order tensor can be viewed as a matrix of tubes, with circular convolution replacing scalar multiplication in the t-product.
- t-product: The t-product produces an n1 × n4 × n3 tensor by summing circular convolutions of corresponding tubes.
- t-SVD: The t-SVD decomposes a tensor using orthogonal tensors U and V, a rectangular f-diagonal tensor S, and the t-product.
- t-SVD: The decomposition is obtained by computing matrix SVDs in the Fourier domain and applying inverse Fourier transforms across higher modes.
- Tensor complexity measures: Tensor multi-rank records the matrix rank of each Fourier-domain frontal slice, while tensor tubal-rank counts nonzero tubes in S.
- Tensor complexity measures: TNN is the tightest convex relaxation of the ℓ1 norm of tensor multi-rank, whereas tensor tubal-rank has no clear convex relaxation.
3. Multilinear data compression using t-SVD
The paper compares t-SVD-based compression with vectorized matrix SVD compression for tensor data. The t-SVD approach is motivated by optimal truncation and captures video structure, especially under camera motion.
- The comparison excludes truncated HOSVD and other tensor decompositions because they lack an established notion of optimality.
- The vectorized SVD representation retains rank-k1 factors whose stored-entry count is (m + n + 1)r in the matrix formulation.
- Matrix SVD compression stores vectorized tensor frontal slices as columns of an n1n2 × n3 matrix.
- Even with small k1, the vectorized SVD approximation can retain most of the tensor's information.
- The first t-SVD compression method follows truncated SVD in the Fourier domain, while the second truncates the leading tubes in the t-product domain.
0. We then call the resulting tensors ˆUk2, ˆSk2 and ˆV
The paper evaluates SVD, t-SVD-tubal, and t-SVD compression on three video datasets, including stationary and moving-camera recordings. Across all three videos, t-SVD compression achieves the best performance, while t-SVD-tubal is especially effective for the moving-camera basketball video.
- The experiments compare vectorized SVD, t-SVD-tubal, and t-SVD compression on three video datasets.The comparison includes compression results at compression ratio 5 and RSE evaluations across compression ratios.
- The Escalator and MERL videos are recorded with stationary cameras, whereas the Basketball video uses a non-stationary panning camera.The Escalator video has size 130 × 160 × 50, the MERL video 192 × 256 × 38, and the Basketball video 144 × 256 × 80.
- t-SVD compression has the best performance on all three videos according to the relative square error comparisons.RSE is defined as 20 log10(∥Xrec − X∥F/∥X∥F).
- The results indicate that tensor multi-rank represents video data effectively for both stationary and non-stationary cameras.
- SVD outperforms t-SVD-tubal on the stationary Escalator and MERL videos, while t-SVD-tubal performs better on the moving-camera Basketball video.The paper attributes the moving-camera advantage to convolution capturing shift and scaling between successive frontal slices.
4. Tensor completion from limited samples
The paper formulates tensor completion as Tensor Nuclear Norm minimization from randomly sampled entries and solves it using ADMM with singular-value thresholding. Experiments compare TNN minimization with LRTC and vectorized nuclear-norm minimization on grayscale and color videos, with TNN yielding excellent reconstruction.
- Problem formulation: Tensor completion seeks to recover an unknown low-tubal-rank tensor from randomly sampled entries.The observed data are represented by an indicator tensor and an orthogonal sampling projector.
- Optimization model: The recovery objective minimizes the tensor nuclear norm subject to agreement with the observed entries.The tensor nuclear norm equals the nuclear norm of a block-diagonal Fourier-domain representation.
- Optimization method: ADMM solves the completion problem through least-squares projection onto the sampling constraint and singular-value thresholding.The method alternates constraint projection with a thresholding-based update.
- Optimization method: The proposed updates have an interpretation as iterative singular-tubal shrinkage implemented by convolution along singular tubes.In the Fourier domain, entries are shrunk slice by slice; in the original domain, this corresponds to convolution with tubal threshold vectors.
- Experiments: Experiments evaluate TNN minimization against LRTC and vectorized nuclear-norm minimization on grayscale and 4-D color basketball videos.The color basketball tensor has size 144 × 256 × 3 × 80, and sampling rates range from 10% to 90%.
- Results: TNN minimization gives excellent reconstruction over LRTC and vectorized nuclear-norm minimization in the reported video recovery results.The paper states that the recovery results align with the t-SVD compressibility results.
5. Tensor robust PCA
The paper extends robust PCA to tensors by separating a low tensor-multi-rank component from a sparse, tube-wise corruption component. On corrupted basketball video, tensor robust PCA separates noise effectively, whereas matrix robust PCA produces a blurred background and misallocates structure and noise.
- Problem formulation: Tensor robust PCA models a corrupted observation tensor as a low tensor-multi-rank component plus a sparse component.The experiments focus on sparse corruption organized as pixel tubes along the third dimension.
- Optimization model: The separation minimizes tensor nuclear norm plus a weighted mixed norm for the sparse tensor under the constraint M = L + S.The mixed norm sums Frobenius norms of the tubes S(i, j, :).
- Optimization method: The method uses ADMM to solve the convex tensor robust PCA optimization problem.The recursion includes updates based on the tensor nuclear-norm formulation.
- Experiments: The experiment corrupts sparse pixel tubes in an 80-frame basketball video with heavy additive Gaussian noise.Each frame is 72 × 128, and noisy tube locations remain fixed for ten consecutive frames before being randomly selected again.
- Results: Tensor robust PCA separates noisy pixels from the video effectively, while matrix robust PCA recovers a blurred background and places scene structure and noise in the sparse component.The comparison uses frame-wise vectorization for matrix robust PCA.
6. Conclusion and Future work
The paper presents t-SVD-based methods for multilinear-data completion and de-noising, demonstrating performance gains on video applications while identifying broader scope and theoretical recovery conditions as future work.
- The methods address completion and de-noising of multilinear data using tensor-SVD.
- Video completion and de-noising from random sparse corruptions showed significant performance gains over existing methods.
- The methods can handle more general multilinear data when that data is compressible in the t-SVD representation.
- Necessary and sufficient recovery conditions for low-multirank tensors using TNN remain an important theoretical problem.