PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient tensor completion for color image and video recovery: Low-rank tensor train

Johann A. Bengua, Ho N. Phien, Hoang D. Tuan, Minh N. Do

arXiv:1606.01500v1math.NAcs.DS

TL;DR

Tensor completion seeks to recover missing entries in high-dimensional data, but conventional rank formulations struggle to capture global correlations and can be computationally difficult. The paper uses tensor train rank with balanced matricizations, proposing SiLRTC-TT, TMac-TT, and tensor augmentation. On color-image and video recovery tasks, the proposed methods show clear advantages over other methods, with TMac-TT outperforming all algorithms in the cited 95%-missing video cases.

  • Problem

    Tensor completion must recover missing entries despite the difficulty of tensor-rank optimization and the limited global-correlation capture of Tucker-rank matricizations.

  • Method

    The paper optimizes tensor train rank using SiLRTC-TT's TT nuclear norm and TMac-TT's multilinear matrix factorization, with ket augmentation for higher-order representations.

  • Results

    TMac-TT outperforms all algorithms in the cited 95% missing-entry NYC and bus video recovery benchmarks, evaluated using RSE and mean SSIM.

  • Takeaways & Limitations

    TT-based algorithms are promising for real-world higher-order tensor recovery, particularly when tensor augmentation is applied to image and video data.

Abstract

from arXiv · show

This paper proposes a novel approach to tensor completion, which recovers missing entries of data represented by tensors. The approach is based on the tensor train (TT) rank, which is able to capture hidden information from tensors thanks to its definition from a well-balanced matricization scheme. Accordingly, new optimization formulations for tensor completion are proposed as well as two new algorithms for their solution. The first one called simple low-rank tensor completion via tensor train (SiLRTC-TT) is intimately related to minimizing a nuclear norm based on TT rank. The second one is from a multilinear matrix factorization model to approximate the TT rank of a tensor, and is called tensor completion by parallel matrix factorization via tensor train (TMac-TT). A tensor augmentation scheme of transforming a low-order tensor to higher-orders is also proposed to enhance the effectiveness of SiLRTC-TT and TMac-TT. Simulation results for color image and video recovery show the clear advantage of our method over all other methods.

I. INTRODUCTION

The paper frames tensor completion as recovery of missing multidimensional data and motivates tensor train rank as a better representation for global tensor correlations. It introduces TT-based optimization methods and augmentation for image and video recovery.

  • I. INTRODUCTION: Tensors represent multidimensional data, including color images as third-order and color videos as fourth-order tensors.Their high-dimensional structure can nevertheless admit low-rank decompositions such as CP, Tucker, or TT.
  • I. INTRODUCTION: Low-rank tensor completion recovers missing tensor entries from partially observed data but remains difficult because CP-rank computation is NP-hard.The problem extends low-rank matrix completion to applications including computer vision, signal processing, and machine learning.
  • I. INTRODUCTION: Tucker rank uses highly unbalanced one-mode-versus-rest matricizations, which may miss global correlations and make rank optimization ineffective.For equal mode dimensions, each matricization has dimensions I × I^(N−1), producing a low and potentially uninformative matrix rank.
  • I. INTRODUCTION: TT rank uses matrices formed by well-balanced matricizations across permutations of modes, enabling more effective capture of correlations among tensor modes.The TT rank is defined by ranks of these matricizations and can be determined through singular matrices in the TT representation.
  • I. INTRODUCTION: The paper proposes SiLRTC-TT, based on TT nuclear-norm optimization, and TMac-TT, based on multilinear matrix factorization to approximate TT rank.It also introduces ket augmentation to reshape low-order tensors into higher-order tensors without changing their number of entries.

III. TENSOR COMPLETION

The paper contrasts conventional Tucker-based completion with TT-rank optimization, arguing that balanced matricizations better capture correlations across multiple tensor modes. It develops nuclear-norm and matrix-factorization formulations for this purpose.

  • III. TENSOR COMPLETION: The paper proposes two TT-rank tensor-completion formulations: nuclear-norm minimization and multilinear matrix factorization.These formulations are presented as alternatives to conventional Tucker-rank optimization.
  • A. Conventional tensor completion: Matrix completion commonly replaces NP-hard rank minimization with nuclear-norm minimization, but this surrogate is efficient mainly for balanced matrices.For highly unbalanced matrices, rank can approach the smaller dimension and require nearly all entries for successful completion.
  • A. Conventional tensor completion: Tucker-rank completion relies on one-mode matricizations that capture correlation between a single mode and the remaining modes.It therefore does not account for correlations between several modes and the tensor remainder, especially for higher-order tensors.
  • A. Conventional tensor completion: TT rank addresses this limitation through more balanced matrices that can capture hidden correlations between tensor modes more effectively.The paper motivates TT-rank optimization as a way to overcome the weakness of conventional Tucker-based completion.

B. Tensor completion by TT rank optimization

The paper formulates tensor completion through TT rank, whose balanced matricizations capture correlations across complementary mode groups. It develops nuclear-norm and matrix-factorization formulations to make TT-rank optimization tractable.

  • The proposed TT-rank completion problem minimizes weighted ranks of tensor unfoldings under observed-entry constraints.The weights αk determine each unfolding rank's contribution, with their sum constrained to one.
  • TT rank uses matricizations along different mode partitions to capture global tensor-entry correlations.The sequence of unfolding ranks captures correlations between k modes and the remaining N−k modes.
  • The rank formulation is difficult to handle directly, motivating two surrogate optimization problems.The paper introduces nuclear-norm and multilinear matrix-factorization alternatives.
  • The TT nuclear-norm formulation uses more balanced unfolding matrices than conventional alternatives, improving its suitability for rank optimization.A square model is obtained by assigning nonzero weight only to the middle unfolding.
  • The factorization formulation represents each unfolding as X[k] = UV and minimizes a Frobenius-norm objective instead of unfolding nuclear norms.This model parallels Tucker-rank tensor completion approaches while using TT unfoldings.

IV. PROPOSED ALGORITHMS

The proposed algorithms section develops solution methods for the paper's two TT-rank tensor-completion optimization problems.

  • Algorithmic development targets the two optimization problems introduced for TT-rank completion.

A. SiLRTC-TT

SiLRTC-TT solves the TT nuclear-norm completion problem by alternating updates of unfolding matrices and the tensor. Its convex objective guarantees convergence to a global solution.

  • A. SiLRTC-TT: SiLRTC-TT addresses the TT nuclear-norm formulation using a block-coordinate strategy over unfolding matrices and tensor X.The unfolding-matrix updates use thresholding SVD, followed by tensor updates that preserve observed entries.
  • A. SiLRTC-TT: Each unfolding matrix is updated through thresholding SVD applied to the corresponding tensor unfolding.The thresholded singular values are max(λl − γk, 0).
  • A. SiLRTC-TT: Tensor X is updated after all unfolding matrices, with known entries fixed to the observed tensor values.
  • A. SiLRTC-TT: SiLRTC-TT is guaranteed to converge and obtain a global solution because its objective is convex with a separable nonsmooth term.The stopping condition uses the relative error between successive tensor iterates.
  • A. SiLRTC-TT: The algorithm outputs the recovered tensor X as an approximation of the original tensor T.

B. TMac-TT

TMac-TT solves the factorization-based TT completion problem by alternating updates of factor matrices and the tensor. Its parallel matrix-factorization design avoids many SVD computations and can substantially reduce computational time.

  • B. TMac-TT: TMac-TT applies block-coordinate updates to factor matrices and tensor X in the TT factorization model.The problem is convex in each variable group when the remaining groups are fixed.
  • B. TMac-TT: The factor-matrix update can use an alternative formulation that avoids computing the Moore-Penrose pseudoinverse.The replacement preserves the product needed in the subsequent update.
  • B. TMac-TT: After factor updates, TMac-TT computes the elements of the next tensor iterate.
  • B. TMac-TT: TMac-TT avoids many SVDs and therefore can substantially save computational time.
  • B. TMac-TT: The method can also use middle-unfolding weights to form the TMac-Square variant.This sets αk = 1 for k = round(N/2) and αk = 0 otherwise.
  • B. TMac-TT: The algorithm takes observed tensor data, an index set, and factorization parameters, then outputs a recovered tensor approximating T.

C. Computational complexity of algorithms

The paper analyzes one-iteration computational complexity for tensor-completion algorithms under equal mode dimensions and equal Tucker and TT ranks.

  • The complexity analysis assumes equal mode dimensions, I1 = I2 = ··· = IN = I, and equal Tucker and TT ranks, r1 = r2 = ··· = rN = r.
  • Table I compares the computational complexity of the algorithms for completing an Nth-order tensor in one iteration.

V. TENSOR AUGMENTATION

Ket augmentation casts a low-order tensor into a higher-order representation that preserves pixel values while enabling tensor-train methods to exploit local structure and mode correlations.

  • Tensor augmentation: Ket augmentation casts an Nth-order tensor into a Kth-order tensor, with K ≥ N, to create a higher-order representation.
  • Tensor augmentation: The augmented tensor can make TT decomposition more efficient by exploiting local data structure, especially when the tensor is slightly correlated.
  • Color-image construction: For color images, the scheme generalizes block-structured addressing to tensors of size 2^n × 2^n × 3.
  • Color-image construction: After repeated block expansion, a 2^n × 2^n × 3 image is represented as an (n + 1)th-order tensor with dimensions 4 × 4 × ··· × 4 × 3.
  • Purpose: The representation preserves pixel values and rearranges them so texture richness can be studied through correlations between tensor modes.
  • Illustration: Figure 1 illustrates the structured block addressing procedure for 2×2×3 and 2^2 × 2^2 × 3 images.

VI. SIMULATIONS

The simulations evaluate tensor-completion algorithms on synthetic data, color images, and videos using missing-ratio experiments, RSE, and iterative convergence criteria.

  • Experimental setup: Experiments compare the proposed algorithms with TMac, TMac-Square, SiLRTC, SiLRTC-Square, FBCP, STDC, and ALS.
  • Experimental setup: Missing entries are sampled randomly under a uniform distribution, and missing ratio mr is varied across simulations.
  • Evaluation: Recovery performance is measured by relative square error between the recovered tensor X and the original tensor T.
  • Evaluation: Convergence is assessed using relative changes between successive iterates, with tol = 10^-4 and maxiter = 1000.
  • Parameter initialization: The initial weights and TT ranks are selected through empirical parameter choices, including βk = fαk and candidate f values from [0.01, 0.05, 0.1, 0.5, 1].
  • Parameter initialization: Initial parameters can affect performance, so the proposed algorithms may not be optimal and automatic or adaptive selection remains future work.

B. Synthetic data completion

Synthetic experiments test completion of tensors with known low Tucker and TT ranks across dimensions, missing ratios, and rank settings. TMac-TT generally performs best and remains effective at high missing ratios and across the tested phase diagram.

  • Synthetic data generation: Synthetic tensors are generated with known Tucker and TT ranks, using random TT-format factors.
  • Completion of low TT rank tensor: The experiments evaluate 4D, 5D, 6D, and 7D tensors with specified dimensions and corresponding TT rank tuples.
  • Completion of low TT rank tensor: TMac-TT shows the best performance in most cases and often recovers tensors at mr = 0.9 with RSE ≈ 10^-4.
  • Completion of low TT rank tensor: SiLRTC-TT and TMac-TT often outperform their corresponding SiLRTC and TMac counterparts on the synthetic tests.
  • Completion of low TT rank tensor: Phase diagrams evaluate successful recovery for a 5D tensor as TT rank varies from 2 to 16 and the recovery threshold is ϵ = 10^-2.
  • Completion of low TT rank tensor: TMac-TT always successfully recovers the tested tensor across the displayed TT ranks and missing ratios.

2) Completion of low Tucker rank tensor:

Experiments on synthetic tensors, color images, and videos evaluate tensor completion with and without ket augmentation. TMac-TT performs especially strongly on augmented image and video recovery, including severe missingness.

  • Synthetic tensor completion: On 5D tensors with low Tucker rank, TMac and TMac-TT perform best, while SiLRTC-TT outperforms SiLRTC and SiLRTC-Square.The experiment uses tensors of size 20×20×20×20×20, with Tucker rank varying from 2 to 16 and ϵ = 10^-2.
  • Synthetic tensor completion: Synthetic experiments show the proposed algorithms perform comparably to Tucker-based algorithms despite tensors being generated with low Tucker ranks.
  • Color image completion: Images are represented as 256 × 256 × 3 third-order tensors, then reshaped into ninth-order tensors using KA without changing the number of entries.The augmented representation is used for Peppers and Lena experiments with missing ratios from 0.5 to 0.9.
  • Color image completion: For Lena, TMac-TT achieves the lowest RSE at every missing rate when using the KA scheme.
  • Color image completion: For House, STDC performs best without augmentation, whereas TMac-TT and TMac-Square perform best with augmentation and TMac nearly removes the text.
  • Video completion: Video completion benchmarks FBCP, ALS, TMac, TMac-TT, and TMac-Square on NYC and bus videos after forming video sequence tensors.The frame and image-row modes are merged, so completion is performed on the entire video rather than independently on each frame.

VII. CONCLUSION

The paper concludes that TT-rank optimization provides effective tensor completion algorithms, particularly after tensor order augmentation. Results are comparable to conventional methods on original images and stronger on augmented image and video data.

  • Conclusion: SiLRTC-TT minimizes TT rank through TT nuclear norm optimization, while TMac-TT uses multilinear matrix factorization to approximate TT rank.
  • Conclusion: TMac-TT is more computationally efficient because it does not require the SVD.
  • Conclusion: On synthetic data, the proposed algorithms outperform others for low TT-rank tensors and perform comparably for low Tucker-rank tensors.
  • Conclusion: On original image tensors, the proposed algorithms are comparable to STDC, while tensor augmentation improves recovery in both image and video experiments.
  • Conclusion: The paper identifies data compression, text mining, image classification, and video indexing as possible future applications.
Loading 1606.01500v1…