WorksComputer Science
Newton's Method for CP Decomposition
Abstract
We present an algorithm for computing the CP tensor decomposition using Newton's method. The problem of fitting a CP model to a data tensor with least squares loss can be solved by various gradient-based optimization techniques, including Gauss-Newton methods that exploit the tensor structure of the problem and iteratively solve the linear system involving the approximate Hessian matrix to determine the step direction at each iteration. Gauss-Newton methods exhibit superlinear convergence when the residual is small but can otherwise struggle to converge when the approximation to the Hessian is not accurate. We show that the Gauss-Newton approach can be extended to Newton's method, using the true Hessian to obtain fast convergence even in the case of large residuals. In particular, we derive efficient means of applying the true Hessian to vectors for use within an iterative solver, we employ globalization and regularization techniques to make the Newton model robust to ill-conditioned and/or indefinite Hessians, and we propose hybrid use of Gauss-Newton and Newton steps to balance convergence behavior both far and near local minima. Our numerical experiments use synthetic examples to show in which scenarios Gauss-Newton and other methods struggle to converge, and we demonstrate the superiority of the hybrid approach on two application data sets.
Introduction
The CP decomposition, known variously as canonical polyadic, CANDECOMP, PARAFAC, rank decomposition, or separated representation, is one of the most widely used low-rank representations of multidimensional data. Given an input data tensor, a CP decomposition is an approximation of the data by a sum of rank-one tensors, where a rank-one tensor is an outer product of vectors. We refer to the number of summands or components in the CP representation as the rank of the model. The (vector) factors of the rank-one tensors are collected into a set of factor matrices, one for each mode of the tensor. CP is particularly useful for interpretation, as it is typically unique (up to ambiguities discussed below) and each rank-one component represents an underlying pattern that describes a multi-way relationship among the different modes of the multidimensional data.
However, the problem of computing a CP approximation using a least-squares loss function has many well-studied challenges. Determining the right approximation rank is a difficult problem, so in practice many different values of rank must be attempted. Even for a fixed rank , the corresponding optimization problem is nonlinear and nonconvex. There may not exist a best rank-
Email addresses: [email protected] (DuBose Tuller), [email protected] (Grey Ballard), [email protected] (Hussam Al Daas), [email protected] (Nicholas I. M. Gould) CP approximation, and even if the best approximation exists, the problem may be ill-conditioned. Furthermore, the scaling and permutation ambiguities in the CP representation can disrupt the convergence of optimization methods.
Many algorithms for solving the CP approximation problem have been developed and optimized, and no single method is clearly superior to all others (see [26], for example). The simplest method is called Alternating Least Squares (ALS) [6, 13], which is a block coordinate descent method that alternates over updating each factor matrix while holding all other factor matrices fixed. ALS is relatively cheap per outer iteration and can converge quickly for some problems but suffers from slow convergence in many other cases. Gradient-based optimization methods update all factor matrices at once, and the evaluation of the gradient has roughly the same cost as an ALS iteration. Quasi-Newton methods such as LBFGS can yield faster convergence than ALS at minimal added expense beyond evaluating the gradient (see [1], for example).
Variants of the Gauss-Newton method, which involve an approximation of the Hessian using first-order derivatives, can work very well for CP with least-squares loss. The CP model with the residual function yields a Jacobian that is highly structured, so the solve for the step direction at each Gauss-Newton outer iteration can be performed by an iterative method (typically, a Krylov method) with cheap inner-iteration cost relative to the gradient evaluation (see [31], for example). In particular, neither the Jacobian nor the Gauss-Newton Hessian approximation is represented explicitly, and instead matrix-vector products are evaluated implicitly. The Gauss-Newton approximation of the Hessian is particularly accurate when the residual is small, and for problems where the CP model is a very good approximation to the data, Gauss-Newton methods can exhibit superlinear convergence.
However, in cases of large residuals, the Gauss-Newton approximation of the Hessian is not accurate, and the convergence of Gauss-Newton methods can slow down or stall. Input tensor data coming from most applications is typically noisy, and the CP approximation problem seeks to separate the low-rank signal from the noise, so the magnitude of the residual depends on the signal-to-noise ratio. The central contribution of this work is the demonstration that the true Hessian matrix can be implicitly and efficiently applied in an implementation of Newton’s method that overcomes this barrier and yields superlinear convergence even in cases of large residuals (e.g., noisy data). We show that the true Hessian has tensor structure that can be exploited similarly to its Gauss-Newton approximation. With efficient evaluation of Hessian matrix-vector products using precomputed temporary values, the cost of an inner iteration of computing a Newton step direction is comparable to that of applying the Gauss-Newton approximation to a vector and cheap relative to the gradient evaluation. The computational cost of precomputation, which is performed once per Newton iteration, is only 50% more than the cost of computing the gradient. This implies that the overall per-iteration cost of Newton’s method for CP is comparable to other gradient-based algorithms, including Gauss-Newton and ALS.
Newton’s method presents its own set of challenges, and previous considerations of using Newton’s method for CP often cite its cost and/or lack of robustness [27, 22] (see also [15, 12] for the related problem of CP rounding). While fast convergence is achievable in the neighborhood of a local minimum, the true Hessian may be indefinite and generally can lead to erratic behavior when far from a solution. We use two techniques to mitigate the loss of robustness of Newton’s algorithm compared to Gauss-Newton. First, we employ unique globalization and regularization techniques that overcome negative curvature present in the Newton, but not the Gauss-Newton model, and coping with this more severely regularized subproblem is more than simply solving a (perturbed) linear system. In this case, an inner iteration using a nonlinear solver like GLRT [7], [8 Chaps. 9 & 10] is required. Second, we take a hybrid approach, relying on Gauss-Newton in early iterations and switching to Newton when the gradient is sufficiently small. This hybrid approach achieves all the advantages of Gauss-Newton methods with added robustness to achieve fast convergence even in the case of large residuals.
Our numerical experiments in § 4 illustrate the behavior predicted by the theory. We use synthetic examples to vary the difficulty of problems in terms of ill-conditioning (using collinearity of factors), noise, and mis-estimations of rank. The experiments show that ill-conditioning can lead to very slow convergence of ALS and that both Gauss-Newton and Newton exhibit superlinear convergence for problems with small residuals. We show that Gauss-Newton’s convergence deteriorates in the presence of large residuals due to high noise or underestimation of the rank, while Newton’s superlinear convergence is robust to the size of the residual. However, our experiments also show that Newton’s method is often slower to locate the neighborhood of a solution, resulting in more iterations overall for easier problems. Our hybrid approach achieves the fewest iterations, following the trajectory of Gauss-Newton when it succeeds and gaining the benefits of Newton when Gauss-Newton struggles. We consider two application data sets that involve noisy data that confirm the observations from the synthetic data experiments.
Background
Tensor Notation
We use calligraphic notation for tensors (e.g., ), capital boldface for matrices (e.g., ), lower-case boldface for vectors (e.g., ), and regular font for scalars (e.g., ). We focus on 3-way tensors in this work, but the methods generalize to the -way case. In general, we assume the input data tensor , and we index into those dimensions using , , and , respectively.
In computing a CP approximation of , we consider the CP model as a Kruskal tensor of rank represented by three factor matrices , , and , and we use to index over the rank . In shorthand, we write , where
where denotes the vector outer product and is the th column of , is the th column of , and is the th column of . Kruskal tensors have inherent ambiguities: the columns of the factor matrices can be permuted and the factors of each vector outer product can be re-scaled [3 Sec. 10.4]. That is, considering consistent columns , and of the factor matrices , and , the term in the Kruskal tensor is identical to , whenever , and for any three scalars satisfying .
Derivative Notation
Let . Then the gradient of is the vector of partial derivatives with respect to each of the elements of , with . The Hessian is the matrix of second derivatives with respect to pairs of the elements of , with .
Let . Then the derivative of is the Jacobian matrix containing the partial derivatives with respect to each variable and each element of the output of , with . Note that we follow the convention of considering gradients as column vectors, which implies that the gradient of an element of is the transpose of the corresponding row of the Jacobian.
Definition 1 (Derivatives of Nonlinear Sum of Squares). Let and be such that . Then the gradient of is given by
and the Hessian of is given by
We denote the second term of this matrix .
Special Matrix and Vector Operations
In developing optimization methods for functions and variables that have matrix and tensor shapes, we rely on vectorizing the principal quantities to obtain standard forms. There are two common ways to linearize matrices and tensors into a vector form.
Definition 2 (Linearization Functions). Let and , then is the natural linearization function such that
and is the reverse linearization function such that
The vec operator takes a matrix or a tensor and linearizes it into a vector according to natural ordering.
Definition 3 (vec Operator). If , then where
If , then where
We can reshape a tensor into a matrix using modal unfoldings. We use the notation to denote the mode-1 unfolding, which stacks the mode-1 fibers as columns into a matrix with columns in natural order. That is, for . Likewise, for and for . In particular, this implies .
The Kronecker, Khatri-Rao, and Hadamard products are central to the analysis of methods for computing CP decompositions.
Definition 4 (Kronecker Product). If and , then where
If and are column vectors of length and , then is a column vector of length .
Definition 5 (Khatri-Rao Product). If and , then such that
The Khatri-Rao Product is equivalently the Kronecker products of each of the corresponding columns in and .
Definition 6 (Hadamard Product). If and , then with
Definition 7 (Tensor-Times-Matrix Product [3 Def. 3.14]). The mode- tensor-times-matrix () product between a tensor and a matrix is written and is defined by
The following properties are crucial to deriving representations of these types of products of matrices that can be evaluated efficiently.
Property 1 ([14 Eq. (4)]). For , , and , we have
Corollary 1.
Note that the size of the identity matrices may not be the same on the left and right sides of the equation, depending on the size of and .
Property 2 ([3 Prop. A.18]). For , , , and , we have
Property 3 ([3 Prop. A.23]). For , , , and , we have
Definition 8. Let be a 3-way tensor. Define the block diagonal operator to take the horizontal slices of and arrange them as the diagonal entries of a block matrix such that:
where is an indicator matrix. We can similarly define block diagonalization using lateral and frontal slices. The subscript indicates which mode of the tensor remains fixed for each diagonal block sub-matrix.
CP Problem
In the standard CP approximation problem, we seek factor matrices of a CP model that can be used to approximate the input tensor as accurately as possible in a least squares sense.
Definition 9. Letting be a 3-way tensor, the CP optimization problem is defined as
or equivalently, to match the notation of Def. 1,
Thus, this CP approximation problem is a nonlinear least squares problem with the following Jacobian and gradient.
Lemma 1. [1, 3] For as given by Def. 9, the Jacobian of is
where and are tensor perfect shuffle permutations, and the gradient of is
The Alternating Least Squares (ALS) algorithm for CP [6, 13] alternates updates to each factor matrix with all others fixed. In terms of the gradient, it alternates solving for , for , and for , which are all linear systems (with multiple right hand sides). By contrast, gradient-based optimization methods, including the Gauss-Newton method below, use the gradient to try to optimize all factor matrices at once at each iteration.
Complexity Analysis. The cost of computing CP gradient is dominated by the computations involving the data tensor. The expressions , , and are called Matricized-Tensor Times Khatri-Rao Products (MTTKRPs). The computational cost of evaluating the MTTKRPs in all modes is plus lower order terms. The cost of evaluating the other expressions of the gradient are , which is also dominated by that of the MTTKRPs. Note that the cost of an ALS iteration (updating all factor matrices once) is the same, up to the lower order terms. For more details, see [3 Sec. 3.6.2].
Gauss-Newton Method for CP
The Gauss-Newton method aims to find an improving correction step from by minimizing the first-order approximation to . The solution to this problem satisfies the Gauss-Newton linear system
but when is large, it is usual to approximate the solution using an iterative (normally, Krylov) method that requires repeated matrix-vector products for a sequence of vectors . For example, Vervliet and De Lathauwer [31] use preconditioned conjugate gradients with a block-diagonal preconditioner. Tensorlab [32] implements three Gauss-Newton variants. The first, nls_gndl, uses a dogleg trust region strategy, in which the minimizer of along a piecewise linear path connecting the initial point to the Gauss-Newton point via the intermediary Cauchy point , where , is sought within the trust-region for a given radius . The second, nls_gncgs, applies the conjugate-gradient method to generate approximations to the minimizer of , but stops whenever one of these approximations reaches the trust-region boundary. The last, nls_lm, is a Levenberg-Morrison-Marquardt regularization method of which we shall say more in § 3.1.
For the CP approximation problem, as outlined in Lem. 1, we partition into three column blocks corresponding to the factor matrices. Then has block matrix structure with blocks corresponding to pairs of factor matrices. Likewise, we partition the vector to match the factor matrices:
We take advantage of the structure of to achieve efficient computation of . As shown in [3, 31], the computations can be performed as follows:
Note that this formula does not depend on the data tensor and instead requires only matrix multiplications among matrices the sizes of the factor matrices. Also, matrices , , and are independent of . They are used in evaluating the gradient (see Lem. 1) and appear multiple times in eq. (2), so they are precomputed once per Gauss-Newton iteration and not recomputed every time is applied to a vector.
Complexity Analysis. The cost of applying to a vector is small compared to computing the gradient. Evaluating eq. (2) costs , while the gradient computation is as described in § 2.4. Applying the block-diagonal preconditioner has comparable cost to evaluating eq. (2) as well. Thus, as long as the number of inner iterations in the solve for is not excessive, the cost of a Gauss-Newton iteration is roughly that of evaluating the gradient. Note that the precomputation of , , and saves only a constant factor per inner iteration. See chapter 13 of [3] for the complete derivation and complexity analysis.
Newton's Method
We now present our proposed method for computing a CP decomposition via Newton’s method. We will follow the approach of efficient Gauss-Newton algorithms for CP [31], using an iterative method to compute the search direction with an efficient means of applying the (now true) Hessian to a vector that exploits the tensor structure. While the linear solve for the Gauss-Newton step direction involves a symmetric positive semi-definite matrix, for which iterative approximations using CGLS or LSQR [23] are appropriate, the true Hessian may be indefinite, so it might appear that we need to use a more sophisticated (and expensive) iterative linear solver such as SYMMLQ [24] in this case. Fortunately this is not so. To enhance the robustness of Newton’s method, we will employ different globalization and regularization techniques from those used for Gauss-Newton.
Globalization and Regularization
The CP problem introduced in § 2.4 is a specific example of the ubiquitous nonlinear least-squares problem
in the special case where the unknowns are organized as
and the residuals are given by . In this section, we focus on this general problem involving , and in particular on methods that are guaranteed (at worst) to find a stationary point of starting from an arbitrary initial guess; in most cases this will also be a local minimizer. As we have already seen, local optimization algorithms, such as the Gauss-Newton and Newton methods, traditionally make use of the gradient
and often the Hessian
of , or a suitable approximation of the latter; here is the Jacobian of , that is the matrix whose -th row is the transpose of the gradient, , of the -th component, , of , and is the Hessian of . However although these methods may attain fast local rates of convergence, they are not guaranteed to converge from afar. Our focus thus necessarily shifts to methods that do.
Two important classes of optimization algorithm for generic continuous optimization are line-search [10, 21] and regularization/trust-region [8, 9, 21] methods. The former move from a candidate solution to a better one by stepping along an -improving line (or arc) based on and sometimes . The others model around by building a suitable approximation of using and sometimes , pick a step from to reduce , and then assess whether is suitably smaller than .
We shall focus here on regularization methods since they have a good reputation for nonlinear least-squares problems, although most of what we say applies equally to trust-region methods. The simplest is the Levenberg-Morrison-Marquardt (LMM) [16, 18, 20] method. Here is replaced by the model
for which is the first-order Taylor approximation of , and is an evolving regularization weight that implicitly controls the length of the step . The step is then chosen to be any for which , where the Cauchy point gives the smallest value of in the steepest descent direction, . In particular, might be chosen as the minimizer of , for which
Notice that these equations involve a non-zero diagonal perturbation to the Gauss–Newton ones (1), and it is this that is crucial to guarantee global convergence. The rest of the algorithm is straightforward. Given , the ratio
of the actual to (model) predicted decrease is computed, and so long as this is adequate (say ), the correction becomes the new and may be decreased. By contrast, if the decrease is inadequate, stays at , but now is increased; the impact of this is to ensure that the next step will be smaller than the current one, and thus resembles better, and ultimately progress will be made. Although it is possible to use matrix factorization to find the minimizer of , this is likely costly in our case, and instead we use a Krylov method (GLRT) [8 Chap. 9 & 10], that simply involves products, to do so.
When the optimal residuals are small, LMM is an excellent method, and fast linear or even superlinear convergence is observed. However, for problems with larger optimal residuals, the convergence is frequently observably poorer, and we need to move to something more Newton like. To do this, we instead consider the regularized Newton (second-order Taylor) model
that includes the term that is missing in LMM; the regularization power has to rise above two to compensate for this extra Hessian term to ensure that the model is bounded from below. All of the remaining ingredients are as before. We need to find an approximate minimizer of that is at least as good as that at the Cauchy point , we accept and reject steps and adjust based on the equivalent of (3) involving , and we can find using either factorization or, in our case, GLRT involving Hessian-vector products.
One important aspect that is peculiar to our tensor fitting problem is that of objective-function ambiguity described in § 2.1. The scaling ambiguity is unfortunate, since it implies that there are an infinite number of global minimizers, and consequently statements about rates of convergence then need to be phrased in terms of a solution set, not isolated single points. Since this is awkward both in theory and practice, we aim to avoid the issue by insisting that all of the iterates we generate are normalized so that . That is, given , we equilibrate them via
as this gives the required renormalization. This is the same equilibration used by Utschmajew for the ALS algorithm [28] and is implemented in Tensor Toolbox’s normalize function [2]. Crucially, this does not impact the global convergence of the method, as this equilibration is akin to taking an evaluation-free magical step [9 §10.4.1], but what the precise implication for the rate of convergence is an open question—our experiments suggest that a fast rate, when expected, is retained.
The other, less serious ambiguity is that we may arbitrarily (but consistently) permute the columns of , and without changing the generated Kruskal tensor. We ignore this possibility in practice as it leads to distinct, as opposed to continuous, solution sets.
Deriving the Hessian for CP
Next, we derive the true Hessian for a 3-way CP decomposition such that , , and . We use the indices , , , and for , , , and , respectively.
The nonlinear least squares optimization for CP is given in Def. 9, and as shown in Def. 1, the Hessian can be expressed as
As the structure of and efficient means of applying it to a vector are described in § 2.5, we focus now on . Here is the residual tensor and is the Hessian of the scalar-valued function , an element of .
Similar to the structure of , we consider (dropping the dependence on for ease of notation) to be a symmetric block matrix based on the mixed partials with respect to each pair of factor matrices:
Note that , which is a linear function in each of the factor matrices. This implies that any mixed partial derivative involving two elements of the same factor matrix is , or equivalently, , , and . We now derive expressions for the three off-diagonal blocks. A visualization of the sparsity structure of is given in Figure 1.
Figure 1. Diagram of K’s structure in the case that the input is an tensor and .
Lemma 2. The off-diagonal blocks of the matrix as defined in eq. (6) are given by
with given by Def. 8 and .
Proof. By definition, . We will first find the mixed partial of a single residual element, then we will sum over all residual elements.
First, we obtain the gradient of a single residual element with respect to . Let be the 3-way indicator tensor, which is when unfolded on the first mode. The Jacobian of is given in Lem. 1, and in particular, . Thus, we can find the gradient of (with respect to ) by selecting and transposing the corresponding row of the Jacobian of (with respect to ):
Next, we differentiate with respect to . Since does not depend on , we differentiate with respect to and multiply back. By definition, the -th column of is , so
Thus,
and therefore
We simplify the product using Prop. 2:
To evaluate the right factor, recall and apply Prop. 2:
Substituting back and applying Prop. 2 once more:
Multiplying by , summing over , and exchanging the order of summation, we have
The derivations of and are analogous.
Efficiently Applying the Hessian to a Vector
To apply the Hessian to a vector , we separately compute (as described in Sec. 2.5) and . As before, we will break the vector into three components which correspond to the three factor matrices, and we drop the dependence on to ease notation. We have
The following lemma illustrates that the structure of these computations is similar to the gradient, but with mixed contributions from the CP model vector and the arbitrary vector .
Proof. We detail the derivation only for , as the other cases are derived similarly. Note that by the definition of the mode-3 product (see Def. 7), the th frontal slice of is . Then
As ,
follows from Prop. 3.
Note the similarities of these expressions to the CP gradient given by Lem. 1. In particular, unlike the computation of in eq. (2), involves the data tensor in the form of MTTKRPs. Evaluating these MTTKRPs directly would make every iteration of an iterative solve for as expensive as evaluating the gradient (roughly equivalent to one Gauss–Newton iteration, for example).
However, we can avoid this overhead using precomputation of contractions between the data tensor and the Newton iterate. Every MTTKRP in Lem. 3 involves one factor matrix from (the fixed Newton iterate) and one factor matrix from (the arbitrary vector that varies over iterations). For example, involves the MTTKRP . As described in [3 Sec. 3.5.1], we can compute the MTTKRP using the following two steps: (1) and (2) , which is computed as batched matrix-vector products. In fact, the six terms can all be computed from three precomputations involving and : , , and . Because of the overlap, we can also use these intermediate quantities (as well as , , and ) to evaluate the gradient.
Complexity Analysis. The cost of applying to a vector is split into costs per Newton iteration and cost per GLRT iteration. The precomputations in Alg. 1, which are performed every Newton iteration, include the three TTMs with the data tensor and computing the Gram matrix for each factor matrix, and they have computational cost plus lower order terms. Note that the gradient can be computed very cheaply given these precomputations (see Alg. 2), so this cost is in place of rather than in addition to that of the gradient. That is, the precomputations of a Newton iteration cost roughly 50% more than computing only the gradient.
The cost per GLRT iteration includes the cost of applying and completing the application of . The cost of applying is (see § 2.5). The six batched matrix-vector products to complete the application of have cost , and the other operations cost . Therefore, assuming is small relative to the tensor dimensions, the cost of a GLRT iteration is more expensive when applying the true Hessian as opposed to the Gauss-Newton approximation, but in either case we expect to be dominated by the evaluation of the gradient (i.e., precomputations in the case of Newton’s method) at each outer iteration.
Algorithm Outline
The pseudocode for the proposed algorithm is given by Alg. 4, and the key computational subroutines are given in Algs. 1 to 3. As described in § 3.1, the overall approach involves outer and inner iterations: the outer iteration corresponds to a Newton step and an approximate CP model represented by , and the inner iteration corresponds to a step of the Krylov method GLRT used to compute the update . We use a stopping criterion for the Newton iteration based on a gradient norm tolerance (see line 24), and we use the Eisenstat-Walker method to adaptively change the forcing tolerance for GLRT at each Newton iteration [11], though that is not specified in Alg. 4. Note that we equilibrate the CP model at every Newton iteration as described in eq. (5) (see line 17).
The dominant computation of using Newton’s method to compute CP can be divided into two major components: evaluation of the gradient and computing the search direction . The latter involves multiple iterations of the GLRT algorithm, whose cost is dominated by applying the term of the Hessian to a vector as described in § 3.3. Both of these major operations can be cast as multi-step tensor contractions. For each Newton iteration, we perform the precomputations that contribute to both evaluations as shown in Alg. 1, and then complete the above operations using the result.
Algorithm 1 Precomputations for Gradient and K
function
Unpack into
return
end function
For the gradient computation, each MTTKRP is completed by one batched matrix-vector product involving a TTM intermediate from that has all modes except two contracted (see Alg. 2). To apply , for each nonzero block we apply one input-vector factor matrix to an intermediate from as shown in § 3.3. The pseudocode is given in Alg. 3. Therefore, by precomputing the intermediates once per Newton step, we avoid redundant computation across the gradient and all applications.
Algorithm 2 Completion of Gradient Evaluation
function = COMP-GRADIENT(, , )
Unpack into
▷
▷
▷
Pack into
return
end function
Algorithm 3 Completion of Application of K Term of Hessian to a Vector
function = COMP-APPLY-K(, , , )
Unpack into , unpack into
Pack into
return
end function
After the search direction has been computed, we then determine whether to accept or reject the step using regularization semantics described in § 3.1. We compute the predicted change in the objective using the unregularized Hessian, then compute the ratio between the true and model decrease found from taking step . If the ratio is sufficiently high, then we accept the step, equilibrate the new point, and decrease . If the ratio is small or negative, then the step is rejected, and is increased. There are also intermediate values of where the step is accepted, but does not decrease.
Algorithm 4 CP Newton with GLRT
1: function v = CP-Newton-GLRT(X, [A₀, B₀, C₀], ε)
2: Pack A₀, B₀, C₀ into v₀
3: Equilibrate v₀ as given by eq. (5)
4: {Y}, {S} ← precompute(X, v₀) ▷ TTM and Gram intermediates, shared by g and K
5: g₀ ← comp-gradient(v₀, {Y}, {S})
6: f₀ ← objective(X, v₀, {Y}, {S})
7: for k = 1, 2, . . . do
8: while GLRT with cubic weight λ not converged do ▷ Compute trial step sₖ
9: Apply (JᵀJ + K) v̄ using {Y} and {S} ▷ for some v̄ determined by GLRT
10: Update sₖ
11: end while
12: Δₘ ← −[½sₖᵀ(JᵀJ + K)sₖ + gₖ₋₁ᵀsₖ] ▷ predicted decrease
13: fₖ ← objective(X, vₖ₋₁ + sₖ)
14: ρ ← (fₖ₋₁ − fₖ) / Δₘ
15: if ρ > ρaccept then ▷ accept the trial step
16: vₖ ← vₖ₋₁ + sₖ
17: Equilibrate vₖ as given by eq. (5)
18: {Y}, {S} ← precompute(X, vₖ)
19: gₖ ← comp-gradient(vₖ, {Y}, {S})
20: else
21: vₖ ← vₖ₋₁; fₖ ← fₖ₋₁; gₖ ← gₖ₋₁ ▷ reject update
22: end if
23: Adjust λ according to ρ ▷ increase when ρ is small, decrease when large
24: if ∥gₖ∥ < ε then
25: return vₖ
26: end if
27: end for
28: end function
Complexity Analysis. Table 1 outlines the cost of each of the above operations in outer and inner iterations, assuming is an tensor and the CP model has rank . For each outer iteration, we highlight the calls to the precompute function (line 18), which includes computing both TTMs and Gram matrices, and the comp-gradient function (line 19), which completes the gradient evaluation. The inner iterations are dominated by the application of the (regularized) Hessian in line 9, which includes both the application of and . We also show the comparison with the complexity of Gauss-Newton methods that rely on a iterative method to compute the step. direction.
| Calculation | Newton Complexity | Gauss-Newton Complexity |
| Per Outer Iteration: | ||
| Precomputed TTMs | ||
| Gradient Completions | ||
| Gram Matrices | ||
| Per Rejected Step | ||
| Per Inner Iteration: | ||
| Apply | ||
| Apply Completions |
Table 1. Comparison of per-iteration complexity of Alg. 4 with Gauss-Newton methods
Note that the cost of a rejected step is a fraction (roughly 1/3rd) of the cost of an accepted step. While not reflected in the pseudocode of Alg. 4 for simplicity, we precompute one of the TTM results (e.g., ), complete an MTTKRP, and evaluate the objective function value in line 13. If the step is accepted, then the temporary can be equilibrated to match the corresponding factor matrix (rather than recomputed), and the objective function evaluation is essentially free. If the step is rejected, then the evaluation is an added cost which is less than the cost of the full precomputation subroutine.
Generalization to d-way Case
While we detail Newton’s algorithm for CP for the simpler 3-way case, we describe in this subsection how the derivations, computations, and conclusions generalize to the -way case. As usual, the notational complexity of the -way case can obscure the key concepts. We briefly introduce -way notation and provide examples rather than comprehensive expressions to illustrate the ideas. We consider to be a -way data tensor with dimensions and a rank- CP model with factor matrices . We use to index dimension for and to index (as in the 3-way case), and we use MATLAB-style indexing with parentheses when subscript notation becomes overwhelming. Note that the description of Gauss-Newton methods for the -way case is given in [3 Ch. 13].
The structure of the term of the -way Hessian matches the one derived in § 3.2: we consider it as a symmetric block matrix with each block corresponding to the mixed partials of a pair of factor matrices. This implies that the diagonal blocks are zeros and the off-diagonal blocks are given by expressions that generalize Lem. 2. In the case of factor matrices and , the corresponding off-diagonal block is given by where is the tensor computed from a partial MTTKRP involving the residual tensor and all factor matrices except and . Expressed elementwise for the case and , for example, we have
Applying the term of the -way Hessian to a vector follows the pattern described in § 3.3 and Lem. 3: there are matrix-vector product terms to be computed involving a block of and a vectorization of a matrix with the dimensions of one of the two corresponding factor matrices. This simplifies to an MTTKRP involving the residual tensor, all but two factor matrices from the Newton iterate, and one factor matrix from the arbitrary vector. For a notationally convenient example, we have
As in the 3-way case, we must avoid explicitly computing the MTTKRPs involving either the residual tensor or the data tensor at every iteration of GLRT. Instead, we precompute the partial MTTKRPs involving the data tensor and all but two of the Newton iterate factor matrices. Each of these intermediate tensors are 3-way, with two dimensions corresponding to original tensor dimensions (that have not been contracted) and one dimension corresponding to the rank of the CP model. Similar to the definition of above, we have
Note that in the 3-way case, the partial MTTKRP involving all but two factor matrices simplifies to a TTM with one factor matrix. We can also precompute the Gram matrices of the factor matrices of the Newton iterate (e.g., ). Both sets of intermediates are re-used multiple times in evaluating the gradient and applying .
In the 3-way case, the cost of the precomputations is dominated by the three TTMs, which is 50% more than the cost of the two partial MTTKRPs required of ALS or Gauss-Newton methods (when memoization is used). The key to the efficiency in the -way case is to take advantage of memoization in the computation of the tensors. Despite the fact that the number of intermediates to be computed is , we can compute only 3 partial MTTKRPs involving the original data tensor using dimension tree memoization, and the rest of the computations are considerably cheaper [17 Sec. 3.2.3]. The central idea is to choose 3 minimal overlapping subsets of modes such that every pair of modes appears in at least one subset. This implies that the leading order cost of precomputations is still only 50% more than that of ALS or Gauss-Newton methods in the -way case.
Assuming a cubical -way tensor and a rank- CP model, the complexity comparison given in Tab. 1 generalizes as follows. In each outer iteration, the precomputation for Newton’s method is dominated by compared to for Gauss-Newton. The costs of gradient completions (), Gram matrices (), and rejected steps () are the same between methods. In each inner iteration, the cost of applying shared by both methods is , and the added cost of applying is . Because the cost of the precomputations in the outer iteration is the only cost exponential in , we expect to be even more dominated by that step for . Thus, the estimate of Newton iterations costing 50% more than Gauss-Newton iterations should be more accurate for larger .
Numerical Experiments
We implement Alg. 4 in MATLAB using Tensor Toolbox [2] functions for many of the subroutines. We compare against our implementation of Gauss-Newton, which is a modification of our Newton’s method implementation, differing only in that it does not apply the matrix within GLRT. In addition, we consider a hybrid in which Gauss-Newton steps are taken until the norm of the gradient drops below a pre-specified limit, and thereafter Newton steps are taken. We also compare our Gauss-Newton implementation to that in Tensorlab [32] to serve as a baseline, and also to ALS as implemented in Tensor Toolbox [2]. We measure progress in iterations rather than wall-clock time, as our MATLAB implementation has not been performance optimized. We do not visualize rejected steps in the plots; as discussed in § 3.4, a rejected step has about 1/3rd the cost of an accepted step. Table 2 illustrates the number of rejected steps in one of the experiments as a representative example.
Solvers
Each step of our Gauss-Newton (GN) and Newton solvers approximately minimizes a cubic-regularized model shown in eq. (4) using GLRT [8] with a block-diagonal preconditioner [25, 31, 3] and at most 100 inner iterations. The regularization weight starts at . A step is rejected based on the ratio between the true and model decrease: a step is rejected if . Accepted steps with multiply by 3, and those with divide it by 2. The inner tolerance follows the Eisenstat–Walker forcing terms [11], with , , and exponent for GN and for Newton. The hybrid method runs Gauss-Newton until and then switches permanently to Newton. These three methods stop when or when they reach the iteration limit.
‘Tensorlab GN’ is cpd_nls, modified to stop on the gradient norm so that it matches our methods.1 It uses the same gradient tolerance, iteration limit, and maximum number of CG iterations as our methods; all other options are left at their defaults.
The data tensor is scaled to unit Frobenius norm. In each trial we draw Gaussian random initial factors and scale them so that the initial model has the same norm as the data; this keeps the iterate away from the critical point at zero, where the gradient vanishes and the relative error is one. All methods in a trial start from the same initial guess. Trial uses random seed , so different values of a swept parameter share the same initial tensor.
Metrics
We report the relative error and the gradient norm at each iteration, where is the original data, and is the CP model. For synthetic tensors, the true factors are known, so we also measure a proxy for the forward error using the Tensor Toolbox score function, which matches computed components to true components using the cosine similarities between corresponding rank-one components [3 Sec. 10.8]. A score of 1 indicates exact recovery. When the model rank differs from the true rank, the extra components of the larger model are left unmatched. Because Tensorlab returns only the final factors, its score is shown only at the final iterate. We stop on the gradient norm rather than the objective because the score can keep improving well after the relative error has leveled off (see Figure 3, for example).
Figure 3. Synthetic tensors with and , for noise parameter . Rows show relative error, gradient norm, and score; the dotted line marks the relative error of the true model, approximately , and the dashed line marks the gradient tolerance.
Synthetic tensors are , generated with Tensor Toolbox’s create_problem: the factor matrices have unit weights and columns with collinearity , and noise is added as
with Gaussian and .2
We demonstrate the performance of Newton’s method on synthetic and real-world datasets. As discussed in § 3.1, Gauss-Newton converges quickly when the residual at the solution is small, but its convergence slows as the residual grows. Near a local minimizer, Newton’s method retains fast convergence regardless of the residual. Far from a minimizer, however, we observe that Newton’s method can take more iterations than Gauss-Newton to find a neighborhood of a local minimum. These findings motivate the hybrid method described at the start of § 4, which starts with Gauss-Newton and switches to Newton’s method when the gradient norm is sufficiently small.
Without noise, our synthetic tensors are exactly low rank, so a model of the true rank has zero residual at the solution. We therefore introduce residual either by adding noise or by underestimating the rank, and we use high collinearity of the true factors to make the problem harder without introducing residual. For visual clarity, not every method appears in every figure. In each figure, we show the trajectories for relative error, gradient norm, and score (if applicable) for each method and for five random trials.
Varying Collinearity
We first vary the collinearity of the true factors while keeping the residual at zero (Figure 2). The model rank matches the true rank, , and no noise is added, so a fitted model can attain zero relative error. Each method runs for at most 100 iterations.
Figure 2. Synthetic tensors with and , for collinearity . Rows show relative error, gradient norm, and score; the dashed line marks the gradient tolerance.
High collinearity is known to slow the convergence of ALS [19, 26]. As increases, ALS slows, and at it stalls: its relative error is high, its gradient norm barely decreases, and the score is sub-optimal. In contrast, Gauss-Newton and Newton reach the gradient tolerance at every collinearity level and recover the true factors, with a score of 1. Our Gauss-Newton implementation converges in a similar number of iterations as the Tensorlab implementation, so we will use it as a baseline to compare against Newton.
Newton takes approximately twice as many iterations as Gauss-Newton at every collinearity level, although both achieve superlinear convergence eventually. Since the residual vanishes at the solution, so does , and the two methods take nearly the same steps once they are close to a minimizer. The difference therefore comes from the early iterations: far from a minimizer, is not negligible, and Newton wanders before it reaches the region where it converges quickly.
Varying Noise
Next, we fix collinearity at and rank and vary the noise parameter from (8), so that the true model has relative error approximately (Figure 3). Because the data is otherwise exactly low rank, a large amount of noise is needed before the residual noticeably affects Gauss-Newton. Each method runs for at most 100 iterations.
For and , both Gauss-Newton and Newton converge in every trial, with Newton again taking roughly twice as many iterations. At , however, Gauss-Newton does not reach the tolerance in any trial. Newton reaches the tolerance in every trial in a similar number of iterations as for the smaller noise levels, converging superlinearly once it is close to a minimizer.
At , Newton attains a score of about 0.99 in four of the five trials, while Gauss-Newton reaches the iteration limit with a score below 0.9 in four of the five trials. This high level of noise demonstrates Newton’s robustness, and these results show that it is still able to recover the true signal.
Varying Rank
In practice, the true CP rank is not known in advance, so a model may underestimate or overestimate it. We fix , , and , and fit models of rank (Figure 4). Each method runs for at most 200 iterations in this experiment.
Figure 4. Synthetic tensors with , , and , for model rank (underestimated, correct, overestimated). Rows show relative error, gradient norm, and score; the dashed line marks the gradient tolerance.
Underestimating the rank leaves the two unmodeled components in the residual. Although the resulting relative error is only about 0.02, Gauss-Newton does not reach the tolerance in any trial, whereas Newton converges in every trial.
When the rank is correct, the residual is zero, and the results resemble those of the collinearity experiment: Newton takes roughly twice as many iterations as Gauss-Newton.
Overestimating the rank also allows zero residual, but the solution is no longer unique, and convergence is less consistent for every method. Within 200 iterations, Gauss-Newton converges in four trials, and Newton converges in two. Even when a method converges, its score can be less than 1: each true component is matched to a single computed component and any extra components are ignored, so a true component that is split between two computed components is only partially recovered.
Motivation for the Hybrid Method
We conclude the synthetic experiments by comparing the gradient-based methods on two illustrative problems (Figure 5) that motivate the use of a hybrid method. We contrast two cases: ‘easy’ and ‘hard’. The easy problem has low collinearity, the correct rank, and no noise. The hard problem combines the difficulties of the previous experiments: high collinearity, an overestimated rank, and high noise.
Figure 5. Synthetic tensors. Left (Easy): , , and . Right (Hard): , , , and . Rows show relative error, gradient norm, and score; the dashed line marks the gradient tolerance.
On the easy problem, Gauss-Newton and Tensorlab GN converge quickly. Note that the x-axis is truncated to 50 iterations for the easy problem to better highlight the convergence pattern. Newton takes about twice as many iterations as Gauss-Newton similarly to the collinearity experiment. The hybrid method reaches the switching threshold only one iteration before it converges, so it follows Gauss-Newton almost exactly. All methods achieve a perfect score of 1, exactly recovering the true factors.
On the hard problem, neither Gauss-Newton implementation reaches the tolerance in any trial, so this failure is not specific to our implementation. Newton and the hybrid method converge in every trial and also reach a high score in all trials, while Gauss-Newton and Tensorlab GN mostly stop near 0.9. For this experiment, we also report the number of accepted and rejected steps taken by each method in Table 2. On the hard problem, the hybrid method rejects roughly 20 more steps per trial than Gauss-Newton but takes roughly 100 fewer accepted steps. Since a rejected step costs about a third of an accepted one (see § 3.4), counting rejected steps does not change the conclusion.
| Method | Easy Accepted | Easy Rejected | Hard Accepted | Hard Rejected |
| Gauss-Newton | 13–17 | 4–7 | 200 | 7–13 |
| Tensorlab GN | 13–17 | 2–4 | 200 | 20–26 |
| Newton | 25–34 | 9–15 | 76–89 | 30–35 |
| Hybrid | 12–17 | 4–7 | 71–109 | 20–32 |
Table 2. Range over 5 trials of the number of accepted and rejected steps for each method. The iteration limit counts accepted steps only.
The hybrid method therefore costs almost nothing when Gauss-Newton converges quickly, and converges like Newton when Gauss-Newton fails, without knowing in advance which kind of problem it faces.
Gas Sensor Array
We next consider the gas sensor array dataset [29], which has been used to benchmark CP methods in [30, 4]. We follow the preprocessing of [30], except that we keep every 25th time sample to reduce running time, giving a tensor (time sensor experiment).3 We fit , as in [30, 4], and also , for which convergence is more regular (Figure 6). Each method runs for at most 200 iterations. Since the true factors are unknown, we report only relative error and gradient norm.
Figure 6. Gas sensor array tensor (), for . Rows show relative error and gradient norm; the dashed line marks the gradient tolerance. The true factors are unknown, so no score is shown.
Unlike our synthetic tensors, this data is not close to low rank: the computed minimizers have relative errors of about 0.26 for and 0.19 for . For , Gauss-Newton, Newton, and the hybrid method converge in every trial, but in contrast to the zero-residual synthetic problems, Newton converges in fewer iterations than Gauss-Newton. The hybrid method converges faster still, while ALS and Tensorlab GN do not reach the gradient tolerance in any trial. For , no method converges consistently: the hybrid method converges in three trials, Gauss-Newton in two, and Newton in none. In the trials where both converge, the hybrid method takes about half as many iterations as Gauss-Newton.
Monkey BMI
Finally, we consider the Monkey BMI dataset from [3], originally collected in [33], a tensor (neuron time trial). In [3], the rank is chosen where the relative error stops significantly improving, and a nonnegative model of rank 10 is fit. Since our goal is instead to study convergence in the gradient norm, we fit unconstrained models of rank (Figure 7). The convergence behavior for to 10 is similar to that for and is not shown. The relative errors of the computed minimizers are about 0.48, 0.45, and 0.42, respectively, roughly in line with our synthetic experiment.
Figure 7. Monkey BMI tensor (), for . Rows show relative error and gradient norm; the dashed line marks the gradient tolerance. The true factors are unknown, so no score is shown, and only the first 100 of 200 iterations are shown.
For , every method converges within 25 iterations. For , Newton converges in about a third as many iterations as Gauss-Newton, and the hybrid method is only slightly slower than Newton. For , no method reaches the tolerance within the iteration limit, although Gauss-Newton, Newton, and the hybrid method all reach the same relative error.
Conclusion
We have presented an efficient way to apply the true Hessian of the CP model’s objective function to a vector. This allows us to employ a safeguarded Newton method to solve the CP optimization problem, as this can converge much faster than currently used CP algorithms such as ALS and Gauss-Newton (when the residual is large). We have shown that the per-outer-iteration cost of applying the Newton Hessian is roughly 50% higher than that of Gauss-Newton for large tensors.
Gauss-Newton and Newton models for CP have intrinsic issues arising from the ambiguity of ordering and scaling the columns in the factor matrices, resulting in rank-deficient Hessians. An adaptive cubic-regularization technique allowed both methods to overcome the rank deficiency issue and to globalize them, that is, to ensure that the generated iterates converge from any starting point.
Numerical experiments on a variety of synthetic problems and real datasets demonstrated that the asymptotic convergence of Gauss-Newton depends on the difficulty of the problem at hand. The convergence rate of Gauss-Newton ranged from superlinear on easy problems to linear on mild to hard problems (even stagnation in some cases), while Newton-based methods exhibit asymptotic superlinear convergence. In this case, “hard” problems refer to inconsistent problems, large nonzero residual problems and/or highly ill-conditioned factor matrices, which frequently occur in practice. Since Newton convergence was often slow at the start of the minimization, and noticeably slower than that of Gauss-Newton, a hybrid method that starts with a Gauss-Newton model and switches to a Newton model exhibits the best features of both methods, and this is what we recommend practitioners use. The main caveat of the hybrid method is that the threshold for switching from Gauss-Newton to Newton may need tuning.
With savings beyond a factor of two iterations and success where Gauss-Newton struggles to converge, at the cost of extra in the last few iterations, we recommend the hybrid method as the default for Hessian-based CP fitting. While our complexity analysis supports using the number of iterations as a proxy for time, the next step is to demonstrate that the hybrid method also reduces time compared to the alternatives. Future work will replace our MATLAB implementation with optimized computational kernels, including techniques for memoization in the -way case discussed in § 3.5.
While the equilibration technique given by eq. (5) has proved effective in practice, it might be better to try to enforce normalization directly as part of the minimization problem. For example, in the 3-way case, we currently employ the unweighted rank- Kruskal tensor with all the ambiguity that it implies. Another possibility is to use the weighted variant , where now we require that and . These norms mean exactly that the unknowns in lie on a Riemannian manifold, and there are manifold optimization methods [5] that impose such constraints explicitly, thereby removing local ambiguities. We are currently considering the application of such methods to this alternative formulation, and note that the required Jacobian and Hessian products we have developed are easily modified for such a Riemannian derivative case.
Acknowledgements
This material is based upon work supported by the US Department of Energy, Office of Science, Advanced Scientific Computing Research program under awards DE-SC0023296 and DE-SC0025394. Al Daas and Gould are supported by the Ada Lovelace Centre Programme at the Scientific Computing Department, STFC.
During the preparation of this work, the authors used Claude to assist with the following tasks: writing the MATLAB code for our experiments, drafting both the Hessian derivations and the discussion of each experiment, creating the TikZ code for each figure in the manuscript, and checking for mathematical and notational consistency. Afterwards, the authors reviewed and edited the content as needed and take full responsibility for the content of the published article.
References
- [1]E. Acar, D. M. Dunlavy, and T. G. Kolda. A scalable optimization approach for fitting canonical tensor decompositions. Journal of Chemometrics, 25(2):67–86, 2011. doi:10.1002/cem.1335.DOI
- [2]B. W. Bader, T. G. Kolda, et al. MATLAB Tensor Toolbox version 3.8. Available online, October 2025. URL: https://www.tensortoolbox.org.
- [3]G. Ballard and T. G. Kolda. Tensor Decompositions for Data Science. Cambridge University Press, June 2025. URL: https://tensor-toolbox.com/.DOI
- [4]C. Battaglino, G. Ballard, and T. G. Kolda. A practical randomized CP tensor decomposition. SIAM Journal on Matrix Analysis and Applications, 39(2):876–901, 2018. doi: 10.1137/17M1112303.DOI
- [5]N. Boumal. An Introduction to Optimization on Smooth Manifolds. Cambridge University Press, 2023. doi:10.1017/9781009166164.DOI
- [6]J. D. Carroll and J.-J. Chang. Analysis of individual differences in multidimensional scaling via an n-way generalization of “Eckart-Young” decomposition. Psychometrika, 35(3):283–319, Sep 1970. doi:10.1007/BF02310791.DOI
- [7]C. Cartis, N. I. M. Gould, and P. L. Toint. Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results. Mathematical Programming, 127(2):245–295, May 2009. doi:10.1007/s10107-009-0286-5.DOI
- [8]C. Cartis, N. I. M. Gould, and Ph. L. Toint. Evaluation Complexity of Algorithms for Nonconvex Optimization: Theory, Computation, and Perspectives. SIAM, Philadelphia, USA, 2022. doi:10.1137/1.9781611976991.DOI
- [9]A. R. Conn, N. I. M. Gould, and Ph. L. Toint. Trust-Region Methods. SIAM, Philadelphia, USA, 2000. doi:10.1137/1.9780898719857.DOI
- [10]J. E. Dennis and R. B. Schnabel. Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice-Hall, Englewood Cliffs, New Jersey, USA, 1983. Reprinted as Classics in Applied Mathematics 16, SIAM, Philadelphia, USA, 1996. doi:10.1137/1.9781611971200.
- [11]S. C. Eisenstat and H. F. Walker. Choosing the forcing terms in an inexact Newton method. SIAM Journal on Scientific Computing, 17(1):16–32, January 1996. doi:10.1137/0917003.DOI
- [12]M. Espig and W. Hackbusch. A regularized newton method for the efficient approximation of tensors represented in the canonical tensor format. Numerische Mathematik, 122(3):489–525, May 2012. doi:10.1007/s00211-012-0465-9.DOI
- [13]R. A. Harshman. Foundations of the PARAFAC procedure: Models and conditions for an explanatory multimodal factor analysis. Working Papers in Phonetics, 16(10,085):1 – 84, 1970. URL: http://www.psychology.uwo.ca/faculty/harshman/wpppfac0.pdf.
- [14]H. V. Henderson and S. R. Searle. The vec-permutation matrix, the vec operator and Kronecker products: a review. Linear and Multilinear Algebra, 9(4):271–288, 1981. doi: 10.1080/03081088108817379.DOI
- [15]V. A. Kazeev and E. E. Tyrtyshnikov. Structure of the hessian matrix and an economical implementation of newton’s method in the problem of canonical approximation of tensors. Computational Mathematics and Mathematical Physics, 50(6):927–945, 2010. doi:10.1134/S0965542510060011.DOI
- [16]K. Levenberg. A method for the solution of certain problems in least squares. Quarterly of Applied Mathematics, 2(2):164–168, 1944. doi:10.1090/qam/10666.DOI
- [17]L. Ma and E. Solomonik. Accelerating alternating least squares for tensor decomposition by pairwise perturbation. Numerical Linear Algebra with Applications, 29:1–33, 2022. doi:10.1002/nla.2431.DOI
- [18]D. Marquardt. An algorithm for least-squares estimation of nonlinear parameters. SIAM Journal on Applied Mathematics, 11(2):431–441, 1963. doi:10.1137/0111030.DOI
- [19]B. C. Mitchell and D. S. Burdick. Slowly converging parafac sequences: Swamps and two-factor degeneracies. Journal of Chemometrics, 8(2):155–168, 1994. doi:10.1002/cem.1180080207.DOI
- [20]D. D. Morrison. Methods for nonlinear least squares problems and convergence proofs. In J. Lorell and F. Yagi, editors, Proceedings of the Seminar on Tracking Programs and Orbit Determination, pages 1–9, Pasadena, USA, 1960. Jet Propulsion Laboratory.
- [21]J. Nocedal and S. J. Wright. Numerical Optimization. Series in Operations Research. Springer Verlag, Heidelberg, Berlin, New York, second edition, 2006. doi:10.1007/978-0-387-40065-5.DOI
- [22]P. Paatero. A weighted non-negative least squares algorithm for three-way PARAFAC factor analysis. Chemometrics and Intelligent Laboratory Systems, 38(2):223 – 242, 1997. doi:10.1016/S0169-7439(97)00031-2.DOI
- [23]C. C. Paige and M. A. Saunders. LSQR: An algorithm for sparse linear equations and sparse least squares. ACM Transactions on Mathematical Software (TOMS), 8(1):43–71, 1982. doi:10.1145/355984.355989.DOI
- [24]M. A. Paige, C. C.and Saunders. Solution of sparse indefinite systems of linear equations. SIAM Journal on Numerical Analysis, 12(4):617–629, 1975. doi:10.1137/0712047.DOI
- [25]L. Sorber, M. Van Barel, and L. de Lathauwer. Optimization-based algorithms for tensor decompositions: Canonical polyadic decomposition, decomposition in rank-(Lr,Lr,1) terms, and a new generalization. SIAM Journal on Optimization, 23(2):695–720, 2013. doi:10.1137/120868323.DOI
- [26]G. Tomasi and R. Bro. A comparison of algorithms for fitting the PARAFAC model. Computational Statistics & Data Analysis, 50(7):1700–1734, 2006. doi:10.1016/j.csda.2004.11.013.
- [27]Giorgio Tomasi. Practical and Computational Aspects in Chemometric Data Analysis. PhD thesis, Royal Veterinary and Agricultural University, 2006. URL: http://models.life.ku.dk/sites/default/files/Thesis_Giorgio_Tomasi.pdf.
- [28]A. Uschmajew. Local convergence of the alternating least squares algorithm for canonical tensor approximation. SIAM Journal on Matrix Analysis and Applications, 33(2):639–652, 2012. doi:10.1137/110843587.DOI
- [29]A. Vergara. Gas sensor arrays in open sampling settings, 2013. doi:10.24432/C5JP5N.
- [30]N. Vervliet and L. De Lathauwer. A Randomized Block Sampling Approach to Canonical Polyadic Decomposition of Large-Scale Tensors. IEEE Journal of Selected Topics in Signal Processing, 10(2):284–295, March 2016. doi:10.1109/JSTSP.2015.2503260.DOI
- [31]N. Vervliet and L. De Lathauwer. Numerical optimization-based algorithms for data fusion. In Data Handling in Science and Technology, volume 31, pages 81–128. Elsevier, 2019. doi:10.1016/B978-0-444-63984-4.00004-1.DOI
- [32]N. Vervliet, O. Debals, L. Sorber, M. Van Barel, and L. De Lathauwer. Tensorlab 3.0. https://www.tensorlab.net, 2016.DOI
- [33]S. Vyas, N. Even-Chen, S. D. Stavisky, S. I. Ryu, P. Nuyujukian, and K. V. Shenoy. Neural population dynamics underlying motor learning transfer. Neuron, 97(5):1177–1186, 2018. doi:10.1016/j.neuron.2018.01.040.






