Error Preserving Correction for CPD and Bounded-Norm CPD

Anh Huy Phan, Petr Tichavský, Andrzej CichockiarXiv 2017 · OpenReview

TL;DR

This paper introduces novel methods to address degeneracy issues in tensor decomposition (CPD), a common problem when dealing with complex datasets. They propose an "Error Preserving Correction" (EPC) to minimize the norms of rank-1 tensor components while maintaining approximation accuracy, and a "Bounded-Norm CPD" to constrain these norms. These techniques improve the stability and convergence of tensor decomposition algorithms, especially for challenging datasets like those representing matrix multiplication.

What Problem Does This Paper Address?

Canonical Polyadic (CP) decomposition is a powerful technique for breaking down multi-dimensional arrays (tensors) into a sum of simpler rank-1 tensors. However, this process can suffer from "degeneracy." This occurs in several scenarios: when the desired rank of the decomposition exceeds the tensor's dimensions, when the "loading components" (the vectors that form the rank-1 terms) are highly correlated (collinear), or when the standard CP decomposition gets stuck in suboptimal solutions (local minima). In these cases, some rank-1 terms can have very large norms that cancel each other out, leading to unstable algorithms that fail to converge or produce meaningful results even after many iterations. This paper aims to tackle these degeneracy issues by developing methods that not only preserve the approximation quality but also actively manage the norms of the rank-1 components.

Methods

The paper introduces two main algorithmic contributions:

  1. Error Preserving Correction (EPC): This method seeks a new tensor approximation that minimizes the norms of its rank-1 components while ensuring the approximation error remains within a specified bound. Two algorithms are proposed for this:
  2. Alternating Error Preserving Correction (ACEP): This algorithm iteratively updates one factor matrix at a time, reformulating the optimization problem into a series of linear regression sub-problems with bound constraints.
  3. Sequential Quadratic Programming (SQP) for EPC: This approach updates all parameters simultaneously, offering a potentially faster convergence but with higher computational complexity per iteration.
  4. Bounded-Norm CPD: This is a novel CP decomposition method that explicitly imposes a constraint on the norm of the rank-1 tensors. This is a dual problem to the EPC. Similar to EPC, both alternating and SQP-based algorithms are developed for this bounded-norm CPD.

The paper also discusses the relationship between these new algorithms and standard Alternating Least Squares (ALS) algorithms, showing how they generalize or relate to existing methods.

Datasets

The paper does not introduce new datasets. Instead, it uses artificially constructed tensors, including:

  • Tensors with highly collinear loading components.
  • Tensors representing matrix multiplication.
  • Tensors with rank exceeding tensor dimensions.
  • Real-world TV rating data.

These datasets are chosen to specifically highlight the degeneracy issues that the proposed methods aim to solve.

Key Insights and Ideas

  • Degeneracy is a major hurdle: The paper clearly articulates how collinearity and rank issues lead to unstable CP decomposition, where large norms of rank-1 terms cancel out, causing algorithms to get stuck.
  • Minimizing rank-1 norms is crucial: The core idea is that by actively minimizing the norms of individual rank-1 components (while preserving overall accuracy), we can prevent degeneracy and improve convergence.
  • EPC as a "correction" step: The EPC method acts as a post-processing or integrated correction step that refines an existing decomposition to address degeneracy.
  • Bounded-Norm CPD as a proactive approach: This method builds the constraint directly into the decomposition process, preventing large norms from arising in the first place.
  • Algorithmic flexibility: The development of both alternating (ACEP, BALS) and all-at-once (SQP-based) algorithms provides options for different computational trade-offs.

Key Results

The paper demonstrates the effectiveness of its proposed methods through several examples:

  • Improved Convergence: In cases where standard algorithms like fLM (fast Levenberg-Marquardt) get stuck in local minima or fail to converge, applying EPC significantly improves convergence speed and success rates. For instance, in Example 1, fLM without EPC failed to converge, while with EPC, it converged quickly.
  • Reduced Rank-1 Norms: The EPC method successfully reduced the norm of rank-1 tensors, which were excessively large in degenerate cases, from thousands to much smaller values (e.g., from ~3994 to 11.8 in Example 5).
  • Handling Difficult Tensors: The methods showed promise in decomposing challenging tensors, such as those representing matrix multiplication (Example 6) and tensors with rank exceeding dimensions and highly collinear components (Example 5).
  • Competitive Performance: In numerical experiments, the proposed algorithms (ACEP, SCEP, BALS, BSQP) often achieved better or comparable results to existing state-of-the-art methods, especially in scenarios prone to degeneracy. For example, in noisy tensor decomposition (Example 4), EPC-enhanced fLM achieved higher success ratios and required fewer iterations than the standard fLM.

Limitations and Future Work

  • Computational Cost: While the paper presents efficient algorithms, SQP-based methods, which update all parameters at once, can be computationally more expensive per iteration than alternating methods. The paper mentions developing "fast inverse of the Hessian matrix" to mitigate this.
  • Parameter Tuning: The effectiveness of the bounded-norm CPD might depend on the choice of the bound parameter ($\epsilon$). The paper suggests strategies for adjusting this bound during the estimation process.
  • Future Work: The paper implicitly suggests further exploration of these methods for various tensor decomposition applications and potentially combining them with other advanced optimization techniques. The authors also mention the development of a TENSORBOX package for their algorithms.

Summary updated

Abstract

In CANDECOMP/PARAFAC tensor decomposition, degeneracy often occurs in some difficult scenarios, e.g., when the rank exceeds the tensor dimension, or when the loading components are highly collinear in several or all modes, or when CPD does not have an optimal solution. In such the cases, norms of some rank-1 terms become significantly large and cancel each other. This makes algorithms getting stuck in local minima while running a huge number of iterations does not improve the decomposition. In this paper, we propose an error preservation correction method to deal with such problem. Our aim is to seek a new tensor whose norms of rank-1 tensor components are minimised in an optimization problem, while it preserves the approximation error. An alternating correction algorithm and an all-atone algorithm have been developed for the problem. In addition, we propose a novel CPD with a bound constraint on a norm of the rank-one tensors. The method can be useful for decomposing tensors that cannot be analyzed by traditional algorithms, such as tensors corresponding to the matrix multiplication.
BibTeX
@misc{phan2017error,
  author = {Anh Huy Phan and Petr Tichavský and Andrzej Cichocki},
  title = {{Error Preserving Correction for CPD and Bounded-Norm CPD}},
  year = {2017},
  eprint = {1709.08349},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1709.08349},
}
Figure