PaperlayerView exact revision on arXiv

Source-linked AI summary

Exact tensor completion using t-SVD

Zemin Zhang, Shuchin Aeron

arXiv:1502.04689v2cs.LGmath.NAstat.ML

TL;DR

The paper studies recovery of tensors from limited random samples. It uses t-SVD and convex tensor-nuclear-norm minimization to obtain exact-recovery guarantees for low-tubal-rank tensors, with empirical comparisons against alternative completion methods.

  • Problem

    The paper addresses how to recover multidimensional arrays from limited sampling, particularly when the data have low tensor tubal rank.

  • Method

    The approach uses t-SVD to define tubal rank and solves a convex optimization problem minimizing the tensor nuclear norm under observed-entry constraints.

  • Results

    The method guarantees perfect recovery of an n1×n2×n3 tensor of tubal rank r using O(rn1n3 log((n1 + n2)n3)) samples under the stated conditions.

  • Takeaways & Limitations

    For tensors of moderate order, t-SVD provides a computationally and theoretically sound framework whose matrix-oriented tools can support recovery guarantees.

  • Takeaways & Limitations

    The analysis uses Bernoulli random sampling, while guarantees for other sampling models remain an ongoing analysis question.

Abstract

from arXiv · show

In this paper we focus on the problem of completion of multidimensional arrays (also referred to as tensors) from limited sampling. Our approach is based on a recently proposed tensor-Singular Value Decomposition (t-SVD) [1]. Using this factorization one can derive notion of tensor rank, referred to as the tensor tubal rank, which has optimality properties similar to that of matrix rank derived from SVD. As shown in [2] some multidimensional data, such as panning video sequences exhibit low tensor tubal rank and we look at the problem of completing such data under random sampling of the data cube. We show that by solving a convex optimization problem, which minimizes the tensor nuclear norm obtained as the convex relaxation of tensor tubal rank, one can guarantee recovery with overwhelming probability as long as samples in proportion to the degrees of freedom in t-SVD are observed. In this sense our results are order-wise optimal. The conditions under which this result holds are very similar to the incoherency conditions for the matrix completion, albeit we define incoherency under the algebraic set-up of t-SVD. We show the performance of the algorithm on some real data sets and compare it with other existing approaches based on tensor flattening and Tucker decomposition.

1 INTRODUCTION

The paper develops a t-SVD-based framework for exact completion of third-order tensors under random sampling, with recovery guarantees tied to tubal rank. It contrasts this approach with CP-, Tucker-, and unfolding-based methods, which have optimization, weighting, applicability, or guarantee limitations.

  • Tensor completion recovers multidimensional arrays from limited measurements, with applications including recommendation systems, dimensionality reduction, multi-class learning, data mining, and computer vision.
  • Matrix completion motivates tensor methods through incoherent sampling and nuclear-norm minimization as a computationally feasible convex surrogate for low rank.
  • The paper applies t-SVD as a rank-revealing factorization for third-order tensors and derives theoretical recovery bounds under its tubal-rank framework.The t-SVD algebra is designed to retain similarities to matrix algebra and analysis.
  • O(rn1n3 log((n1 + n2)n3)) samples suffice for perfect recovery of an n1×n2×n3 tensor of t-SVD rank r via convex optimization.
  • Tensor Completion Based on CP decomposition: CP-based completion is non-convex and makes CP-rank determination or best low-rank approximation difficult in practice.
  • Tensor Completion Based on Tucker Decomposition: Tucker-based completion lacks a principled choice of matricization weights, does not extend straightforwardly to higher-order tensors, and lacks exact-recovery sample guarantees.

2 NOTATIONS AND PRELIMINARIES

This section establishes tensor notation and the t-product framework, then defines t-SVD, tensor tubal rank, tensor operators, inner products, and standard tensor bases. It also records Fourier-domain representations and auxiliary norms used in the paper’s analysis.

  • Fourier notation: The third-mode Fourier transform is denoted by bA = fft(A, [ ], 3), with A recovered using the corresponding inverse FFT.The ith frontal slice of A is written A(i) or A(:, :, i).
  • Tensor operations: Tensor transposes conjugate-transpose frontal slices and reverse the order of transposed slices 2 through n3.
  • Tensor notation and t-product: A third-order tensor is treated as a matrix of tubes, with multiplication replacing scalar products by circular convolution along the third dimension.
  • t-SVD: The t-SVD factors a tensor into orthogonal tensors and a rectangular f-diagonal tensor whose entries are its singular values.The decomposition is obtained by computing matrix SVDs in the Fourier domain and applying inverse transforms.
  • Tensor rank: Tensor tubal rank equals the number of nonzero singular tubes and alternatively the largest matrix rank among the tensor’s Fourier-domain frontal slices.The reduced t-SVD uses factors with tubal-rank-sized inner dimensions for faster computation and lower storage.
  • Bases and auxiliary constructions: Standard column and tube bases provide elementary tensor components, while tensor operators and inner products support Fourier-domain analysis and decomposition.A unit tensor can be obtained from these bases, and the tensor inner product includes the FFT normalization factor 1/n3.

3 MAIN RESULT

The paper studies recovery of third-order tensors from limited observations using t-SVD and tensor nuclear-norm minimization. Under incoherence conditions, it establishes high-probability exact recovery for both entry sampling and random tubal sampling, with the latter reducing to Fourier-domain matrix completion.

  • Random Sampling: Tensor completion seeks to recover a tensor from sampled entries by solving a convex optimization problem based on t-SVD.The formulation minimizes the tensor nuclear norm subject to agreement with observed entries.
  • Incoherence Conditions: Standard tensor incoherence requires the t-SVD tensor columns to be sufficiently spread and uncorrelated with the standard tensor basis.Low incoherence means entries carry approximately similar amounts of information, whereas concentrated columns make recovery difficult.
  • Random Sampling: The analysis avoids the joint incoherence condition used in matrix completion by applying an ℓ∞,2-norm-based idea to tensors.The paper states that this yields a tensor recovery guarantee under the standard tensor incoherent condition.
  • Random Sampling: Under standard tensor incoherence, M is the unique minimizer of the tensor nuclear-norm program with probability at least 1 − c1((n1 + n2)n3)^−c2.The result applies to the reduced t-SVD setting specified in Theorem 3.1.
  • Random Sampling: The random-sampling analysis does not reduce to independent Fourier-domain matrix completion because the measurements are coupled.The paper explicitly contrasts this with random tubal sampling, where the slices do separate.
  • Random Tubal Sampling: For random tubal sampling, the optimization is equivalent to n3 matrix completion problems in the Fourier domain.Sampling tubes decouples the Fourier-domain slices, allowing matrix-completion results to be applied under the stated slice-wise conditions.

4 PROOF OF THE MAIN RESULTS

The proof establishes exact recovery by showing that the true tensor uniquely minimizes the tensor nuclear norm under the stated sampling and incoherence conditions. It uses convex analysis, tensor dual certificates, projection properties, and supporting propositions and lemmas.

  • The proof’s main strategy is to verify that M is the unique minimum tensor nuclear norm solution to (22).
  • The argument assumes n1 = n2 = n without restricting n3; the unequal n1 and n2 case follows analogously.
  • Under the proposition’s conditions, every feasible X ≠ M has greater tensor nuclear norm, so M is the unique minimizer of (22).
  • The proof uses a tensor nuclear norm dual representation and orthogonal projection relations derived from the t-SVD framework.
  • A tensor dual certificate Y supported in Ω is used to establish the required tensor nuclear norm inequalities.

5 NUMERICAL EXPERIMENTS

The experiments evaluate t-SVD tensor completion on synthetic tensors and a basketball video. They examine recovery across sampling rates and tubal ranks and compare five completion methods on randomly missing video entries.

  • Synthetic tensors are generated with i.i.d. Gaussian entries, reduced to tubal-rank r by t-SVD, and sampled uniformly before solving (22).Recovery is counted as correct when RSE ≤ 10^-3, with 20 repetitions per experiment.
  • Figure 4 maps empirical recovery rate and RSE across sampling rates and tubal ranks for 40 × 40 × 30 and 30 × 30 × 20 tensors.Black indicates failure or RSE 1, while white indicates success or RSE 0.
  • Five video-completion methods are compared: framewise matrix completion, LRTC, Tucker-based Riemannian optimization, random-sampling t-SVD, and tubal-sampling t-SVD.
  • The basketball video has size 144 × 256 × 80 and is evaluated with 50% random entry sampling, except that tubal sampling observes 50% of the tubes.
  • Both t-SVD approaches outperform the other four methods in the reported basketball-video RSE experiment.

6 CONCLUSION

The paper concludes that low-tubal-rank tensors can be exactly recovered under a Tensor Standard Incoherent condition and that t-SVD provides a theoretically and computationally sound framework for moderate-order tensors.

  • Under a Tensor Standard Incoherent condition, the method can perfectly recover tensors with low tubal-rank and provides a theoretical bound for exact completion.
  • Experiments comparing tensor-completion approaches show better performance for the proposed method on some real data sets.
  • For tensors of moderate order, t-SVD provides a computationally and theoretically sound analysis framework.
  • Within this framework, matrix prediction and learning tools based on vector spaces can be adapted to obtain reliable performance guarantees.

APPENDIX A PROOF OF PROPOSITION 4.1 CONDITION 1

The appendix uses a theorem first developed in prior work as a recurring tool in the subsequent proof.

  • A theorem developed in is introduced as a frequently used ingredient in the following proof.
  • The appendix relies on an existing theorem rather than presenting it as newly developed here.
  • The theorem’s role is to support the proof that follows in the appendix.

Theorem A.1. (Noncommutative Bernstein Inequality)

This section introduces a noncommutative Bernstein inequality and applies it to control tensor sampling operators in spectral norm.

  • The theorem is presented as a corollary of a Chernoff bound for finite-dimensional operators.
  • The proof studies the operator PT RΩPT and seeks to show that it remains close to its expected value PT in spectral norm.
  • The sampling operator is decomposed into component operators Tijk acting on tensors Z.
  • The component-operator norm is bounded using the projected tensor basis elements.
  • The argument invokes the stated inequality under a sampling condition and concludes the proof.

PROOF OF LEMMA 4.1

The proof begins from a tensor in the sampling null space and assumes the relevant operator deviation is at least 1/2.

  • The argument considers a tensor Z satisfying PΩ(Z) = 0.
  • It proceeds under the assumption that ∥PT RΩPT − PT∥op is at least 1/2.
  • The proof is concluded after this setup.

APPENDIX C PROOF OF PROPOSITION 4.1 CONDITION 2

This appendix proves Condition 2 of Proposition 4.1 by constructing a golfing-scheme helper tensor and combining sampling-operator bounds under incoherence assumptions.

  • PROOF OF PROPOSITION 4.1 CONDITION 2: The proof relies on supplementary lemmas to establish Condition 2 of Proposition 4.1.
  • PROOF OF PROPOSITION 4.1 CONDITION 2: The supporting lemmas bound operator deviations and ℓ∞,2∗ distances with high probability when p satisfies the theorem’s sampling condition.
  • PROOF OF PROPOSITION 4.1 CONDITION 2: A tensor helper Y is constructed iteratively using a golfing scheme over a union of smaller sampling sets Ωt.
  • PROOF OF PROPOSITION 4.1 CONDITION 2: The construction initializes W0 = 0, updates the iterates, and sets Y = Wt0, ensuring PΩ(Y) = Y.
  • PROOF OF PROPOSITION 4.1 CONDITION 2: The residual Dt is defined from U∗V⊤ and PT(Wt), then controlled using sampling bounds and auxiliary lemmas.
  • PROOF OF PROPOSITION 4.1 CONDITION 2: The bounds use incoherent tensor factors and estimates involving tensor tubes and the standard incoherent condition.

Proof of Lemma C.1

Lemma C.1 bounds the deviation between the sampled and expected projected operators by decomposing tensor columns and applying concentration inequalities with union bounds.

  • The proof decomposes the sampled operator into contributions from independent tensors C(ijk).
  • The tensor basis construction identifies the nonzero entry produced by a component indexed by j.
  • The argument applies an extension of Theorem A.1 to obtain a probability bound for the operator deviation.
  • For each tensor column, the proof represents zero-mean independent tensor columns as vectorized vectors and bounds their ℓ2 norms.
  • The incoherent condition and concentration estimates control the column and row contributions, after which a union bound is applied.
  • The entrywise deviation is finally bounded using another concentration step and a union bound over tensor entries.
Loading 1502.04689v2…