PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Low Rank Tensor Ring Completion

Wenqi Wang, Vaneet Aggarwal, Shuchin Aeron

arXiv:1707.08184v1cs.LGcs.IT

TL;DR

Tensor completion needs expressive low-rank representations that can recover missing entries, while tensor train structures have limitations for some completion settings. The paper proposes MPS-based tensor-ring completion with TRA initialization and alternating least squares, and reports significant improvement over tensor-train completion across several real datasets.

  • Problem

    Tensor train completion has structural limitations, motivating completion methods based on the more expressive tensor ring representation.

  • Method

    The paper uses the MPS representation of tensor rings, initializes factors with TRA, and alternates least-squares updates over the low-rank factors.

  • Results

    The proposed method significantly improves completion performance over tensor train methods on Einstein’s image, Extended YaleFace Dataset B, and video data.

  • Takeaways & Limitations

    Tensor ring structure provides improved expressive power for completion compared with tensor train structure in the evaluated computer-vision settings.

Abstract

from arXiv · show

Using the matrix product state (MPS) representation of the recently proposed tensor ring decompositions, in this paper we propose a tensor completion algorithm, which is an alternating minimization algorithm that alternates over the factors in the MPS representation. This development is motivated in part by the success of matrix completion algorithms that alternate over the (low-rank) factors. In this paper, we propose a spectral initialization for the tensor ring completion algorithm and analyze the computational complexity of the proposed algorithm. We numerically compare it with existing methods that employ a low rank tensor train approximation for data completion and show that our method outperforms the existing ones for a variety of real computer vision settings, and thus demonstrate the improved expressive power of tensor ring as compared to tensor train.

I. INTRODUCTION

The paper motivates tensor ring completion as a cyclic alternative to tensor train representations and develops an MPS-based alternating minimization approach for missing-data recovery. It introduces initialization, efficient subproblem solution, complexity analysis, and empirical comparisons with tensor train completion.

  • Motivation: Tensor train representations efficiently store order-d tensors with O(dnr^2) parameters, but their image-classification and completion applications remain limited.Tensor train also imposes border rank-1 constraints, uneven intermediate ranks, and non-permutation-invariant factor multiplication.
  • Motivation: Tensor ring removes tensor train’s boundary rank constraints and permits circularly shifted cores through its trace-based structure.The trace operation makes core products independent of strict ordering.
  • Contributions: The proposed method models missing data with tensor ring decomposition and alternates minimization over low-rank MPS factors.The approach extends tensor train approximation for zero-filled missing data and converts subproblems into efficient least-squares problems.
  • Contributions: Using a common tensor ring rank R provides one tunable rank parameter, unlike tensor train’s typically larger intermediate ranks.The tensor ring rank is generally a vector, but the paper assumes all ranks equal for its setup.
  • Contributions: The paper analyzes storage and computational complexity and compares tensor ring completion with tensor train methods on real computer-vision data.Evaluations include Einstein’s image, Extended YaleFace Dataset B, and high-speed video.

A. Problem Formulation

The problem is to recover a low tensor-ring-rank approximation that matches the observed entries of a partially observed tensor. TR-ALS initializes the factors with TRA and cyclically updates each factor using alternating least squares.

  • Problem Formulation: Tensor ring completion seeks a low-rank approximation f(U1 ··· Un) that matches the observed entries selected by PΩ.The observed-entry indicator PΩ distinguishes known entries from missing ones.
  • Problem Formulation: The tensor ring rank R is predefined, and every MPS factor Ui has dimensions R×Ii×R.This setup uses a scalar rank shared across all factors.
  • Solution Strategy: TR-ALS first initializes the MPS factors with Tensor Ring Approximation and then cyclically estimates one factor while holding the others fixed.The alternating updates solve the completion problem through least-squares subproblems.

B. Tensor Ring Approximation (TRA)

TRA initializes tensor-ring completion by extending a truncated tensor-train decomposition of zero-filled data to the desired ring dimensions. TR-ALS then updates each factor through independent least-squares problems, with complexity analyzed per iteration.

  • Tensor Ring Approximation (TRA): TRA decomposes zero-filled data in tensor-train form, constraining ranks through SVD before extending factors to tensor-ring dimensions.The retained rank at each SVD step is thresholded by R and the relevant tensor dimensions.
  • Tensor Ring Approximation (TRA): TRA fills the extended tensor-ring entries with small random normal values rather than zeros.The paper reports faster convergence in small examples and notes that nonzero entries help initialize larger corner ranks.
  • Alternating Least Square: TR-ALS initializes factors with TRA and cyclically minimizes the observed-entry reconstruction error over one MPS factor at a time.Each update keeps the remaining factors fixed and solves the resulting least-squares problem.
  • Alternating Least Square: Because each factor slice corresponds to an observed-row subproblem, updating Ui reduces to Ii equivalent least-squares problems.The formulation uses observations associated with each mode-k slice.
  • Alternating Least Square: The algorithm updates all factors repeatedly until convergence without requiring MPS normalization.Normalization is unnecessary here, unlike in the tensor-ring decomposition algorithm used to seek a unique factorization.

D. Complexity Analysis

The tensor ring model reduces storage through orthonormal MPS factors and uses a tunable rank, while its alternating least-squares updates have complexity governed by observations and rank.

  • R^2(ΣI_i − n + 1) parameters store the tensor ring MPS representation, with rank R adjustable for the desired accuracy.The storage expression follows orthonormalizing the factors and consolidating products.
  • max(O(nPR^4), O(nR^6)) is the overall complexity for one iteration updating n MPS factors.Each factor update costs max(O(PR^4), O(R^6)), where P is the number of observations.
  • Tensor train completion has similar nominal complexity, but its generally larger intermediate ranks can make tensor ring completion computationally cheaper.Tensor ring uses a single rank parameter that is easier to tune and may be smaller than tensor-train intermediate ranks.

IV. NUMERICAL RESULTS

The numerical-results section evaluates TR-ALS against tensor-train completion methods across synthetic and real data settings, using iterative convergence with a fixed maximum iteration count.

  • TR-ALS is compared with TT-ALS and SiLRTC for tensor completion experiments.SiLRTC is included because it previously showed good recovery in image completion.
  • TR-ALS uses at most 300 iterations, with convergence monitored through the change in the last factorization term and tolerance 10^-10.The stated maximum iteration count is maxiter = 300.
  • The experiments cover synthetic data, image completion, YaleFace image sets, and video completion.The evaluation therefore spans both synthetic and multiple computer-vision data settings.

A. Synthetic Data

On a synthetic fourth-order tensor generated under a tensor-ring rank-8 model, TR-ALS achieves lower recovery error than the tested tensor-train and SiLRTC methods as sampling increases.

  • The synthetic tensor has dimensions 20×20×20×20 and tensor-ring rank 8, with independently standard-normal sampled cores.Its four cores each have dimensions 8×20×8.
  • TR-ALS has the lowest recovery error among TR-ALS, LR-TT, HR-TT, and SiLRTC over observation ratios from 10% to 60%.The tensor-train baselines use ranks and.
  • Higher observation ratios produce faster TR-ALS convergence, while the proposed setup cannot complete the tensor when the ratio is below 10%.The convergence comparison uses sampling ratios of 10%, 15%, 20%, 30%, 40%, and 50%.

B. Image Completion

The experiments reshape image data into higher-order tensors for completion and compare TR-ALS with TT-ALS across ranks and observation settings. TR-ALS achieves better recovery accuracy and preserves more image detail in the reported comparisons.

  • Einstein Image: The RGB Einstein image is reshaped from 600 × 600 × 3 into a 7-order tensor of size 6 × 10 × 10 × 6 × 10 × 10 × 3.
  • Einstein Image: TR-ALS has lower recovery error than TT-ALS at all considered ranks and observation percentages for the Einstein image.The comparison uses 5%, 10%, 20%, and 30% observed data.
  • Einstein Image: TR-ALS with rank 28 gives the best Einstein-image recovery accuracy among the considered ranks when 10% of pixels are randomly observed.
  • Extended YaleFace: The Extended YaleFace data is down-sampled, formatted as a 4-order tensor, and reshaped into an 8-order tensor for completion.The resulting tensor has size 6 × 8 × 6 × 7 × 8 × 8 × 19 × 2, with 10% of pixels considered observed.
  • Extended YaleFace: For Extended YaleFace recovery, TR-ALS better captures image detail and produces higher-resolution recovered images than TT-ALS.

D. Video completion

The video-completion experiment reshapes high-speed color video into an 11-order tensor with 90% missing pixels, then compares TR-ALS and TT-ALS reconstructions across ranks. TR-ALS achieves lower recovery error and visually better completion than TT-ALS.

  • Video setup: The gun-shot video contains 85 frames of 100×260×3 color images and is reshaped into an 11-order tensor for completion.The reshaped dimensions are 5 × 2 × 5 × 2 × 13 × 2 × 5 × 2 × 3 × 5 × 17.
  • Results: 6.25% recovery error is achieved by TR-ALS with 10% of video pixels observed, versus 14.83% for the best TT-ALS result.The reported comparison is for completion error on the video data.
  • Experimental comparison: 90% missing pixels are used to compare TR-ALS and TT-ALS reconstructions across tensor-train and tensor-ring ranks.The figures show rank settings from 10 through 30 for the two methods.
  • Results: The completed video frames show better resolution and clearer bullets and smoke with TR-ALS than with TT-ALS.This visual comparison is reported alongside the quantitative recovery-error result.
  • Scope: The proposed tensor-ring completion algorithm is evaluated on video completion among several computer-vision datasets and improves over tensor-train completion.The conclusion describes significant improvement across Einstein’s image, Extended YaleFace Dataset B, and video completion.

VI. APPENDIX

The appendix establishes that cyclically permuting tensor modes corresponds to cyclically shifting the tensor-ring cores. This follows from the trace operation’s invariance under cyclic permutations.

  • Permutation identity: Tensor permutation reorders the entries of X by moving a suffix of indices before the remaining prefix.The appendix writes the permuted entry as X(jn−i+2, ..., jn, j1, ..., jn−i+1).
  • Cyclic core shift: The permuted tensor is represented by cyclically shifting the product of tensor-ring cores from U1 · · · Un to Ui · · · UnU1 · · · Ui−1.The shifted ordering appears inside the function f defining the tensor-ring representation.
  • Conclusion: The proof concludes that corresponding entries on both sides are equal because trace is invariant under cyclic permutations.This establishes the tensor-ring permutation property used by the appendix.

C. Proof of Lemma 3

The proof rewrites the alternating-minimization subproblem after permuting tensor modes. It uses Frobenius-norm invariance and cyclic core reordering to obtain an equivalent formulation.

  • Norm invariance: Tensor permutation preserves the tensor Frobenius norm because it leaves all entries unchanged.This permits the residual objective to be expressed after permuting the tensor.
  • Cyclic reformulation: Applying the cyclic-shift lemma rewrites f(U1 · · · Ui−1YUi+1 · · · Un) after permutation as f(YUi+1 · · · UnU1 · · · Ui−1).The variable factor Y moves to the front while the remaining factors retain cyclic order.
  • Equivalent subproblem: The resulting equation replaces the original observation mask, data tensor, and fixed-factor product with their permuted equivalents.The proof compares these substitutions to establish equivalence with the target formulation.
Loading 1707.08184v1…