PaperlayerView exact revision on arXiv

Source-linked AI summary

Estimation of low-rank tensors via convex optimization

Ryota Tomioka, Kohei Hayashi, Hisashi Kashima

arXiv:1010.0789v2stat.MLmath.NA

TL;DR

The paper tackles estimation of low-rank Tucker tensors from partial observations while avoiding the local-minimum issues of conventional non-convex procedures. It proposes three trace-norm-based convex formulations and a core-level PARAFAC heuristic, achieving strong reconstruction and predictive results across synthetic and real-world data. The approaches also address cases where low rank is concentrated in particular modes.

  • Problem

    Conventional tensor-decomposition estimation is generally non-convex, while tensor rank is difficult to compute and directly generalizing matrix trace norm is not straightforward.

  • Method

    The paper proposes three convex trace-norm formulations for partially observed Tucker tensors and applies PARAFAC to the estimated core as an interpretability heuristic.

  • Results

    The approaches show superior predictive performance against conventional EM-based Tucker estimation; tensor completion nearly perfectly reconstructs a simulated tensor from 35% observations, and the mixture approach is more effective when only certain modes are low-rank.

  • Takeaways & Limitations

    The methods can recover partially observed low-rank tensors while automatically handling mode ranks, and the core heuristic can recover true factors despite PARAFAC rank misspecification.

  • Takeaways & Limitations

    Further work is needed for non-Gaussian noise, tensors too large for RAM, and theoretical analysis of threshold behaviour.

Abstract

from arXiv · show

In this paper, we propose three approaches for the estimation of the Tucker decomposition of multi-way arrays (tensors) from partial observations. All approaches are formulated as convex minimization problems. Therefore, the minimum is guaranteed to be unique. The proposed approaches can automatically estimate the number of factors (rank) through the optimization. Thus, there is no need to specify the rank beforehand. The key technique we employ is the trace norm regularization, which is a popular approach for the estimation of low-rank matrices. In addition, we propose a simple heuristic to improve the interpretability of the obtained factorization. The advantages and disadvantages of three proposed approaches are demonstrated through numerical experiments on both synthetic and real world datasets. We show that the proposed convex optimization based approaches are more accurate in predictive performance, faster, and more reliable in recovering a known multilinear structure than conventional approaches.

1. Introduction.

The paper addresses limitations of conventional non-convex Tucker estimation by proposing three convex formulations for recovering low-rank tensors from partial observations. Experiments compare these approaches with conventional methods and evaluate a heuristic for factor interpretability.

  • Motivation: Conventional Tucker and CP estimation procedures are generally non-convex, offering only local convergence guarantees and potentially poor local minima.HOOI may converge to a stationary point that is not even a local minimizer.
  • Contributions: The paper proposes three formulations for estimating low-rank tensors.
  • Contributions: The three approaches extend trace-norm regularization through a single unfolding, simultaneous mode penalties, or a mixture of mode-wise low-rank tensors.The constraint approach avoids choosing one mode but may require all modes to be low-rank; the mixture approach relaxes that assumption.
  • Results: The proposed approaches show superior predictive performance to conventional EM-based Tucker estimation on synthetic and real-world datasets.
  • Results: A heuristic is evaluated for improving the interpretability of the core tensor obtained from the proposed methods.

2. Low rank matrix and tensor.

This section relates matrix rank to trace-norm regularization and reviews tensor rank, Tucker decomposition, and mode-k rank. It motivates tensor trace-norm methods by showing both the tractability of unfolded mode ranks and the difficulty of directly generalizing matrix trace norm.

  • 2.1. Rank of a matrix and the trace norm: Matrix rank is the number of nonzero singular values, but direct rank minimization is non-convex and NP-hard.The singular-value decomposition expresses the matrix through orthogonal factors and singular values.
  • 2.1. Rank of a matrix and the trace norm: The trace norm is the tightest convex lower bound of matrix rank and sums the singular values.Its nondifferentiability at the origin promotes singular values to zero when used for regularization.
  • 2.1. Rank of a matrix and the trace norm: Spectral soft-thresholding shrinks singular values and sets those smaller than λ to zero, usually producing a low-rank matrix.
  • 2.2. Rank of a tensor: A Tucker decomposition represents a tensor using a core tensor and mode-specific factor matrices, while CP decomposition uses rank-one components.Tucker decomposition is more general than CP decomposition.
  • 2.2. Rank of a tensor: Tensor rank based on the minimum number of CP components is hard to compute, so generalizing matrix trace norm is not straightforward because Tucker cores are generally non-diagonal.
  • 2.2. Rank of a tensor: Mode-k rank equals the matrix rank of the mode-k unfolding, making a Tucker low-rank tensor low-rank when appropriately unfolded.Mode-k ranks are computable through the ranks of K matrices.

3. Three strategies to extend the trace-norm regularization to tensors.

The paper extends trace-norm regularization to tensors through three convex strategies based on unfoldings, joint mode penalties, and mixtures of tensors. These formulations support partial-observation reconstruction and a core-based heuristic for interpretable factors.

  • 3.1. Tensor as a matrix: The first strategy unfolds the tensor along one mode and minimizes the trace norm of that matrix unfolding.It is appropriate when the tensor is low-rank in the selected mode.
  • 3.2. Constraint: The second strategy jointly penalizes every tensor mode with trace norms using auxiliary unfolding matrices and a convex reformulation solved with ADMM.It removes arbitrariness in selecting one mode but may impose an overly strict joint-low-rank assumption.
  • 3.1. Tensor as a matrix: In the noiseless case, O(˜n_k^6/5 r_k log(˜n_k)) samples suffice for perfect recovery when the selected mode rank is not too high.Recovery of the mode-k unfolding recovers the whole tensor, regardless of ranks in other modes.
  • 3.1. Tensor as a matrix: The single-unfolding strategy depends on choosing a suitable mode, because a large selected-mode rank prevents recovery from a small number of samples.
  • 3.3. Mixture: The mixture strategy relaxes joint low-rankness by predicting with K tensors, each regularized to be low-rank in every mode.
  • 3.4. Interpretation: Applying PARAFAC to the estimated core separates prediction from interpretation and narrows the component search using automatically obtained core dimensions.The heuristic is reported as more robust when the PARAFAC rank is misspecified.

4. Optimization.

The proposed tensor estimators are solved with ADMM by splitting primal and auxiliary variables, then alternating closed-form updates and multiplier adjustments. The method supports the three formulations while using spectral soft-thresholding for trace-norm regularization and a relative duality-gap stopping rule.

  • ADMM framework: ADMM is applied to the optimization problems for all three tensor-estimation formulations.The algorithms begin from initial points and use the ADMM framework for the corresponding augmented Lagrangians.
  • ADMM framework: The augmented Lagrangian combines convex objectives with a quadratic penalty that enforces the equality constraint.The penalty parameter need not become very large, avoiding the poor conditioning associated with penalty methods.
  • ADMM framework: ADMM decouples minimization over x and z, using the updated x^(t+1) when computing z^(t+1).This splitting makes the updates easier than the joint augmented-Lagrangian minimization.
  • Stopping and scaling: The algorithms stop when the relative duality gap meets the specified criterion, which is invariant to the scale of observed entries and problem size.The dual objective uses the largest dual value obtained so far, while the raw multiplier may violate dual constraints.
  • As a Matrix: For the “as a matrix” approach, observed entries are updated from y while unobserved entries use the current mode-k prediction.When λ → 0, the observed entries are directly overwritten by the observed values.
  • As a Matrix: The auxiliary tensor updates use spectral soft-thresholding on the matricized input, implementing the trace-norm regularization.The operation is applied to the mode-k unfolding in the single-mode approach and analogously across modes in the constraint formulation.

5. Numerical experiments.

Experiments on synthetic tensors and amino acid fluorescence data compare the proposed convex approaches with Tucker, PARAFAC, and EM-based baselines. The results assess predictive accuracy, computation time, threshold behavior, and factor interpretability.

  • Experimental setup: The experiments use two synthetic datasets and amino acid fluorescence data, comparing the proposed methods with Tucker, PARAFAC, and EM-based baselines.The synthetic experiments include rank-(7,8,9) and rank-(50,50,5) tensors of dimensions 50 × 50 × 20.
  • Synthetic experiments: At 35% observation, “Constraint” achieves nearly perfect generalization, with error transitioning from above 1 to approximately 10^-3.The transition is sharper than those reported for the mode-specific “As a Matrix” strategy and the “Mixture” approach.
  • Synthetic experiments: The threshold experiment measures the observation fraction required for generalization error below 0.01 against the sum of the tensor’s true mode-k ranks.The sum is defined using min(r1, r2r3) + min(r2, r3r1) + min(r3, r1r2).
  • Synthetic experiments: For the rank-(50,50,5) tensor, “Constraint” performs poorly, while “mode 3” and “Mixture” perform clearly better because the tensor is low-rank only in its third mode.This experiment demonstrates differing behavior across approaches when low-rank structure is concentrated in one mode.
  • Amino acid fluorescence data: On amino acid fluorescence data, “Constraint” decreases generalization error quickly, while rank-(4,4,4) Tucker cannot reduce error below 0.05.The “Constraint” result is comparable to PARAFAC with the correct dimension, and rank-(3,3,3) Tucker performs similarly to PARAFAC after more than half the entries are observed.
  • Amino acid fluorescence data: Applying PARAFAC to the proposed method’s core produces major factors more similar to the three-component PARAFAC solution than to a redundant four-component direct fit.The core used for this comparison has dimensionality 4 × 4 × 5, and the authors report greater robustness than applying four-component PARAFAC directly.

6. Summary.

The paper proposes three convex trace-norm approaches for estimating partially observed low-rank tensors, with automatic rank determination. Experiments show strong reconstruction, predictive performance, computational speed, and factor-recovery results, while also identifying method-specific limitations and future extensions.

  • Summary: The three proposed strategies extend trace-norm regularization to estimate partially observed low-rank tensors through convex optimization.The tensor decomposition rank is automatically determined during optimization.
  • Summary: 35% observations yielded nearly perfect reconstruction with the “Constraint” approach in the simulated experiment.The fraction of samples at the sharp threshold was empirically roughly proportional to the sum of mode-k ranks.
  • Summary: The “Mixture” approach was more effective when the unknown tensor was low-rank only in certain modes.The “Constraint” approach assumes low rank in every mode, whereas “Mixture” can detect the rank-deficient mode automatically.
  • Summary: The proposed “Constraint” approach outperformed conventional EM-based Tucker decomposition and was comparable to PARAFAC with the correct component count on amino acid fluorescence data.The proposed heuristic also reliably recovered true factors when the number of PARAFAC factors was misspecified.
  • Summary: Future work includes non-Gaussian noise, tensor classification, large-scale tensors beyond RAM capacity, and theoretical analysis of threshold behavior.These directions are presented as extensions of the proposed approaches.

Appendix A. Computation of the dual objectives.

Appendix A explains how the paper computes dual objective values for the relative duality gap.

  • Appendix A. Computation of the dual objectives.: The appendix describes computation of dual objective values used to calculate the relative duality gap in Equation (4.8).

A.1. Computation of dual objective for the “As a Matrix” approach.

For the “As a Matrix” approach, the appendix constructs a dual-feasible point from ADMM multipliers before evaluating the dual objective.

  • A.1. Computation of dual objective for the “As a Matrix” approach.: The dual problem associated with constrained minimization problem (4.9) is stated for the “As a Matrix” approach.
  • A.1. Computation of dual objective for the “As a Matrix” approach.: The anti-observation operator reshapes unobserved entries, while A is the matricization of α and ∥·∥ denotes spectral norm.
  • A.1. Computation of dual objective for the “As a Matrix” approach.: ADMM multipliers are projected onto the equality constraint by setting entries corresponding to unobserved positions to zero.
  • A.1. Computation of dual objective for the “As a Matrix” approach.: The projected multiplier is shrunk using its matricization’s maximum singular value, then substituted into the dual objective to compute the relative duality gap.

A.2. Computation of dual objective for the “Constraint” approach.

For the “Constraint” approach, the appendix enforces dual equality and spectral-norm constraints by projecting multiplier vectors and applying singular-value-based shrinkage before evaluating the dual objective.

  • A.2. Computation of dual objective for the “Constraint” approach.: The dual problem for constrained minimization problem (3.3) is stated for the “Constraint” approach.
  • A.2. Computation of dual objective for the “Constraint” approach.: Dual feasibility requires P^k⊤α^k = 0 and ∥A^k∥ ≤ γ_k for k = 1, . . . , K.
  • A.2. Computation of dual objective for the “Constraint” approach.: For each mode, A^k is the matricization of α^k, and the anti-observation operator is defined as in the preceding subsection.
  • A.2. Computation of dual objective for the “Constraint” approach.: The multiplier vectors are projected onto the equality constraint by averaging their sums over each unobserved entry and subtracting that average from every mode.
  • A.2. Computation of dual objective for the “Constraint” approach.: The largest singular value of each projected matricization is computed to define a common shrinkage factor enforcing the inequality constraints.
  • A.2. Computation of dual objective for the “Constraint” approach.: The resulting feasible multipliers are used in the dual objective to compute the relative duality gap.

A.3. Computation of dual objective for the “Mixture” approach.

The Mixture approach’s dual objective is evaluated by making its inequality constraints explicit and scaling the ADMM output to obtain a dual-feasible point for the relative duality gap.

  • Dual formulation: The dual formulation imposes spectral-norm constraints ∥P kΩ⊤α∥≤γk for k = 1, . . . , K.The norm is interpreted as the spectral norm of the matricization of P kΩ⊤α.
  • Dual feasibility: The ADMM iterate αt generally violates the dual inequality constraints, so it cannot directly be used for dual-objective evaluation.The section identifies feasibility as the missing step in evaluating the dual objective.
  • Dual feasibility: For each k, the method computes the largest singular value σk,1 = σ1(P kΩ⊤α) to determine the required shrinkage factor.These singular values provide the inputs for the shrinkage calculation in Equation (A.4).
  • Dual objective evaluation: Scaling α by the shrinkage factor produces the dual-feasible point ˜α = cα used to compute the relative duality gap (4.8).The scaled vector is the final feasible point used for evaluating the gap.
Loading 1010.0789v2…