PaperlayerView exact revision on arXiv

Source-linked AI summary

A New Convex Relaxation for Tensor Completion

Bernardino Romera-Paredes, Massimiliano Pontil

arXiv:1307.4653v1cs.LGmath.OCstat.ML

TL;DR

Tensor completion requires recovering tensors from linear measurements, but the commonly used tensor trace norm has limited relaxation quality. The paper proposes a Euclidean-ball convex relaxation and an ADMM-based solver, with experiments indicating significantly improved estimation error while remaining computationally tractable.

  • Problem

    Tensor completion needs a convex proxy for average matricization rank, but tensor trace norm is not a tight convex relaxation of tensor rank.

  • Method

    The paper develops a convex relaxation on the Euclidean ball and solves its regularization problem using ADMM with a subgradient method for the proximity operator.

  • Results

    Empirical comparisons consistently indicate improved estimation error over tensor trace norm regularization while remaining computationally comparable on the considered problems.

  • Takeaways & Limitations

    The proposed convex regularizer may provide a tighter and practically useful alternative to tensor trace norm regularization for tensor completion.

  • Takeaways & Limitations

    The experiments and computational-comparability claim are limited to the range of problems considered, and the paper notes a Gaussian sampling assumption for one estimator.

Abstract

from arXiv · show

We study the problem of learning a tensor from a set of linear measurements. A prominent methodology for this problem is based on a generalization of trace norm regularization, which has been used extensively for learning low rank matrices, to the tensor setting. In this paper, we highlight some limitations of this approach and propose an alternative convex relaxation on the Euclidean ball. We then describe a technique to solve the associated regularization problem, which builds upon the alternating direction method of multipliers. Experiments on one synthetic dataset and two real datasets indicate that the proposed method improves significantly over tensor trace norm regularization in terms of estimation error, while remaining computationally tractable.

1 Introduction

The paper studies tensor completion from linear measurements and proposes a convex regularizer with an associated optimization method. It argues that tensor trace norm regularization has a fundamental limitation and reports improved estimation error while remaining computationally tractable.

  • Tensor completion learns a tensor from linear measurements and has applications including collaborative filtering, computer vision, and medical imaging.
  • The tensor trace norm averages the trace norms of tensor matricizations, extending matrix trace norm regularization to tensors.
  • The paper proves that tensor trace norm regularization is not a tight convex relaxation of tensor rank.
  • The proposed convex relaxation is solved using an alternating direction method of multipliers approach combined with a subgradient method for the proximity operator.
  • Experiments on one synthetic and two real datasets indicate significantly lower estimation error than tensor trace norm regularization while remaining computationally tractable.

2 Preliminaries

The paper formulates tensor completion as recovery from noisy linear measurements and uses matricization ranks to characterize tensor simplicity. It reviews the tensor trace norm as a convex proxy derived from matrix spectral-norm geometry.

  • An N-order tensor is an array indexed across N modes, with vectors and matrices treated as first- and second-order tensors.
  • Mode-n matricization arranges mode-n fibers as columns of a matrix, with column order arbitrary when used consistently.
  • The learning model observes y = I(W0) + ξ, where I is a linear measurement operator and ξ is disturbance noise.
  • For tensor completion, I measures prescribed tensor entries, and the objective is to recover W0 from (I, y).
  • The regularizer encourages tensors with few degrees of freedom, motivating the average rank of their matricizations.
  • The tensor trace norm averages the nuclear norms of all matricizations and coincides with ordinary matrix trace norm when the tensor has order two.
  • Its matrix analogue is motivated as the tightest convex lower bound to rank on the spectral unit ball, obtained through convex-envelope and conjugate constructions.

3 Alternative Convex Relaxation

The paper shows that tensor trace norm is not generally the tight convex relaxation of matricization rank and develops an alternative relaxation on Euclidean-ball geometry. The new relaxation can exceed tensor trace norm on unequal-mode tensors while remaining a convex lower bound.

  • The section proves that tensor trace norm is not a tight convex relaxation of tensor rank and introduces an alternative convex relaxation.
  • Computing the convex envelope of average matricization rank is difficult because the rank function is composite, so approximations are required.
  • The alternative relaxation studies tensor rank on a Euclidean ball and uses the convex envelope of vector cardinality on an ℓ2-ball of radius α.
  • The proposed function Ωα is a convex lower bound for tensor rank on αG2, including G∞ when G∞ ⊂ αG2.
  • The exhibited unequal-dimension tensors are constructed through a mode matricization’s singular value decomposition and can vary through arbitrary left singular vectors.
  • When pmin < pmax, infinitely many tensors in G∞ satisfy Ωα(W) > ∥W∥tr for α = √pmin, while Ω1(W) ≥ ∥W∥tr on G2.
  • The construction is motivated by the non-invariance of spectral norm under tensor matricization, whereas the Euclidean or Frobenius norm is invariant.

4 Optimization Method

The optimization method applies ADMM to decouple interdependent matricization regularizers, then computes the proposed proximity operator through spectral-function and projected-subgradient techniques. This framework supports both tensor trace norm and the proposed regularizer.

  • ADMM is used to solve the regularization problem associated with the proposed tensor regularizer.
  • The general formulation covers tensor trace norm regularization and the proposed regularizer through a convex spectral function Ψ.
  • ADMM introduces auxiliary tensors B1, …, BN to decouple the interdependent matricization terms.
  • The augmented Lagrangian uses a positive parameter β and Lagrange multipliers associated with the auxiliary-tensor constraints.
  • The method alternates updates under the ADMM iterative scheme, with some updates obtained directly and others expressed through proximity operators.
  • For Ψ based on the ℓ1 gauge, the proximity operator is soft thresholding, while the proposed choice uses ω∗∗α.
  • The proximity calculation for ω∗∗α uses conjugate-function identities, scaling properties, and a projected subgradient method over an ordered nonnegative set.
  • The projected subgradient implementation initializes a step size and feasible solution, updates the best iterate, and stops after the stated update-based condition.

5 Experiments

Experiments compare the proposed convex regularizer with tensor trace norm regularization on synthetic, educational, and video completion tasks. The proposed method shows lower estimation error, with computational overhead shrinking as tensor size increases.

  • 5 Experiments: The experiments evaluate both methods on one controlled synthetic problem and two real tensor-completion datasets.The real datasets are ILEA examination data and the Ocean video.
  • 5.1 Synthetic Dataset: The synthetic study generates a 3-order 40×20×10 tensor using Tucker decomposition and Gaussian components, then adds Gaussian noise.Training, validation, and test sets contain 10%, 45%, and 45% of tensor elements, respectively.
  • 5.1 Synthetic Dataset: For p = 20, the proposed method’s running time is 22.661 times the trace-norm method, decreasing to 1.9113 at p = 200.The decreasing ratio reflects the increasing importance of singular value decomposition, which both methods use.
  • 5.2 School Dataset: The proposed approach significantly improves RMSE over tensor trace norm regularization on the ILEA dataset, with paired-test p-values below 0.01 for every sample size m.ILEA is represented as a 5-order tensor with dimensions 139×2×3×11×3.
  • 5.3 Video Completion: On the Ocean video, the proposed approach is noticeably better in RMSE, with paired-test p-values below 0.01 for every m and below 10^-6 when m > 5 × 10^4.The video tensor has dimensions 160×112×3×32, and results average ten repetitions.

6 Conclusion

The paper proposes a convex relaxation for tensor matricization ranks and compares it with tensor trace norm regularization. Experiments indicate consistently lower estimation error while computational cost remains comparable on the tested problems.

  • 6 Conclusion: The proposed method is a convex relaxation for the average rank of tensor matricizations.
  • 6 Conclusion: Tensor trace norm regularization is shown not to be tight, motivating comparison with the proposed relaxation.
  • 6 Conclusion: Empirical comparisons indicate consistently lower estimation error and computational comparability on the considered tensor-completion problems.

Appendix

The appendix presents an auxiliary result and the main steps for computing an approximate projection.

  • Appendix: The appendix describes an auxiliary result and the main steps for computing an approximate projection.

A A Useful Lemma

The lemma compares convex envelopes on a product domain with those obtained after restricting to a diagonal subset. This yields lower bounds for tensor-rank relaxations, including the tensor trace norm and the Euclidean-ball function Ωα.

  • A Useful Lemma: Lemma 4 compares the convex envelope of g on a smaller diagonal set with the convex envelope of h(x)=g(x,…,x) on D.It states that the former cannot be larger than the latter.
  • A Useful Lemma: Applying the lemma derives a convex lower bound for the function R in equation (2).
  • A Useful Lemma: On αG2, the convex envelope of R is lower bounded by the function Ωα in equation (6).
  • A Useful Lemma: On G∞, the convex envelope of R is bounded below by the average of the trace norms of the tensor matricizations.

B Computation of an Approximated Projection

The paper computes an approximate Euclidean projection onto an ordered nonnegative set by decomposing it into nested convex sets. A recursive projection formula and Proposition 5 support the resulting sequential algorithm.

  • Computation of an Approximated Projection: The target set is S = {v ∈ R^d : v1 ≥ ··· ≥ vd ≥ 0}.Algorithm 2 computes an output in this set, initialized from y and updated over coordinates.
  • Computation of an Approximated Projection: S is represented as the smallest set in a series of nested sets, enabling sequential approximate projection.The sequential construction uses associated projection operators for the nested convex sets.
  • Computation of an Approximated Projection: The recursive step only requires computing P_Si+1(v) for v ∈ S_i, rather than full knowledge of P_Si.A subsequent proposition supplies the recursive formula for this step.
  • Computation of an Approximated Projection: Proposition 5 handles repeated final coordinates by identifying the largest trailing block with equal entries before applying the projection formula.It expresses the first i elements using the last j equal entries and uses the all-ones vector 1_d in the characterization.
  • Computation of an Approximated Projection: Algorithm 2 summarizes the approximate projection method based on Proposition 5.
Loading 1307.4653v1…