PaperlayerView exact revision on arXiv

Source-linked AI summary

Low-rank tensor completion: a Riemannian manifold preconditioning approach

Hiroyuki Kasai, Bamdev Mishra

arXiv:1605.08257v1cs.LGcs.NAmath.NAmath.OCstat.ML

TL;DR

The paper addresses completion of low-rank tensors from partially observed entries when the rank is known or estimated. It proposes a Tucker-symmetry- and least-squares-aware Riemannian metric for batch and online algorithms, and reports superior performance across benchmarks.

  • Problem

    The paper addresses low-rank tensor completion from partially observed entries when the rank is known or estimated.

    Source: §1 · p. 1

  • Method

    A Riemannian metric tailored to least-squares structure and Tucker symmetry supports quotient-manifold preconditioned optimization.

    Source: §1 · p. 2, §2 · p. 3, §3 · p. 4

  • Results

    The proposed algorithms show superior performance on different benchmarks.

    Source: §6 · p. 10

  • Takeaways & Limitations

    The proposed metric provides a Riemannian optimization framework for preconditioned batch conjugate-gradient and online stochastic-gradient algorithms.

    Source: §1 · p. 2, §6 · p. 10

    The metric’s positive-definiteness conditions assume full-rank core unfoldings and rank inequalities r1 ≤ r2r3, r2 ≤ r1r3, and r3 ≤ r1r2.

    Source: §2 · p. 3

Abstract

from arXiv · show

We propose a novel Riemannian manifold preconditioning approach for the tensor completion problem with rank constraint. A novel Riemannian metric or inner product is proposed that exploits the least-squares structure of the cost function and takes into account the structured symmetry that exists in Tucker decomposition. The specific metric allows to use the versatile framework of Riemannian optimization on quotient manifolds to develop preconditioned nonlinear conjugate gradient and stochastic gradient descent algorithms for batch and online setups, respectively. Concrete matrix representations of various optimization-related ingredients are listed. Numerical comparisons suggest that our proposed algorithms robustly outperform state-of-the-art algorithms across different synthetic and real-world datasets.

1 Introduction

The paper studies low-rank tensor completion with known or estimated rank, focusing on third-order tensors while allowing straightforward generalization to higher orders. It proposes a Tucker-symmetry-aware Riemannian metric for batch and online optimization.

1 Introduction

  • Low-rank tensor completion seeks a tensor with known or estimated rank from entries observed only at selected indices.The paper focuses on third-order tensors and states that its developments generalize straightforwardly to higher orders.Source: §1 · p. 1
  • Unfolding-based nuclear-norm regularization can perform well, but its high-dimensional SVD computations make large-scale use nontrivial.Tucker-decomposition methods offer another route to large-scale algorithms.Source: §1 · p. 1
  • The proposed Tucker-manifold approach uses a least-squares-tuned metric to develop competitive algorithms that exploit Tucker symmetry.It views the rank-constrained search space as a product of simpler spaces with symmetries, unlike the embedded-submanifold and Euclidean-metric approach of Kressner et al..Source: §1 · p. 2
  • The paper develops preconditioned conjugate gradient for batch completion and stochastic gradient descent for online completion, with numerical comparisons on synthetic and real-world benchmarks.It reports implementation in the Manopt Matlab toolbox and provides concrete formulas for optimization ingredients.Source: §1 · p. 2

2 Exploiting the problem structure

The section builds a Riemannian metric by combining Tucker-decomposition symmetry with the least-squares cost structure. A block-diagonal Hessian approximation supplies the metric’s factor weights.

2 Exploiting the problem structure

  • Tucker decomposition is non-unique under orthogonal transformations, so the search space identifies equivalent factor-and-core representations on a quotient manifold.The total space is a product of three Stiefel manifolds and the core tensor space; the quotient removes the non-isolated minima associated with this invariance.Source: §2 · pp. 2–3
  • A block-diagonal approximation to the full-data least-squares Hessian provides a computationally simpler basis for metric tuning.The cost is quadratic in the tensor and individually in its Tucker factors and core.Source: §2 · p. 3
  • The metric’s positive-definiteness argument assumes full-rank core unfoldings and rank inequalities r1 ≤ r2r3, r2 ≤ r1r3, and r3 ≤ r1r2.The paper describes these inequalities as a reasonable assumption.Source: §2 · p. 3
  • The proposed metric weights each factor’s tangent inner product by its core-unfolding Gram matrix and uses a Euclidean inner product for the core component.The metric is induced from the block-diagonal Hessian approximation and is invariant along Tucker equivalence classes.Source: §2 · p. 3

3 Notions of manifold optimization

The section explains how quotient-manifold objects are represented and computed in the total space. Horizontal lifts, metric-compatible projections, retractions, and vector transports provide the ingredients for first-order optimization.

3 Notions of manifold optimization

  • A quotient tangent vector is represented by its unique horizontal lift, orthogonal to directions that move only within the same equivalence class.The tangent space splits into vertical and horizontal subspaces, with the horizontal subspace defined using the metric.Source: §3 · p. 4
  • The metric descends to the quotient when its value is independent of the chosen representative, enabling quotient gradients to be computed through total-space matrix representations.The proposed metric satisfies this invariance, making the quotient a Riemannian submersion of the total space.Source: §3 · p. 4
  • The horizontal projector removes the vertical component by solving coupled Lyapunov equations for skew-symmetric matrices.The equations are solved with Matlab’s pcg routine and a symmetric preconditioner based on a Gauss-Seidel approximation.Source: §3 · p. 5
  • A retraction combines orthogonal-factor extraction for the Stiefel components with an additive update to the core, then maps the result to the quotient.The resulting quotient retraction does not depend on the chosen matrix representatives.Source: §3 · p. 5
  • Vector transport projects a transported tangent vector back to the horizontal space, and its cost depends on the projection and retraction operations.The tangent-space and horizontal-space projections provide matrix representatives for the abstract quotient objects.Source: §3 · pp. 4–5

4 Riemannian algorithms for (1)

The paper derives batch preconditioned conjugate-gradient and online stochastic-gradient algorithms using a tailored Riemannian metric. It gives the gradient, step-size, update, and computational-cost ingredients for both settings.

Riemannian algorithms for (1)

  • The tailored metric drives preconditioned batch conjugate-gradient and online stochastic-gradient algorithms; theory guarantees convergence to a stationary point, while simulations often reach global minima.The batch method uses Manopt’s conjugate-gradient implementation, and the online method uses stochastic gradient descent.Source: §4 · p. 6
  • The Riemannian gradient is obtained by scaling the cost-specific partial derivatives and lifting them horizontally; its computation costs O(|Ω|r1r2r3).The Euclidean gradient is represented by a sparse residual tensor, and the metric scaling uses inverses of core-factor products.Source: §4 · pp. 6–7
  • A degree-2 polynomial approximation along a search direction gives a closed-form initial step-size guess at cost O(|Ω|r1r2r3).The approximation exploits the least-squares objective over the manifold.Source: §4 · p. 7
  • Online SGD updates the factor matrices and core for each randomly sampled frontal slice, using a rank-one Riemannian gradient followed by retraction.The step size follows γk = γ0/(1 + γ0λk); γ0 is selected during pre-training and λ is fixed to 10^-7.Source: §4 · p. 7
  • Batch iterations cost O(|Ω|r1r2r3), matching geomCG, while each online update has a separate cost depending on slice observations, dimensions, ranks, and slices seen.The online cost is O(|Ωslice|r1r2 + n1r2_1 + n2r2_2 + Tr2_3 + r1r2r3).Source: §4 · p. 7

5 Numerical comparisons

The experiments compare the proposed batch and online algorithms with established tensor-completion methods across synthetic and real datasets. The reported comparisons favor the proposed methods in large-scale, low-sampling, noisy, ill-conditioned, and selected real and online settings.

Experimental setup

  • The batch comparisons include Tucker-based and nuclear-norm methods; for large-scale instances, only geomCG is compared because the other algorithms cannot handle them.Experiments use five runs per scenario and evaluate test MSE on a held-out set Γ.Source: §5 · p. 7

Cases S3–S4

  • On large and scarcely sampled synthetic tensors, the proposed method outperforms geomCG, with test error decreasing while geomCG’s increases.The large-scale tests include tensors up to 10000 × 10000 × 10000; the low-sampling test uses OS = 4.Source: Figure 2 · p. 8, §5 · pp. 8–9

Cases S5–S6

  • Across condition numbers 5, 50, and 100, the proposed method outperforms geomCG; under noise, it converges faster while test error is almost the noise floor.The noise floor is reported as ϵ²∥PΩ(X ⋆)∥²_F.Source: Figure 2 · p. 8, §5 · p. 9

Case S7

  • For rectangular synthetic instances, the proposed method converges faster than geomCG across the tested tensor sizes and rank configurations.The comparisons cover two sets of rectangular dimensions and ranks.Source: Figure 2 · p. 8, §5 · p. 9

Case S2

  • On small synthetic tensors, the proposed method converges faster than other algorithms, while it and geomCG obtain the lowest test errors.The tests vary tensor size and over-sampling ratio.Source: Figure 2 · p. 8, §5 · p. 8

Case R2

  • On MovieLens-10M, the proposed method gives lower test errors than geomCG across ranks.The dataset contains 10,000,054 ratings and fewer than 0.002% known entries.Source: Table 2 · p. 9, §5 · p. 9

Case O

  • On the Airport Hall sequence, both proposed algorithms achieve lower test errors than TeCPSGD [16] and OLSTEC [10]; on synthetic data, online and batch methods have the same asymptotic convergence behavior.The synthetic instance has 10% observed entries.Source: Figure 3 · p. 10, §5 · p. 10

6 Conclusion

The paper concludes that its tailored Riemannian metric supports preconditioned batch and online tensor-completion algorithms. Numerical comparisons suggest superior performance across different benchmarks.

Conclusion

  • The proposed methods are preconditioned batch conjugate-gradient and online stochastic-gradient algorithms for tensor completion.They use a novel Riemannian metric within a Riemannian optimization framework.Source: §6 · p. 10
  • The approach exploits Tucker-decomposition symmetry and the least-squares structure of the cost function.The metric is the inner product used in the Riemannian optimization framework.Source: §6 · p. 10
  • Numerical comparisons suggest superior performance across different benchmarks.Source: §6 · p. 10

A Proof and derivation of manifold-related ingredients

The appendix presents the total-space representation used for Tucker factors and core, then describes the equivalence classes induced by Tucker decomposition’s orthogonal invariance.

A Proof and derivation of manifold-related ingredients

A.1 Tangent space characterization and the Riemannian metric

The appendix characterizes tangent, normal, vertical, and horizontal spaces for the Tucker-factor representation. These spaces describe the local geometry and quotient directions used in the optimization framework.

A.1 Tangent space characterization and the Riemannian metric

  • The tangent space at a Tucker representation is the product of the tangent spaces of its individual factor manifolds.The tangent vector is represented by factor and core components.Source: §A.1 · p. 13

A.2 Characterization of the normal space

  • The normal space is characterized through vectors orthogonal to every tangent vector under the proposed metric.The characterization reduces factor components to symmetric matrices and sets the orthogonal-complement component to zero.Source: §A.2 · p. 13

A.3 Characterization of the vertical space

  • The vertical space consists of tangent directions that linearize changes within the same Tucker equivalence class.These directions arise from orthogonal rotations of the factors and corresponding core transformations.Source: §A.3 · p. 14

A.4 Characterization of the horizontal space

  • The horizontal space is defined by metric orthogonality to the vertical space, excluding directions that only move along an equivalence class.Its characterization follows by imposing orthogonality to every vertical direction.Source: §A.4 · p. 14

A.5 Proof of Proposition 1

The proof establishes that horizontal tangent lifts represent the same quotient tangent vector across equivalent Tucker representations. It also verifies that the proposed metric is invariant under those transformations.

A.5 Proof of Proposition 1

  • Horizontal lifts at equivalent Tucker representations correspond to the same tangent vector on the quotient manifold.The proof compares the lifted directions under orthogonal transformations of the factors and core.Source: §A.5 · pp. 14–15
  • A function on the quotient is lifted to the total space by composition with the quotient map, making it constant across each equivalence class.The proof differentiates this invariance to relate derivatives at equivalent representations.Source: §A.5 · pp. 14–15
  • The metric has the claimed invariance when its terms are evaluated on the corresponding transformed horizontal lifts.The proof checks the factor terms and concludes the invariant property.Source: §A.5 · p. 16

A.6 Proof of Proposition 2 (derivation of the tangent space projector)

The proof derives the tangent-space projector by removing the component normal to the tangent space. It formulates the projector using the normal-space characterization and a Lyapunov equation.

A.6 Proof of Proposition 2 (derivation of the tangent space projector)

  • The tangent-space projector is obtained by extracting the ambient component normal to the tangent space.The proof uses the matrix characterization of the normal space to derive the operator.Source: §A.6 · p. 16
  • The factor matrices must satisfy the tangent-space conditions when deriving the projector.The proof invokes the defining conditions for the tangent space.Source: §A.6 · p. 16
  • The projector derivation yields a Lyapunov equation, which the implementation solves with Matlab’s lyap routine.The passage identifies the routine used to solve the equation efficiently.Source: §A.6 · p. 16

A.7 Proof of Proposition 3 (derivation of the horizontal space projector)

The appendix derives the horizontal-space projector by subtracting vertical directions and derives the Riemannian gradient using the scaled metric. The resulting calculations use coupled Lyapunov equations and an observed-entry residual.

A.7 Proof of Proposition 3 (derivation of the horizontal space projector)

  • The horizontal-space projector subtracts the vertical component from a tangent vector to produce its horizontal component.The operator is expressed using skew-symmetric matrices determined by the horizontal-space conditions.Source: §A.7 · p. 17
  • The projector’s skew-symmetric matrices are determined by coupled Lyapunov equations.The equations are solved with Matlab’s pcg routine combined with a preconditioner from a Gauss-Seidel approximation.Source: §A.7 · p. 17

A.8 Proof of Proposition 4 (derivation of the Riemannian gradient formula)

  • The auxiliary sparse tensor S is twice the observed-entry reconstruction residual divided by the number of known entries.The residual compares the observed entries of the Tucker reconstruction with those of the target tensor.Source: §A.8 · p. 18
  • The scaled metric further scales the partial derivatives when forming the Riemannian gradient.The horizontal lift of the quotient gradient is obtained by applying Ψ to the Euclidean gradient.Source: §A.8 · p. 18
  • The factor components of the gradient are obtained by solving Lyapunov equations.The appendix states that these equations are solved with Matlab’s lyap routine.Source: §A.8 · p. 19

B Additional numerical comparisons

Additional experiments compare the proposed algorithms across synthetic and real-world tensor-completion settings. The reported comparisons include favorable convergence, error, or image-recovery performance across varied scales, sampling rates, conditioning, shapes, and online data.

Case S2: small-scale instances

  • On small synthetic instances, the proposed method is competitive or faster than geomCG, HalRTC, and TOpt, with competitive or lower train and test errors, especially at OS 10.The small-scale cases use tensors up to 200 × 200 × 200; the reported error comparison names geomCG and HalRTC.Source: B Additional numerical comparisons · p. 19

Cases S3–S4: large-scale and low-sampling instances

  • On large-scale synthetic tensors, the proposed algorithm outperforms geomCG; at OS 5, its error decreases stably across five runs while geomCG errors increase.The low-sampling comparison uses tensors of size 10000 × 10000 × 10000 and rank (5, 5, 5).Source: B Additional numerical comparisons · p. 19

Cases S5–S6: ill-conditioning and noise

  • Case S5 (OS = 5), with a diagonal core having exponentially decaying positive values and condition numbers 5, 50, and 100, the proposed algorithm outperforms geomCG on the training set for all considered condition numbers.Source: B Additional numerical comparisons · p. 19

Case S7: rectangular instances

  • For rectangular instances, the proposed algorithm outperforms geomCG in asymmetric-rank cases on both train and test comparisons.The evaluated cases include unequal tensor dimensions and ranks.Source: B Additional numerical comparisons · pp. 19–20

Case S8: medium-scale instances

  • On medium-scale tensors up to 1500 × 1500 × 1500, the proposed algorithm performs better than geomCG in all cases.These comparisons cover ranks (5, 5, 5), (10, 10, 10), and (15, 15, 15).Source: B Additional numerical comparisons · p. 20

Case R1: hyperspectral image

  • On the Ribeira hyperspectral image, the proposed algorithm has lower test errors than the other algorithms and good image-recovery performance, especially at lower sampling ratios.The recovery comparisons use OS values 11 and 22.Source: B Additional numerical comparisons · p. 20

Case R2: MovieLens-10M

  • On MovieLens-10M, the convergence plots across four ranks show superior performance for the proposed algorithm.The comparisons cover ranks (4, 4, 4), (6, 6, 6), (8, 8, 8), and (10, 10, 10).Source: B Additional numerical comparisons · p. 20

Case O: online instances

  • For online instances, the proposed stochastic gradient method converges similarly to or faster than the batch method on synthetic tensors and the Airport Hall video sequence.The synthetic cases use tensors of size 100 × 100 × 5000 and 100 × 100 × 10000; Airport Hall comparisons also report superior final train and test MSEs for the proposed algorithms.Source: B Additional numerical comparisons · p. 20
Loading 1605.08257v1…