PaperlayerView exact revision on arXiv

Source-linked AI summary

Low Complexity Damped Gauss-Newton Algorithms for CANDECOMP/PARAFAC

Anh Huy Phan, Petr Tichavský, Andrzej Cichocki

arXiv:1205.2584v2math.NAcs.LGcs.NAmath.OC

TL;DR

CP dGN can handle difficult collinear or different-magnitude factors, but inverting its large approximate Hessian is computationally demanding. The paper derives a lower-complexity dGN implementation for real and complex tensors, and reports faster execution than dGN and ALS, with better difficult-case accuracy than ALS.

  • Problem

    dGN handles collinear or different-magnitude factors, but its large approximate-Hessian inverse makes it computationally demanding for large-scale factorization.

    Source: §1 · p. 1, §7 · p. 16

  • Method

    The proposed fast dGN uses the approximate Hessian's structure to work with smaller matrices and avoid storing the full Hessian or its inverse, with a complex-valued variant.

    Source: §4.3 · p. 7, §7 · p. 16

  • Results

    Simulations on real- and complex-valued tensors found fLM faster than dGN and ALS and more accurate than ALS on difficult test cases; its MedSAE was comparable to CRIB for most cases, including noisy tensors.

    Source: §7 · pp. 15–16

  • Takeaways & Limitations

    The fast implementation targets low-rank real- and complex-valued tensor factorization without constructing or storing the full approximate Hessian and its inverse.

    Source: §7 · p. 16

    The Jacobian remains in the gradient computation and may still demand high computational cost.

    Source: §4.2 · p. 5

Abstract

from arXiv · show

The damped Gauss-Newton (dGN) algorithm for CANDECOMP/PARAFAC (CP) decomposition can handle the challenges of collinearity of factors and different magnitudes of factors; nevertheless, for factorization of an $N$-D tensor of size $I_1\times I_N$ with rank $R$, the algorithm is computationally demanding due to construction of large approximate Hessian of size $(RT \times RT)$ and its inversion where $T = \sum_n I_n$. In this paper, we propose a fast implementation of the dGN algorithm which is based on novel expressions of the inverse approximate Hessian in block form. The new implementation has lower computational complexity, besides computation of the gradient (this part is common to both methods), requiring the inversion of a matrix of size $NR^2\times NR^2$, which is much smaller than the whole approximate Hessian, if $T \gg NR$. In addition, the implementation has lower memory requirements, because neither the Hessian nor its inverse never need to be stored in their entirety. A variant of the algorithm working with complex valued data is proposed as well. Complexity and performance of the proposed algorithm is compared with those of dGN and ALS with line search on examples of difficult benchmark tensors.

1. Introduction.

CP methods can struggle with factors of different magnitudes and collinearity, while dGN can handle these difficult cases but is costly for large-scale, high-dimensional data. The paper develops a faster approximate-Hessian inverse and dGN algorithms that avoid storing the full Hessian and its inverse.

1. Introduction.

  • dGN can decompose difficult data with different-magnitude or collinear factors, but its large approximate-Hessian inverse limits use on large-scale, high-dimensional data.ALS variants can improve performance but do not completely solve these difficulties.Source: §1 · p. 1
  • The paper derives a fast inverse by showing that the approximate Hessian is a low-rank adjustment to a block diagonal matrix.Source: §1 · p. 1
  • The paper is organized from notation and CP algorithms through fast dGN derivation and complex-valued extension, followed by examples and a conclusion.Source: §1 · p. 1

2. Tensor notation and CANDECOMP/PARAFAC (CP) model.

This section establishes notation for tensors, matrices, vectors, and products, then introduces the CP model as a representation of a data tensor using factor matrices.

2. Tensor notation and CANDECOMP/PARAFAC (CP) model.

  • Bold calligraphic letters denote tensors, bold capitals denote matrices, and bold italic letters denote vectors.Source: §2 · p. 1
  • The notation identifies mode-n unfolding and uses ⊗, ⊙, and ⊛ for Kronecker, Khatri-Rao, and Hadamard products, respectively.Source: §2 · p. 2
  • The CP model represents an Nth-order data tensor with a set of N factor matrices.Source: §2 · p. 2
  • The model describes the data tensor as an approximation and often assumes unit-length components in modes 1 through N−1.Source: §2 · p. 2

3. CP Algorithms.

This section reviews ALS and all-at-once Gauss-Newton methods for CP factorization, including dGN's damping and the computational burden of inverting its approximate Hessian. It also describes a prior reduced-matrix inverse approach and its storage and tensor-order constraints.

3. CP Algorithms.

  • ALS sequentially updates the factor matrices, whereas dGN is an all-at-once method that simultaneously updates the concatenated factor vector.Source: §3 · p. 2
  • Damping in dGN is associated with advantages over ALS for swamps and factors of different magnitudes.Source: §3 · p. 2
  • The inverse of the approximate Hessian H has O(R^3T^3) complexity beyond gradient computation, keeping existing dGN methods costly for large-scale problems.Prior approaches used Cholesky decomposition with back substitution or QR decomposition to address the inverse.Source: §3 · p. 3
  • A prior inverse method uses 3R^2 × 3R^2 matrices and improves running time when rank is much smaller than mode dimensions, but requires temporary storage and is restricted to third-order tensors.Source: §3 · p. 3

4. Fast damped Gauss-Newton algorithm.

The section derives fast damped Gauss–Newton updates by exploiting low-rank and block structure in the approximate Hessian. It also presents two variants, compares their complexity with dGN, and describes the damping strategy.

4. Fast damped Gauss-Newton algorithm.

  • The fast algorithm targets the cost of constructing and inverting H, the main computational challenge identified for the dGN update.Its derivation uses a low-rank adjustment and the binomial inverse theorem to invert a smaller matrix.Source: §4 · pp. 3–4

4.1. Fast inverse of the approximate Hessian H.

  • For NR ≪ T, a low-rank adjustment of H enables its damped inverse to be computed through a smaller NR^2 × NR^2 matrix.The block form also avoids storing the full H or H inverse; the cited passages describe storage in terms of mode-wise matrices and eSμ.Source: §4.1 · pp. 4–5

4.2. Proof of Theorem 4.1.

  • The fast update replaces Hμ^-1 in the dGN rule with the derived inverse expressions, while the Jacobian remains in the gradient and may still be costly.The update is implemented in Algorithm 1; the text notes that the gradient still involves the Jacobian.Source: §4.2 · pp. 5–6

4.3. Two variants of the fast dGN algorithm.

  • The two fast dGN variants solve different NR^2 × NR^2 systems, Φ1 and Φ2; Φ1 is less sparse and nonsymmetric, while Φ2 is symmetric.The text also notes that K is singular when factor matrices have mutually orthogonal columns.Source: §4.3 · pp. 6–7

4.4. Comparison of complexity between dGN and fast dGN.

  • The fLM algorithm builds and inverts a smaller NR^2 × NR^2 matrix Φ instead of the full approximate Hessian, with lower complexity than dGN for NR < T.The comparison excludes gradient computation and damped ALS factors, which are common costs; for N > 7, fLM has the same complexity order as ALS but is reported to be faster because it needs fewer iterations.Source: §4.4 · p. 8

4.5. Damping parameter in the LM algorithm.

  • The damping parameter μ controls the direction and step size of the update and is adjusted using Nielsen’s strategy.Factors are updated only when the new approximation has lower error; the algorithm stops when μ becomes sufficiently large.Source: §4.5 · p. 8

5. Complex-valued tensor factorization.

The paper extends damped Gauss–Newton and its fast variant to complex-valued tensor factorization. It derives complex-case approximate-Hessian expressions and gives a fast factor update for NR ≪ T.

5. Complex-valued tensor factorization.

  • The complex-valued extension uses factors A(n) ∈ C^(I_n×R) and rewrites the damped Gauss–Newton update for complex data.The paper treats real and complex algorithms separately for simplicity, although real-valued tensors can be viewed as complex-valued tensors with zero imaginary part.Source: §5 · pp. 8–9
  • The complex approximate Hessian is J^H J and is organized into mode-wise blocks, with subsubmatrices that are diagonal or rank one.The paper derives explicit expressions for these Hessian blocks, adapting the real-valued derivation.Source: §5 · p. 9
  • For NR ≪ T, the complex fast dGN update uses a fast factor-update rule based on the low-rank adjustment of the approximate Hessian.The low-rank adjustment is stated for H = J^H J; the update uses frontal slices of a tensor F.Source: §5 · pp. 9–10

6. Experiments - Computer simulations.

The simulations compare fLM with dGN and ALSls on real-valued tensors, then test fLM against ALSls on complex-valued tensors. They report runtime, memory, and factor-reconstruction results across ranks and collinearity settings.

6. Experiments - Computer simulations.

  • The experiments evaluated CP factorizations with controlled factor collinearity, measuring median squared angular error (MedSAE) between original and estimated components and comparing average MedSAE with average CRIB.For 4-D complex-valued tensors with size In = 70 and ranks R = 5, 15, algorithms stopped at a derivative of successive relative errors of 10^-8 or 2,000 iterations.Source: §6 · pp. 10–11, Figure 6.4 · p. 15

6.1. Comparison between dGN and fLM for 3-D tensor factorizations.

  • For 3-D tensors, fLM’s total-time speedups over dGN ranged from 2.8× to 35.1× across R=5–60; both reconstructed components r≥2 well even at R=60.For the first components, reconstruction failed for both methods at R≥40 because of noise; at R=20 and 30, fLM reconstructed them.Source: §6.1 · pp. 11–12, Figure 6.1 · p. 12
  • For 3-D tensors with R≥50, fLM used less than 4 GB of memory, while dGN required more than 4 GB and could use 20 GB at R=100.On the 64-GB computer, fLM was slightly slower per iteration than dGN for R≥90; on the 4-GB computer, dGN became dramatically slower for R≥40.Source: §6.1 · p. 12, Figure 6.2 · p. 13

6.2. Factorization of higher-order real-valued tensors.

  • For 4-D tensors at SNR = 40 dB, fLM was 21 times faster than ALSls at R = 10, ν = 0.1 and 24.7 times faster at R = 15, ν = 0.1; their MedSAEs were almost similar and approached CRIB except at R = 15, ν = 0.1.At lower collinearity, fLM was still approximately 3 times faster than ALSls.Source: §6.2 · p. 13, Figure 6.3 · p. 14

6.3. Factorization of complex-valued tensors.

  • For complex-valued tensors, fLM outperformed ALSls across all tested cases, and differences in component magnitude did not affect fLM.ALSls did not achieve perfect reconstruction at ν=4 and 5; it also stopped after tens of iterations at ν=3, 4, and 5.Source: §6.3 · p. 14, Figure 6.4 · p. 15

7. Conclusions.

The proposed fast damped Gauss–Newton method uses the approximate Hessian’s structure to reduce inversion and storage costs, and extends to complex-valued tensors. Simulations report faster execution than dGN and ALS, with approximation accuracy outperforming ALS and comparable to CRIB for most test cases, including noisy tensors.

7. Conclusions.

  • fLM was faster than dGN and ALS, outperformed ALS in approximation accuracy, and had MedSAE comparable to CRIB for most test cases, including noisy tensors.The conclusion also reports that higher rank made factor retrieval more difficult, while higher tensor dimension improved performance at fixed size, rank, and collinearity degree.Source: §7 · pp. 15–16
  • The proposed dGN/LM algorithms avoid forming the full approximate Hessian and its inverse by using matrices of size NR^2 × NR^2 instead of RT × RT.The paper reports that the fast computation uses no significant temporary extra storage and reduces the cost of building and applying L_μ by a factor R.Source: §7 · p. 16, Appendix A · p. 18
  • The fast dGN/LM algorithms are proposed for low-rank real- and complex-valued tensors, with possible extensions to nonnegative CPD, supersymmetric tensor factorization, and INDSCAL.The proposed methods were evaluated on difficult benchmarks for both real- and complex-valued tensors.Source: §7 · p. 16
  • Eigenvalue analysis of tensor unfoldings can predict whether noisy factorization will retrieve collinear factors and indicate possible instability or non-unique solutions.For the illustrated 3-D case, the smallest noisy eigenvalue approaches the noise level at SNR = 20 dB for ν ≤ 0.3, or at SNR = 30 dB for ν ≤ 0.1.Source: Appendix F · p. 18
Loading 1205.2584v2…