betaFeedback

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 rr, the corresponding optimization problem is nonlinear and nonconvex. There may not exist a best rank-rr

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., X\mathcal{X}), capital boldface for matrices (e.g., A\mathbf{A}), lower-case boldface for vectors (e.g., v\mathbf{v}), and regular font for scalars (e.g., ff). We focus on 3-way tensors in this work, but the methods generalize to the dd-way case. In general, we assume the input data tensor X∈Rm×n×p\mathcal{X} \in\mathbb{R}^{m \times n \times p}, and we index into those dimensions using ii, jj, and kk, respectively.

In computing a CP approximation of X\mathcal{X}, we consider the CP model as a Kruskal tensor T\mathcal{T} of rank rr represented by three factor matrices A∈Rm×r\mathbf{A} \in\mathbb{R}^{m \times r}, B∈Rn×r\mathbf{B} \in\mathbb{R}^{n \times r}, and C∈Rp×r\mathbf{C} \in\mathbb{R}^{p \times r}, and we use ℓ\ell to index over the rank rr. In shorthand, we write T=[[A,B,C]]\mathcal{T} = [[\mathbf{A}, \mathbf{B}, \mathbf{C}]], where

tijk=∑ℓ=1raiℓbjℓckℓ,or equivalentlyT=∑ℓ=1raℓ∘bℓ∘cℓ,t_{ijk} = \sum_{\ell=1}^{r} a_{i\ell}b_{j\ell}c_{k\ell}, \qquad\text{or equivalently} \qquad\mathcal{T} = \sum_{\ell=1}^{r} \mathbf{a}_{\ell} \circ\mathbf{b}_{\ell} \circ\mathbf{c}_{\ell},

where ∘\circ denotes the vector outer product and aℓ\mathbf{a}_{\ell} is the ℓ\ellth column of A\mathbf{A}, bℓ\mathbf{b}_{\ell} is the ℓ\ellth column of B\mathbf{B}, and cℓ\mathbf{c}_{\ell} is the ℓ\ellth column of C\mathbf{C}. 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 a\mathbf{a}, b\mathbf{b} and c\mathbf{c} of the factor matrices A\mathbf{A}, B\mathbf{B} and C\mathbf{C}, the term a∘b∘c\mathbf{a} \circ\mathbf{b} \circ\mathbf{c} in the Kruskal tensor is identical to a^∘b^∘c^\hat{\mathbf{a}} \circ\hat{\mathbf{b}} \circ\hat{\mathbf{c}}, whenever a^=αa\hat{\mathbf{a}} = \alpha\mathbf{a}, b^=βb\hat{\mathbf{b}} = \beta\mathbf{b} and c^=γc\hat{\mathbf{c}} = \gamma\mathbf{c} for any three scalars satisfying αβγ=1\alpha\beta\gamma= 1.

Derivative Notation

Let f(v):Rn→Rf(\mathbf{v}) : \mathbb{R}^{n} \to\mathbb{R}. Then the gradient g(v)=∇f(v)\mathbf{g}(\mathbf{v}) = \nabla f(\mathbf{v}) of ff is the vector of partial derivatives with respect to each of the elements of v\mathbf{v}, with [g(v)]i=∂f∂vi[\mathbf{g}(\mathbf{v})]_i = \frac{\partial f}{\partial v_i}. The Hessian H(v)=∇2f(v)\mathbf{H}(\mathbf{v}) = \nabla^2 f(\mathbf{v}) is the matrix of second derivatives with respect to pairs of the elements of v\mathbf{v}, with [H(v)]ij=∂2f∂vi∂vj[\mathbf{H}(\mathbf{v})]_{ij} = \frac{\partial^2 f}{\partial v_i \partial v_j}.

Let r(v):Rn→Rm\mathbf{r}(\mathbf{v}) : \mathbb{R}^{n} \to\mathbb{R}^{m}. Then the derivative J(v)\mathbf{J}(\mathbf{v}) of r\mathbf{r} is the Jacobian matrix containing the partial derivatives with respect to each variable vv and each element of the output of r\mathbf{r}, with [J(v)]ij=∂ri∂vj[\mathbf{J}(\mathbf{v})]_{ij} = \frac{\partial r_i}{\partial v_j}. Note that we follow the convention of considering gradients as column vectors, which implies that the gradient of an element of r(v)\mathbf{r}(\mathbf{v}) is the transpose of the corresponding row of the Jacobian.

Definition 1 (Derivatives of Nonlinear Sum of Squares). Let r(v):Rn→Rm\mathbf{r}(\mathbf{v}) : \mathbb{R}^{n} \to\mathbb{R}^{m} and f(v):Rn→Rf(\mathbf{v}) : \mathbb{R}^{n} \to\mathbb{R} be such that f(v)=12∥r(v)∥2f(\mathbf{v}) = \frac{1}{2}\lVert\mathbf{r}(\mathbf{v})\rVert^{2}. Then the gradient g(v)\mathbf{g}(\mathbf{v}) of f(v)f(\mathbf{v}) is given by

g(v)≡∇f(v)=JT(v)r(v),\mathbf{g}(\mathbf{v}) \equiv\nabla f(\mathbf{v}) = \mathbf{J}^{\mathsf{T}}(\mathbf{v})\mathbf{r}(\mathbf{v}),

and the Hessian H(v)\mathbf{H}(\mathbf{v}) of ff is given by

H(v)≡∇2f(v)=JT(v)J(v)+∑i=1mri(v)⋅∇2ri(v).\mathbf{H}(\mathbf{v}) \equiv\nabla^{2}f(\mathbf{v}) = \mathbf{J}^{\mathsf{T}}(\mathbf{v})\mathbf{J}(\mathbf{v}) + \sum_{i=1}^{m} r_i(\mathbf{v}) \cdot\nabla^{2}r_i(\mathbf{v}).

We denote the second term of this matrix K(v)\mathbf{K}(\mathbf{v}).

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 i∈[m]i \in[m] and j∈[n]j \in[n], then L:[m]×[n]→[mn]\mathsf{L} : [m] \times[n] \to[mn] is the natural linearization function such that

L(i,j;m,n)=i+(j−1)m,\mathsf{L}(i,j;m,n) = i + (j-1)m,

and L∗:[m]×[n]→[mn]\mathsf{L}^{*} : [m] \times[n] \to[mn] is the reverse linearization function such that

L∗(i,j;m,n)=j+(i−1)n.\mathsf{L}^{*}(i,j;m,n) = j + (i-1)n.

The vec operator takes a matrix A\mathbf{A} or a tensor X\mathcal{X} and linearizes it into a vector according to natural ordering.

Definition 3 (vec Operator). If A∈Rm×n\mathbf{A} \in\mathbb{R}^{m \times n}, then vec⁡(A)∈Rmn\operatorname{vec}(\mathbf{A}) \in\mathbb{R}^{mn} where

[vec⁡(A)]α=aijwithα=L(i,j;m,n)=i+(j−1)m.[\operatorname{vec}(\mathbf{A})]_{\alpha} = a_{ij}\quad\text{with}\quad\alpha= \mathsf{L}(i,j;m,n) = i + (j-1)m.

If X∈Rm×n×p\mathcal{X} \in\mathbb{R}^{m \times n \times p}, then vec⁡(X)∈Rmnp\operatorname{vec}(\mathcal{X}) \in\mathbb{R}^{mnp} where

[vec⁡(X)]α=xijkwithα=i+(j−1)m+(k−1)mn.[\operatorname{vec}(\mathcal{X})]_{\alpha} = x_{ijk}\quad\text{with}\quad\alpha= i + (j-1)m + (k-1)mn.

We can reshape a tensor into a matrix using modal unfoldings. We use the notation X(1)\mathbf{X}_{(1)} to denote the mode-1 unfolding, which stacks the mode-1 fibers as columns into a matrix with columns in natural order. That is, [X(1)]iα=xijk[\mathbf{X}_{(1)}]_{i\alpha} = x_{ijk} for α=L(j,k;n,p)\alpha= \mathsf{L}(j,k;n,p). Likewise, [X(2)]jβ=xijk[\mathbf{X}_{(2)}]_{j\beta} = x_{ijk} for β=L(i,k;m,p)\beta= \mathsf{L}(i,k;m,p) and [X(3)]kγ=xijk[\mathbf{X}_{(3)}]_{k\gamma} = x_{ijk} for γ=L(i,j;m,n)\gamma= \mathsf{L}(i,j;m,n). In particular, this implies vec⁡(X)=vec⁡(X(1))\operatorname{vec}(\mathcal{X}) = \operatorname{vec}(\mathbf{X}_{(1)}).

The Kronecker, Khatri-Rao, and Hadamard products are central to the analysis of methods for computing CP decompositions.

Definition 4 (Kronecker Product). If A∈Rm×p\mathbf{A} \in\mathbb{R}^{m \times p} and B∈Rn×q\mathbf{B} \in\mathbb{R}^{n \times q}, then A⊗B∈Rmn×pq\mathbf{A} \otimes\mathbf{B} \in\mathbb{R}^{mn \times pq} where

[A⊗B]αβ=aikbjℓwith{α=L∗(i,j;m,n)=j+(i−1)nβ=L∗(k,ℓ;p,q)=ℓ+(k−1)q[\mathbf{A} \otimes\mathbf{B}]_{\alpha\beta} = a_{ik}b_{j\ell}\quad\text{with}\quad \begin{cases} \alpha= \mathsf{L}^{*}(i,j;m,n) = j + (i-1)n\\ \beta= \mathsf{L}^{*}(k,\ell;p,q) = \ell+ (k-1)q \end{cases}

If aa and bb are column vectors of length mm and nn, then a⊗ba \otimes b is a column vector of length mnmn.

Definition 5 (Khatri-Rao Product). If A∈Rm×p\mathbf{A} \in\mathbb{R}^{m \times p} and B∈Rn×p\mathbf{B} \in\mathbb{R}^{n \times p}, then A⊙B∈Rmn×p\mathbf{A} \odot\mathbf{B} \in\mathbb{R}^{mn \times p} such that

[A⊙B]αℓ=aiℓbjℓwithα=L∗(i,j;m,n)=j+(i−1)n.[\mathbf{A} \odot\mathbf{B}]_{\alpha\ell} = a_{i\ell}b_{j\ell} \quad\text{with} \quad\alpha= \mathrm{L}^{*}(i,j;m,n) = j + (i-1)n.

The Khatri-Rao Product is equivalently the Kronecker products of each of the corresponding columns in A\mathbf{A} and B\mathbf{B}.

Definition 6 (Hadamard Product). If A∈Rm×n\mathbf{A} \in\mathbb{R}^{m \times n} and B∈Rm×n\mathbf{B} \in\mathbb{R}^{m \times n}, then A∗B∈Rm×n\mathbf{A} * \mathbf{B} \in\mathbb{R}^{m \times n} with

[A∗B]ij=aijbij.[\mathbf{A} * \mathbf{B}]_{ij} = a_{ij}b_{ij}.

Definition 7 (Tensor-Times-Matrix Product [3 Def. 3.14]). The mode-kk tensor-times-matrix (TTMTTM) product between a tensor X\mathcal{X} and a matrix U\mathbf{U} is written Y=X×kU\mathcal{Y} = \mathcal{X} \times_k \mathbf{U} and is defined by

Y(k)=UX(k).\mathcal{Y}_{(k)} = \mathbf{U}\mathcal{X}_{(k)}.

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 A∈Rm×p\mathbf{A} \in\mathbb{R}^{m \times p}, B∈Rn×q\mathbf{B} \in\mathbb{R}^{n \times q}, and X∈Rp×q\mathbf{X} \in\mathbb{R}^{p \times q}, we have

(B⊗A)vec⁡(X)=vec⁡(AXBT).(\mathbf{B} \otimes\mathbf{A})\operatorname{vec}(\mathbf{X}) = \operatorname{vec}(\mathbf{A}\mathbf{X}\mathbf{B}^{\mathsf{T}}).

Corollary 1.

(BT⊗I)vec⁡(A)=vec⁡(AB)=(I⊗A)vec⁡(B)(\mathbf{B}^{\mathsf{T}} \otimes\mathbf{I})\operatorname{vec}(\mathbf{A}) = \operatorname{vec}(\mathbf{A}\mathbf{B}) = (\mathbf{I} \otimes\mathbf{A})\operatorname{vec}(\mathbf{B})

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 A\mathbf{A} and B\mathbf{B}.

Property 2 ([3 Prop. A.18]). For A∈Rm×n\mathbf{A} \in\mathbb{R}^{m \times n}, B∈Rq×r\mathbf{B} \in\mathbb{R}^{q \times r}, C∈Rn×p\mathbf{C} \in\mathbb{R}^{n \times p}, and D∈Rr×s\mathbf{D} \in\mathbb{R}^{r \times s}, we have

(A⊗B)(C⊗D)=(AC⊗BD).(\mathbf{A} \otimes\mathbf{B})(\mathbf{C} \otimes\mathbf{D}) = (\mathbf{A}\mathbf{C} \otimes\mathbf{B}\mathbf{D}).

Property 3 ([3 Prop. A.23]). For A∈Rm×r\mathbf{A} \in\mathbb{R}^{m \times r}, B∈Rn×r\mathbf{B} \in\mathbb{R}^{n \times r}, C∈Rm×s\mathbf{C} \in\mathbb{R}^{m \times s}, and D∈Rn×s\mathbf{D} \in\mathbb{R}^{n \times s}, we have

(A⊙B)T(C⊙D)=ATC∗BTD.(\mathbf{A} \odot\mathbf{B})^{\mathsf{T}}(\mathbf{C} \odot\mathbf{D}) = \mathbf{A}^{\mathsf{T}}\mathbf{C} * \mathbf{B}^{\mathsf{T}}\mathbf{D}.

Definition 8. Let X∈Rm×n×p\mathcal{X} \in\mathbb{R}^{m \times n \times p} be a 3-way tensor. Define the block diagonal operator blkdiag⁡1(X)\operatorname{blkdiag}_{1}(\mathcal{X}) to take the horizontal slices of X\mathcal{X} and arrange them as the diagonal entries of a m×mm \times m block matrix such that:

blkdiag⁡1(X)=[X(1,:,:)0⋱0X(m,:,:)]=∑i=1mEii⊗X(i,:,:),\operatorname{blkdiag}_{1}(\mathcal{X}) = \begin{bmatrix} \mathcal{X}(1,:,:)&\mathbf{0}&\\ &\ddots&\\ \mathbf{0}&&\mathcal{X}(m,:,:) \end{bmatrix} = \sum_{i=1}^{m}\mathbf{E}_{ii}\otimes\mathcal{X}(i,:,:),

where Eii=eieiT\mathbf{E}_{ii} = \mathbf{e}_{i}\mathbf{e}_{i}^{\mathsf{T}} 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 X∈Rm×n×p\mathcal{X} \in\mathbb{R}^{m \times n \times p} be a 3-way tensor, the CP optimization problem is defined as

min⁡A,B,Cf(A,B,C)≡12∥⟦A,B,C⟧−X∥2subject to A∈Rm×r, B∈Rn×r, C∈Rp×r,\min_{\mathbf{A},\mathbf{B},\mathbf{C}} f(\mathbf{A},\mathbf{B},\mathbf{C}) \equiv\frac{1}{2}\left\|\llbracket\mathbf{A},\mathbf{B},\mathbf{C}\rrbracket-\mathcal{X}\right\|^2 \quad\text{subject to } \mathbf{A}\in\mathbb{R}^{m\times r},\ \mathbf{B}\in\mathbb{R}^{n\times r},\ \mathbf{C}\in\mathbb{R}^{p\times r},

or equivalently, to match the notation of Def. 1,

min⁡vf(v)≡12∥r(v)∥2withv=[vec⁡(A)vec⁡(B)vec⁡(C)]∈Rmr+nr+prandr(v)=vec⁡(⟦A,B,C⟧−X).\min_{\mathbf{v}} f(\mathbf{v}) \equiv\frac{1}{2}\|\mathbf{r}(\mathbf{v})\|^2 \quad\text{with}\quad\mathbf{v}=\begin{bmatrix}\operatorname{vec}(\mathbf{A})\\ \operatorname{vec}(\mathbf{B})\\ \operatorname{vec}(\mathbf{C})\end{bmatrix}\in\mathbb{R}^{mr+nr+pr}\quad\text{and}\quad\mathbf{r}(\mathbf{v})=\operatorname{vec}(\llbracket\mathbf{A},\mathbf{B},\mathbf{C}\rrbracket-\mathcal{X}).

Thus, this CP approximation problem is a nonlinear least squares problem with the following Jacobian and gradient.

Lemma 1. [1, 3] For f(v)=12∥r(v)∥2f(\mathbf{v})=\frac{1}{2}\|\mathbf{r}(\mathbf{v})\|^2 as given by Def. 9, the Jacobian of r\mathbf{r} is

J(v)=[∂r∂vec⁡(A)∂r∂vec⁡(B)∂r∂vec⁡(C)]=[(C⊙B)⊗ImP2[(C⊙A)⊗In]P3[(B⊙A)⊗Ip]],\mathbf{J}(\mathbf{v})=\left[\begin{array}{ccc}\frac{\partial\mathbf{r}}{\partial\operatorname{vec}(\mathbf{A})}&\frac{\partial\mathbf{r}}{\partial\operatorname{vec}(\mathbf{B})}&\frac{\partial\mathbf{r}}{\partial\operatorname{vec}(\mathbf{C})}\end{array}\right]=\left[(\mathbf{C}\odot\mathbf{B})\otimes\mathbf{I}_{m}\quad\mathbf{P}_{2}\left[(\mathbf{C}\odot\mathbf{A})\otimes\mathbf{I}_{n}\right]\quad\mathbf{P}_{3}\left[(\mathbf{B}\odot\mathbf{A})\otimes\mathbf{I}_{p}\right]\right],

where P2\mathbf{P}_{2} and P3\mathbf{P}_{3} are tensor perfect shuffle permutations, and the gradient of ff is

g(v)=JT(v)⋅r(v)=[vec⁡(A(CTC∗BTB)−X(1)(C⊙B))vec⁡(B(CTC∗ATA)−X(2)(C⊙A))vec⁡(C(BTB∗ATA)−X(3)(B⊙A))].\mathbf{g}(\mathbf{v})=\mathbf{J}^{T}(\mathbf{v})\cdot\mathbf{r}(\mathbf{v})= \begin{bmatrix} \operatorname{vec}\left(\mathbf{A}(\mathbf{C}^{T}\mathbf{C}*\mathbf{B}^{T}\mathbf{B})-\mathbf{X}_{(1)}(\mathbf{C}\odot\mathbf{B})\right)\\ \operatorname{vec}\left(\mathbf{B}(\mathbf{C}^{T}\mathbf{C}*\mathbf{A}^{T}\mathbf{A})-\mathbf{X}_{(2)}(\mathbf{C}\odot\mathbf{A})\right)\\ \operatorname{vec}\left(\mathbf{C}(\mathbf{B}^{T}\mathbf{B}*\mathbf{A}^{T}\mathbf{A})-\mathbf{X}_{(3)}(\mathbf{B}\odot\mathbf{A})\right) \end{bmatrix}.

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 ∂f∂A=0\frac{\partial f}{\partial\mathbf{A}}=0 for A\mathbf{A}, ∂f∂B=0\frac{\partial f}{\partial\mathbf{B}}=0 for B\mathbf{B}, and ∂f∂C=0\frac{\partial f}{\partial\mathbf{C}}=0 for C\mathbf{C}, 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 X(1)(C⊙B)\mathbf{X}_{(1)}(\mathbf{C}\odot\mathbf{B}), X(2)(C⊙A)\mathbf{X}_{(2)}(\mathbf{C}\odot\mathbf{A}), and X(3)(B⊙A)\mathbf{X}_{(3)}(\mathbf{B}\odot\mathbf{A}) are called Matricized-Tensor Times Khatri-Rao Products (MTTKRPs). The computational cost of evaluating the MTTKRPs in all modes is 4mnpr4mnpr plus lower order terms. The cost of evaluating the other expressions of the gradient are O((m+n+p)r2)O((m+n+p)r^2), 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 skGN\mathbf{s}^{GN}_{k} from vk\mathbf{v}_{k} by minimizing the first-order approximation mk(s)≡12∥r(vk)+J(vk)s∥2m_{k}(\mathbf{s})\equiv\frac{1}{2}\|\mathbf{r}(\mathbf{v}_{k})+\mathbf{J}(\mathbf{v}_{k})\mathbf{s}\|^2 to f(vk+s)f(\mathbf{v}_{k}+\mathbf{s}). The solution skGN\mathbf{s}^{GN}_{k} to this problem satisfies the Gauss-Newton linear system

JT(vk)J(vk)skGN=−JT(vk)r(vk)=−g(vk),(1)\mathbf{J}^{T}(\mathbf{v}_{k})\mathbf{J}(\mathbf{v}_{k})\mathbf{s}^{GN}_{k}=-\mathbf{J}^{T}(\mathbf{v}_{k})\mathbf{r}(\mathbf{v}_{k})=-\mathbf{g}(\mathbf{v}_{k}), \tag*{(1)}

but when nn is large, it is usual to approximate the solution using an iterative (normally, Krylov) method that requires repeated matrix-vector products JT(vk)J(vk)vˉ\mathbf{J}^{\mathsf{T}}(\mathbf{v}_k)\mathbf{J}(\mathbf{v}_k)\bar{\mathbf{v}} for a sequence of vectors vˉ\bar{\mathbf{v}}. 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 mkm_k along a piecewise linear path connecting the initial point vk\mathbf{v}_k to the Gauss-Newton point vk+skGN\mathbf{v}_k+\mathbf{s}_k^{GN} via the intermediary Cauchy point vk+skC\mathbf{v}_k+\mathbf{s}_k^C, where skC=arg⁡min⁡mk(−αg(vk))\mathbf{s}_k^C=\arg\min m_k(-\alpha\mathbf{g}(\mathbf{v}_k)), is sought within the trust-region {s:∥s∥≤Δk}\{\mathbf{s}:\lVert\mathbf{s}\rVert\le\Delta_k\} for a given radius Δk>0\Delta_k>0. The second, nls_gncgs, applies the conjugate-gradient method to generate approximations to the minimizer of mkm_k, 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 J(v)\mathbf{J}(\mathbf{v}) into three column blocks corresponding to the factor matrices. Then JT(v)J(v)\mathbf{J}^{\mathsf{T}}(\mathbf{v})\mathbf{J}(\mathbf{v}) has 3×33\times3 block matrix structure with blocks corresponding to pairs of factor matrices. Likewise, we partition the vector vˉ\bar{\mathbf{v}} to match the factor matrices:

vˉ=[vec⁡(Aˉ)vec⁡(Bˉ)vec⁡(Cˉ)].\bar{\mathbf{v}}= \begin{bmatrix} \operatorname{vec}(\bar{\mathbf{A}})\\ \operatorname{vec}(\bar{\mathbf{B}})\\ \operatorname{vec}(\bar{\mathbf{C}}) \end{bmatrix}.

We take advantage of the structure of J(v)\mathbf{J}(\mathbf{v}) to achieve efficient computation of JT(vk)J(vk)vˉ\mathbf{J}^{\mathsf{T}}(\mathbf{v}_k)\mathbf{J}(\mathbf{v}_k)\bar{\mathbf{v}}. As shown in [3, 31], the computations can be performed as follows:

JT(v)J(v)vˉ=[vec⁡(Aˉ(BTB∗CTC)+A(BˉTB∗CTC)+A(BTB∗CˉTC))vec⁡(B(AˉTA∗CTC)+Bˉ(ATA∗CTC)+B(ATA∗CˉTC))vec⁡(C(AˉTA∗BTB)+C(ATA∗BˉTB)+Cˉ(ATA∗BTB))].(2)\mathbf{J}^{\mathsf{T}}(\mathbf{v})\mathbf{J}(\mathbf{v})\bar{\mathbf{v}}= \begin{bmatrix} \operatorname{vec}\left(\bar{\mathbf{A}}(\mathbf{B}^{\mathsf{T}}\mathbf{B}*\mathbf{C}^{\mathsf{T}}\mathbf{C})+\mathbf{A}(\bar{\mathbf{B}}^{\mathsf{T}}\mathbf{B}*\mathbf{C}^{\mathsf{T}}\mathbf{C})+\mathbf{A}(\mathbf{B}^{\mathsf{T}}\mathbf{B}*\bar{\mathbf{C}}^{\mathsf{T}}\mathbf{C})\right)\\ \operatorname{vec}\left(\mathbf{B}(\bar{\mathbf{A}}^{\mathsf{T}}\mathbf{A}*\mathbf{C}^{\mathsf{T}}\mathbf{C})+\bar{\mathbf{B}}(\mathbf{A}^{\mathsf{T}}\mathbf{A}*\mathbf{C}^{\mathsf{T}}\mathbf{C})+\mathbf{B}(\mathbf{A}^{\mathsf{T}}\mathbf{A}*\bar{\mathbf{C}}^{\mathsf{T}}\mathbf{C})\right)\\ \operatorname{vec}\left(\mathbf{C}(\bar{\mathbf{A}}^{\mathsf{T}}\mathbf{A}*\mathbf{B}^{\mathsf{T}}\mathbf{B})+\mathbf{C}(\mathbf{A}^{\mathsf{T}}\mathbf{A}*\bar{\mathbf{B}}^{\mathsf{T}}\mathbf{B})+\bar{\mathbf{C}}(\mathbf{A}^{\mathsf{T}}\mathbf{A}*\mathbf{B}^{\mathsf{T}}\mathbf{B})\right) \end{bmatrix}. \tag*{(2)}

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 ATA\mathbf{A}^{\mathsf{T}}\mathbf{A}, BTB\mathbf{B}^{\mathsf{T}}\mathbf{B}, and CTC\mathbf{C}^{\mathsf{T}}\mathbf{C} are independent of vˉ\bar{\mathbf{v}}. 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 JT(v)J(v)\mathbf{J}^{\mathsf{T}}(\mathbf{v})\mathbf{J}(\mathbf{v}) is applied to a vector.

Complexity Analysis. The cost of applying JT(v)J(v)\mathbf{J}^{\mathsf{T}}(\mathbf{v})\mathbf{J}(\mathbf{v}) to a vector is small compared to computing the gradient. Evaluating eq. (2) costs O((m+n+p)r2)O((m+n+p)r^2), while the gradient computation is O(mnpr)O(mnpr) 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 sk\mathbf{s}_k is not excessive, the cost of a Gauss-Newton iteration is roughly that of evaluating the gradient. Note that the precomputation of ATA\mathbf{A}^{\mathsf{T}}\mathbf{A}, BTB\mathbf{B}^{\mathsf{T}}\mathbf{B}, and CTC\mathbf{C}^{\mathsf{T}}\mathbf{C} 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

min⁡v∈Rr(m+n+p)f(v)≡12∥r(v)∥2\min_{v\in\mathbb{R}^{r(m+n+p)}} f(v) \equiv\frac{1}{2}\lVert r(v)\rVert^2

in the special case where the unknowns are organized as v=v =

[vec⁡(A)vec⁡(B)vec⁡(C)]\begin{bmatrix} \operatorname{vec}(A) \\ \operatorname{vec}(B) \\ \operatorname{vec}(C) \end{bmatrix}

and the mnpmnp residuals are given by r(v)=vec⁡(⟦A,B,C⟧−X)r(v) = \operatorname{vec}(\llbracket A,B,C\rrbracket- X). In this section, we focus on this general problem involving f(v)f(v), and in particular on methods that are guaranteed (at worst) to find a stationary point of ff 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

g(v)≡JT(v)r(v)g(v) \equiv J^{\mathsf{T}}(v)r(v)

and often the Hessian

H(v)≡JT(v)J(v)+∑i=1mri(v)Hi(v)H(v) \equiv J^{\mathsf{T}}(v)J(v) + \sum_{i=1}^{m} r_i(v)H_i(v)

of f(v)f(v), or a suitable approximation of the latter; here J(v)J(v) is the Jacobian of r(v)r(v), that is the matrix whose ii-th row is the transpose of the gradient, gi(v)g_i(v), of the ii-th component, ri(v)r_i(v), of r(v)r(v), and Hi(v)H_i(v) is the Hessian of ri(v)r_i(v). 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 vkv_k to a better one by stepping along an ff-improving line (or arc) based on g(vk)g(v_k) and sometimes H(vk)H(v_k). The others model f(v)f(v) around vkv_k by building a suitable approximation mk(s)m_k(s) of f(vk+s)f(v_k+s) using g(vk)g(v_k) and sometimes H(vk)H(v_k), pick a step sks_k from vkv_k to reduce mk(s)m_k(s), and then assess whether f(vk+sk)f(v_k+s_k) is suitably smaller than f(vk)f(v_k).

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 f(vk+s)f(v_k+s) is replaced by the model

m1,k(s)=12∥r(vk)+J(vk)s∥2+12λk∥s∥2m_{1,k}(s) = \frac{1}{2}\lVert r(v_k)+J(v_k)s\rVert^2 + \frac{1}{2}\lambda_k\lVert s\rVert^2

for which r(vk)+J(vk)sr(v_k)+J(v_k)s is the first-order Taylor approximation of r(vk+s)r(v_k+s), and λk>0\lambda_k>0 is an evolving regularization weight that implicitly controls the length of the step ss. The step sks_k is then chosen to be any ss for which m1,k(sk)≤m1,k(skC)m_{1,k}(s_k) \le m_{1,k}(s_k^{\mathrm{C}}), where the Cauchy point skC=arg⁡min⁡m1,k(−αg(vk))s_k^{\mathrm{C}} = \arg\min m_{1,k}(-\alpha g(v_k)) gives the smallest value of m1,k(s)m_{1,k}(s) in the steepest descent direction, −αg(vk)-\alpha g(v_k). In particular, sks_k might be chosen as the minimizer sk,⋆s_{k,\star} of m1,k(s)m_{1,k}(s), for which

(JT(vk)J(vk)+λkI)sk,⋆=−JT(vk)r(vk).\left(\mathbf{J}^{\mathsf{T}}(v_k)\mathbf{J}(v_k)+\lambda_k I\right)s_{k,\star}=-\mathbf{J}^{\mathsf{T}}(v_k)r(v_k).

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 sks_k, the ratio

ρk=f(vk)−f(vk+sk)m1,k(0)−m1,k(sk)(3)\rho_k=\frac{f(v_k)-f(v_k+s_k)}{m_{1,k}(0)-m_{1,k}(s_k)} \tag*{(3)}

of the actual to (model) predicted decrease is computed, and so long as this is adequate (say ρk≥0.75\rho_k\geq0.75), the correction vk+skv_k+s_k becomes the new vk+1v_{k+1} and λk\lambda_k may be decreased. By contrast, if the decrease is inadequate, vk+1v_{k+1} stays at vkv_k, but now λk\lambda_k is increased; the impact of this is to ensure that the next step will be smaller than the current one, and thus mk+1(s)m_{k+1}(s) resembles f(vk+s)f(v_k+s) better, and ultimately progress will be made. Although it is possible to use matrix factorization to find the minimizer of m1,k(s)m_{1,k}(s), this is likely costly in our case, and instead we use a Krylov method (GLRT) [8 Chap. 9 & 10], that simply involves JT(v)J(v)vˉ\mathbf{J}^{\mathsf{T}}(v)\mathbf{J}(v)\bar{v} products, to do so.

When the optimal residuals r(v∗)r(v_\ast) 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

m2,k(s)=f(vk)+gT(vk)s+12sTH(vk)s+13λk∥s∥3(4)m_{2,k}(s)=f(v_k)+\mathbf{g}^{\mathsf{T}}(v_k)s+\frac{1}{2}s^{\mathsf{T}}\mathbf{H}(v_k)s+\frac{1}{3}\lambda_k\lVert s\rVert^3 \tag*{(4)}

that includes the K(vk)\mathbf{K}(v_k) 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 sks_k of m2,k(s)m_{2,k}(s) that is at least as good as that at the Cauchy point skC=arg⁡min⁡m2,k(−αg(vk))s_k^C=\arg\min m_{2,k}(-\alpha g(v_k)), we accept and reject steps and adjust λk\lambda_k based on the equivalent of (3) involving m2,km_{2,k}, and we can find sks_k 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 ∥a^∥=∥b^∥=∥c^∥\lVert\hat{\mathbf{a}}\rVert=\lVert\hat{\mathbf{b}}\rVert=\lVert\hat{\mathbf{c}}\rVert. That is, given a,b,c\mathbf{a},\mathbf{b},\mathbf{c}, we equilibrate them via

a←σa∥a∥,b←σb∥b∥andc←σc∥c∥,whereσ=∥a∥∥b∥∥c∥3,(5)\mathbf{a}\leftarrow\sigma\frac{\mathbf{a}}{\lVert\mathbf{a}\rVert},\quad \mathbf{b}\leftarrow\sigma\frac{\mathbf{b}}{\lVert\mathbf{b}\rVert} \quad\text{and}\quad \mathbf{c}\leftarrow\sigma\frac{\mathbf{c}}{\lVert\mathbf{c}\rVert}, \qquad\text{where}\quad \sigma=\sqrt[3]{\lVert\mathbf{a}\rVert\lVert\mathbf{b}\rVert\lVert\mathbf{c}\rVert}, \tag*{(5)}

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 A\mathbf{A}, B\mathbf{B} and C\mathbf{C} 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 X≈[A,B,C]∈Rm×n×p\mathcal{X} \approx[\mathbf{A},\mathbf{B},\mathbf{C}] \in\mathbb{R}^{m \times n \times p} such that A∈Rm×r\mathbf{A} \in\mathbb{R}^{m \times r}, B∈Rn×r\mathbf{B} \in\mathbb{R}^{n \times r}, and C∈Rp×r\mathbf{C} \in\mathbb{R}^{p \times r}. We use the indices ii, jj, kk, and ℓ\ell for mm, nn, pp, and rr, 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

H(v)≡JT(v)J(v)+K(v),whereK(v)=∑i,j,krijk(v)∇2rijk(v)andv=[vec⁡(A)vec⁡(B)vec⁡(C)].\mathbf{H}(\mathbf{v}) \equiv\mathbf{J}^{\mathsf{T}}(\mathbf{v})\mathbf{J}(\mathbf{v}) + \mathbf{K}(\mathbf{v}), \qquad\text{where} \qquad\mathbf{K}(\mathbf{v}) = \sum_{i,j,k} r_{ijk}(\mathbf{v}) \nabla^{2}r_{ijk}(\mathbf{v}) \qquad\text{and} \qquad\mathbf{v} = \begin{bmatrix} \operatorname{vec}(\mathbf{A}) \\ \operatorname{vec}(\mathbf{B}) \\ \operatorname{vec}(\mathbf{C}) \end{bmatrix}.

As the structure of JT(v)J(v)\mathbf{J}^{\mathsf{T}(\mathbf{v})\mathbf{J}(\mathbf{v})} and efficient means of applying it to a vector are described in § 2.5, we focus now on K(v)\mathbf{K}(\mathbf{v}). Here R=[A,B,C]−X\mathcal{R} = [\mathbf{A},\mathbf{B},\mathbf{C}] - \mathcal{X} is the residual tensor and Hijk(v)H_{ijk}(\mathbf{v}) is the Hessian of the scalar-valued function rijk(v)r_{ijk}(\mathbf{v}), an element of R\mathcal{R}.

Similar to the structure of JT(v)J(v)\mathbf{J}^{\mathsf{T}}(\mathbf{v})\mathbf{J}(\mathbf{v}), we consider K\mathbf{K} (dropping the dependence on v\mathbf{v} for ease of notation) to be a symmetric 3×33 \times3 block matrix based on the mixed partials with respect to each pair of factor matrices:

K=[KAAKABKACKABTKBBKBCKACTKBCTKCC],where, for example,KAB=∑i,j,krijk∂2rijk∂vec⁡(B)∂vec⁡(A).(6)\mathbf{K} = \begin{bmatrix} \mathbf{K}_{AA} & \mathbf{K}_{AB} & \mathbf{K}_{AC} \\ \mathbf{K}_{AB}^{\mathsf{T}} & \mathbf{K}_{BB} & \mathbf{K}_{BC} \\ \mathbf{K}_{AC}^{\mathsf{T}} & \mathbf{K}_{BC}^{\mathsf{T}} & \mathbf{K}_{CC} \end{bmatrix}, \qquad\text{where, for example,} \qquad\mathbf{K}_{AB} = \sum_{i,j,k} r_{ijk}\frac{\partial^{2}r_{ijk}}{\partial\operatorname{vec}(\mathbf{B})\partial\operatorname{vec}(\mathbf{A})}. \tag*{(6)}

Note that rijk(v)=∑ℓ=1raiℓbjℓckℓ−xijkr_{ijk}(\mathbf{v}) = \sum_{\ell=1}^{r} a_{i\ell}b_{j\ell}c_{k\ell} - x_{ijk}, 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 00, or equivalently, KAA=0\mathbf{K}_{AA} = 0, KBB=0\mathbf{K}_{BB} = 0, and KCC=0\mathbf{K}_{CC} = 0. We now derive expressions for the three off-diagonal blocks. A visualization of the sparsity structure of K\mathbf{K} is given in Figure 1.

Figure 1. Diagram of K’s structure in the case that the input is an m×n×pm \times n \times p tensor and r=5r = 5.

Lemma 2. The off-diagonal blocks of the matrix K\mathbf{K} as defined in eq. (6) are given by

KAB=blkdiag⁡3(R×3CT)\mathbf{K}_{AB} = \operatorname{blkdiag}_{3}(\mathcal{R} \times_{3} \mathbf{C}^{\mathsf{T}})
KAC=blkdiag⁡2(R×2BT)\mathbf{K}_{AC} = \operatorname{blkdiag}_{2}(\mathcal{R} \times_{2} \mathbf{B}^{\mathsf{T}})
KBC=blkdiag⁡1(R×1AT)\mathbf{K}_{BC} = \operatorname{blkdiag}_{1}(\mathcal{R} \times_{1} \mathbf{A}^{\mathsf{T}})

with blkdiag⁡k(⋅)\operatorname{blkdiag}_{k}(\cdot) given by Def. 8 and R=[A,B,C]−X\mathcal{R} = [\mathbf{A},\mathbf{B},\mathbf{C}] - \mathcal{X}.

Proof. By definition, KAB=∑ijkrijk∂2rijk∂vec⁡(B)∂vec⁡(A)\mathbf{K}_{AB} = \sum_{ijk} r_{ijk}\frac{\partial^{2}r_{ijk}}{\partial\operatorname{vec}(\mathbf{B})\partial\operatorname{vec}(\mathbf{A})}. 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 rijkr_{ijk} with respect to vec⁡(A)\operatorname{vec}(\mathbf{A}). Let Eijk\mathcal{E}_{ijk} be the 3-way indicator tensor, which is Ei,L(j,k)\mathbf{E}_{i,\mathcal{L}(j,k)} when unfolded on the first mode. The Jacobian of r\mathbf{r} is given in Lem. 1, and in particular, ∂r∂vec⁡(A)=(C⊙B)⊗Im\frac{\partial\mathbf{r}}{\partial\operatorname{vec}(\mathbf{A})} = (\mathbf{C} \odot\mathbf{B}) \otimes\mathbf{I}_{m}. Thus, we can find the gradient of rijkr_{ijk} (with respect to vec⁡(A)\operatorname{vec}(\mathbf{A})) by selecting and transposing the corresponding row of the Jacobian of r\mathbf{r} (with respect to vec⁡(A)\operatorname{vec}(\mathbf{A})):

∂rijk∂vec⁡(A)=(vec⁡(Eijk)T[(C⊙B)⊗Im])T=[(C⊙B)T⊗Im]vec⁡(Ei,L(j,k))Unfold Eijk on the first mode=(Ir⊗Ei,L(j,k))vec⁡(C⊙B)Cor. 1.\begin{aligned} \frac{\partial r_{ijk}}{\partial\operatorname{vec}(\mathbf{A})} = \left(\operatorname{vec}(\mathcal{E}_{ijk})^{\mathsf{T}} [(\mathbf{C} \odot\mathbf{B}) \otimes\mathbf{I}_{m}]\right)^{\mathsf{T}} \\ &= [(\mathbf{C} \odot\mathbf{B})^{\mathsf{T}} \otimes\mathbf{I}_{m}] \operatorname{vec}(\mathbf{E}_{i,\mathcal{L}(j,k)}) \qquad\text{Unfold } \mathcal{E}_{ijk} \text{ on the first mode} \\ &= (\mathbf{I}_{r} \otimes\mathbf{E}_{i,\mathcal{L}(j,k)}) \operatorname{vec}(\mathbf{C} \odot\mathbf{B}) \qquad\textit{Cor. 1.} \end{aligned}

Next, we differentiate with respect to vec⁡(B)\operatorname{vec}(\mathbf{B}). Since Ir⊗Ei,L(j,k)I_r \otimes E_{i,L(j,k)} does not depend on B\mathbf{B}, we differentiate vec⁡(C⊙B)\operatorname{vec}(\mathbf{C} \odot\mathbf{B}) with respect to vec⁡(B)\operatorname{vec}(\mathbf{B}) and multiply back. By definition, the ℓ\ell-th column of C⊙B\mathbf{C} \odot\mathbf{B} is cℓ⊗bℓ\mathbf{c}_{\ell} \otimes\mathbf{b}_{\ell}, so

vec⁡(C⊙B)=∑ℓ=1reℓ⊗cℓ⊗bℓ=∑ℓ=1r(eℓ⊗cℓ⊗In)bℓProp. 2=∑ℓ=1r(eℓ⊗cℓ⊗In)Beℓ=∑ℓ=1r(eℓ⊗cℓ⊗In)(eℓT⊗In)vec⁡(B)Cor. 1.\begin{aligned} \operatorname{vec}(\mathbf{C} \odot\mathbf{B}) = \sum_{\ell=1}^{r} \mathbf{e}_{\ell} \otimes\mathbf{c}_{\ell} \otimes\mathbf{b}_{\ell} = \sum_{\ell=1}^{r} (\mathbf{e}_{\ell} \otimes\mathbf{c}_{\ell} \otimes I_n)\mathbf{b}_{\ell} \qquad\text{Prop. 2} \\ &= \sum_{\ell=1}^{r} (\mathbf{e}_{\ell} \otimes\mathbf{c}_{\ell} \otimes I_n)\mathbf{B}\mathbf{e}_{\ell} = \sum_{\ell=1}^{r} (\mathbf{e}_{\ell} \otimes\mathbf{c}_{\ell} \otimes I_n)(\mathbf{e}_{\ell}^{\mathsf{T}} \otimes I_n)\operatorname{vec}(\mathbf{B}) \qquad\text{Cor. 1.} \end{aligned}

Thus,

∂vec⁡(C⊙B)∂vec⁡(B)=∑ℓ=1r(eℓ⊗cℓ⊗In)(eℓT⊗In),\frac{\partial\operatorname{vec}(\mathbf{C} \odot\mathbf{B})}{\partial\operatorname{vec}(\mathbf{B})} = \sum_{\ell=1}^{r}(\mathbf{e}_{\ell} \otimes\mathbf{c}_{\ell} \otimes I_n)(\mathbf{e}_{\ell}^{\mathsf{T}} \otimes I_n),

and therefore

∂2rijk∂vec⁡(B) ∂vec⁡(A)=(Ir⊗Ei,L(j,k))∑ℓ=1r(eℓ⊗cℓ⊗In)(eℓT⊗In).\frac{\partial^{2}r_{ijk}}{\partial\operatorname{vec}(\mathbf{B})\,\partial\operatorname{vec}(\mathbf{A})} = (I_r \otimes E_{i,L(j,k)})\sum_{\ell=1}^{r}(\mathbf{e}_{\ell} \otimes\mathbf{c}_{\ell} \otimes I_n)(\mathbf{e}_{\ell}^{\mathsf{T}} \otimes I_n).

We simplify the product (Ir⊗Ei,L(j,k))(eℓ⊗cℓ⊗In)(I_r \otimes E_{i,L(j,k)})(\mathbf{e}_{\ell} \otimes\mathbf{c}_{\ell} \otimes I_n) using Prop. 2:

[Ir⊗Ei,L(j,k)](eℓ⊗(cℓ⊗In))=eℓ⊗[Ei,L(j,k)(cℓ⊗In)].[I_r \otimes E_{i,L(j,k)}](\mathbf{e}_{\ell} \otimes(\mathbf{c}_{\ell} \otimes I_n)) = \mathbf{e}_{\ell} \otimes[E_{i,L(j,k)}(\mathbf{c}_{\ell} \otimes I_n)].

To evaluate the right factor, recall Ei,L(j,k)=ei(ek⊗ej)T\mathbf{E}_{i,\mathcal{L}(j,k)}=\mathbf{e}_i(\mathbf{e}_k\otimes\mathbf{e}_j)^{\mathsf{T}} and apply Prop. 2:

Ei,L(j,k)(Cℓ⊗In)=ei(ekTCℓ⊗ejT)=ckℓEij.\mathbf{E}_{i,\mathcal{L}(j,k)}(\mathbf{C}_{\ell}\otimes\mathbf{I}_n)=\mathbf{e}_i(\mathbf{e}_k^{\mathsf{T}}\mathbf{C}_{\ell}\otimes\mathbf{e}_j^{\mathsf{T}})=c_{k\ell}\mathbf{E}_{ij}.

Substituting back and applying Prop. 2 once more:

∂2rijk∂vec⁡(B)∂vec⁡(A)=∑ℓ=1r(eℓ⊗ckℓEij)(eℓT⊗In)=∑ℓ=1reℓeℓT⊗(ckℓEij).\frac{\partial^2r_{ijk}}{\partial\operatorname{vec}(\mathbf{B})\partial\operatorname{vec}(\mathbf{A})}=\sum_{\ell=1}^{r}(\mathbf{e}_{\ell}\otimes c_{k\ell}\mathbf{E}_{ij})(\mathbf{e}_{\ell}^{\mathsf{T}}\otimes\mathbf{I}_n)=\sum_{\ell=1}^{r}\mathbf{e}_{\ell}\mathbf{e}_{\ell}^{\mathsf{T}}\otimes(c_{k\ell}\mathbf{E}_{ij}).

Multiplying by rijkr_{ijk}, summing over (i,j,k)(i,j,k), and exchanging the order of summation, we have

KAB=∑ℓ=1reℓeℓT⊗∑ijkrijkckℓEij=∑ℓ=1rEℓℓ⊗(R×3cℓT)=blkdiag⁡3(R×3CT)Def. 8.\begin{aligned} \mathbf{K}_{AB}=\sum_{\ell=1}^{r}\mathbf{e}_{\ell}\mathbf{e}_{\ell}^{\mathsf{T}}\otimes\sum_{ijk}r_{ijk}c_{k\ell}\mathbf{E}_{ij} \\ &=\sum_{\ell=1}^{r}\mathbf{E}_{\ell\ell}\otimes(\mathcal{R}\times_3\mathbf{c}_{\ell}^{\mathsf{T}}) \\ &=\operatorname{blkdiag}_3(\mathcal{R}\times_3\mathbf{C}^{\mathsf{T}})\qquad\textit{Def. 8.} \end{aligned}

The derivations of KAC\mathbf{K}_{AC} and KBC\mathbf{K}_{BC} are analogous.

Efficiently Applying the Hessian to a Vector

To apply the Hessian H(v)\mathbf{H}(\mathbf{v}) to a vector vˉ\bar{\mathbf{v}}, we separately compute JT(v)J(v)vˉ\mathbf{J}^{\mathsf{T}}(\mathbf{v})\mathbf{J}(\mathbf{v})\bar{\mathbf{v}} (as described in Sec. 2.5) and K(v)vˉ\mathbf{K}(\mathbf{v})\bar{\mathbf{v}}. As before, we will break the vector vˉ\bar{\mathbf{v}} into three components which correspond to the three factor matrices, and we drop the dependence on v\mathbf{v} to ease notation. We have

Kvˉ=[0KABKACKABT0KBCKACTKBCT0][vec⁡(Aˉ)vec⁡(Bˉ)vec⁡(Cˉ)]=[KABvec⁡(Bˉ)+KACvec⁡(Cˉ)KABTvec⁡(Aˉ)+KBCvec⁡(Cˉ)KACTvec⁡(Aˉ)+KBCTvec⁡(Bˉ)].(7)\mathbf{K}\bar{\mathbf{v}}= \begin{bmatrix} \mathbf{0} & \mathbf{K}_{AB} & \mathbf{K}_{AC}\\ \mathbf{K}_{AB}^{\mathsf{T}} & \mathbf{0} & \mathbf{K}_{BC}\\ \mathbf{K}_{AC}^{\mathsf{T}} & \mathbf{K}_{BC}^{\mathsf{T}} & \mathbf{0} \end{bmatrix} \begin{bmatrix} \operatorname{vec}(\bar{\mathbf{A}})\\ \operatorname{vec}(\bar{\mathbf{B}})\\ \operatorname{vec}(\bar{\mathbf{C}}) \end{bmatrix} = \begin{bmatrix} \mathbf{K}_{AB}\operatorname{vec}(\bar{\mathbf{B}})+\mathbf{K}_{AC}\operatorname{vec}(\bar{\mathbf{C}})\\ \mathbf{K}_{AB}^{\mathsf{T}}\operatorname{vec}(\bar{\mathbf{A}})+\mathbf{K}_{BC}\operatorname{vec}(\bar{\mathbf{C}})\\ \mathbf{K}_{AC}^{\mathsf{T}}\operatorname{vec}(\bar{\mathbf{A}})+\mathbf{K}_{BC}^{\mathsf{T}}\operatorname{vec}(\bar{\mathbf{B}}) \end{bmatrix}. \tag*{(7)}

The following lemma illustrates that the structure of these computations is similar to the gradient, but with mixed contributions from the CP model vector v\mathbf{v} and the arbitrary vector vˉ\bar{\mathbf{v}}.

Lemma 3. The components of Kvˉ\mathbf{K}\bar{\mathbf{v}} from eq. (7) can be computed as follows:

KABvec⁡(Bˉ)=vec⁡(R(1)(C∘Bˉ))=vec⁡(A(CTC∗BTBˉ)−X(1)(C∘Bˉ))\mathbf{K}_{AB}\operatorname{vec}(\bar{\mathbf{B}})=\operatorname{vec}(\mathbf{R}_{(1)}(\mathbf{C}\circ\bar{\mathbf{B}}))=\operatorname{vec}(\mathbf{A}(\mathbf{C}^{\mathsf{T}}\mathbf{C}*\mathbf{B}^{\mathsf{T}}\bar{\mathbf{B}})-\mathbf{X}_{(1)}(\mathbf{C}\circ\bar{\mathbf{B}}))
KACvec⁡(Cˉ)=vec⁡(R(1)(Cˉ∘B))=vec⁡(A(CTCˉ∗BTB)−X(1)(Cˉ∘B))\mathbf{K}_{AC}\operatorname{vec}(\bar{\mathbf{C}})=\operatorname{vec}(\mathbf{R}_{(1)}(\bar{\mathbf{C}}\circ\mathbf{B}))=\operatorname{vec}(\mathbf{A}(\mathbf{C}^{\mathsf{T}}\bar{\mathbf{C}}*\mathbf{B}^{\mathsf{T}}\mathbf{B})-\mathbf{X}_{(1)}(\bar{\mathbf{C}}\circ\mathbf{B}))
KBCvec⁡(Cˉ)=vec⁡(R(2)(Cˉ∘A))=vec⁡(B(CTCˉ∗ATA)−X(2)(Cˉ∘A))\mathbf{K}_{BC}\operatorname{vec}(\bar{\mathbf{C}})=\operatorname{vec}(\mathbf{R}_{(2)}(\bar{\mathbf{C}}\circ\mathbf{A}))=\operatorname{vec}(\mathbf{B}(\mathbf{C}^{\mathsf{T}}\bar{\mathbf{C}}*\mathbf{A}^{\mathsf{T}}\mathbf{A})-\mathbf{X}_{(2)}(\bar{\mathbf{C}}\circ\mathbf{A}))
KABTvec⁡(Aˉ)=vec⁡(R(2)(C∘Aˉ))=vec⁡(B(CTC∗ATAˉ)−X(2)(C∘Aˉ))\mathbf{K}_{AB}^{\mathsf{T}}\operatorname{vec}(\bar{\mathbf{A}})=\operatorname{vec}(\mathbf{R}_{(2)}(\mathbf{C}\circ\bar{\mathbf{A}}))=\operatorname{vec}(\mathbf{B}(\mathbf{C}^{\mathsf{T}}\mathbf{C}*\mathbf{A}^{\mathsf{T}}\bar{\mathbf{A}})-\mathbf{X}_{(2)}(\mathbf{C}\circ\bar{\mathbf{A}}))
KACTvec⁡(Aˉ)=vec⁡(R(3)(B∘Aˉ))=vec⁡(C(BTB∗ATAˉ)−X(3)(B∘Aˉ))\mathbf{K}_{AC}^{\mathsf{T}}\operatorname{vec}(\bar{\mathbf{A}})=\operatorname{vec}(\mathbf{R}_{(3)}(\mathbf{B}\circ\bar{\mathbf{A}}))=\operatorname{vec}(\mathbf{C}(\mathbf{B}^{\mathsf{T}}\mathbf{B}*\mathbf{A}^{\mathsf{T}}\bar{\mathbf{A}})-\mathbf{X}_{(3)}(\mathbf{B}\circ\bar{\mathbf{A}}))
KBCTvec⁡(Bˉ)=vec⁡(R(3)(Bˉ∘A))=vec⁡(C(BTBˉ∗ATA)−X(3)(Bˉ∘A))\mathbf{K}_{BC}^{\mathsf{T}}\operatorname{vec}(\bar{\mathbf{B}})=\operatorname{vec}(\mathbf{R}_{(3)}(\bar{\mathbf{B}}\circ\mathbf{A}))=\operatorname{vec}(\mathbf{C}(\mathbf{B}^{\mathsf{T}}\bar{\mathbf{B}}*\mathbf{A}^{\mathsf{T}}\mathbf{A})-\mathbf{X}_{(3)}(\bar{\mathbf{B}}\circ\mathbf{A}))

Proof. We detail the derivation only for KABvec⁡(Bˉ)=blkdiag⁡3(R×3CT)vec⁡(Bˉ)\mathbf{K}_{AB}\operatorname{vec}(\bar{\mathbf{B}})=\operatorname{blkdiag}_3(\mathcal{R}\times_3\mathbf{C}^{\mathsf{T}})\operatorname{vec}(\bar{\mathbf{B}}), as the other cases are derived similarly. Note that by the definition of the mode-3 product (see Def. 7), the ℓ\ellth frontal slice of R×3CT\mathcal{R} \times_{3} \mathcal{C}^{\mathsf{T}} is R×3cℓT=R(1)(cℓ⊗In)\mathcal{R} \times_{3} \mathbf{c}_{\ell}^{\mathsf{T}} = \mathbf{R}_{(1)}(\mathbf{c}_{\ell} \otimes\mathbf{I}_{n}). Then

blkdiag⁡3(R×3CT)vec⁡(B‾)=[∑ℓ=1rEℓℓ⊗(R×3cℓT)]vec⁡(B‾)=∑ℓ=1rvec⁡((R×3cℓT)B‾eℓeℓT)Prop. 1=∑ℓ=1rvec⁡(R(1)(cℓ⊗In)b‾ℓeℓT)=∑ℓ=1rvec⁡(R(1)(cℓ⊗b‾ℓ)eℓT)Prop. 2=∑ℓ=1rvec⁡(R(1)(C⊙B‾)eℓeℓT)Def. 5=vec⁡(R(1)(C⊙B‾))because ∑ℓ=1reℓeℓT=Ir.\begin{aligned} \operatorname{blkdiag}_{3}(\mathcal{R}\times_{3}\mathbf{C}^{\mathsf{T}})\operatorname{vec}(\overline{\mathbf{B}}) &=\left[\sum_{\ell=1}^{r}\mathbf{E}_{\ell\ell}\otimes(\mathcal{R}\times_{3}\mathbf{c}_{\ell}^{\mathsf{T}})\right]\operatorname{vec}(\overline{\mathbf{B}})\\ &=\sum_{\ell=1}^{r}\operatorname{vec}\left((\mathcal{R}\times_{3}\mathbf{c}_{\ell}^{\mathsf{T}})\overline{\mathbf{B}}\mathbf{e}_{\ell}\mathbf{e}_{\ell}^{\mathsf{T}}\right)\qquad\text{Prop. 1}\\ &=\sum_{\ell=1}^{r}\operatorname{vec}\left(\mathbf{R}_{(1)}(\mathbf{c}_{\ell}\otimes\mathbf{I}_{n})\overline{\mathbf{b}}_{\ell}\mathbf{e}_{\ell}^{\mathsf{T}}\right)\\ &=\sum_{\ell=1}^{r}\operatorname{vec}\left(\mathbf{R}_{(1)}(\mathbf{c}_{\ell}\otimes\overline{\mathbf{b}}_{\ell})\mathbf{e}_{\ell}^{\mathsf{T}}\right)\qquad\text{Prop. 2}\\ &=\sum_{\ell=1}^{r}\operatorname{vec}\left(\mathbf{R}_{(1)}(\mathbf{C}\odot\overline{\mathbf{B}})\mathbf{e}_{\ell}\mathbf{e}_{\ell}^{\mathsf{T}}\right)\qquad\text{Def. 5}\\ &=\operatorname{vec}\left(\mathbf{R}_{(1)}(\mathbf{C}\odot\overline{\mathbf{B}})\right)\qquad\text{because }\sum_{\ell=1}^{r}\mathbf{e}_{\ell}\mathbf{e}_{\ell}^{\mathsf{T}}=\mathbf{I}_{r}. \end{aligned}

As R(1)=A(C⊙B)T−X(1)\mathbf{R}_{(1)}=\mathbf{A}(\mathbf{C}\odot\mathbf{B})^{\mathsf{T}}-\mathbf{X}_{(1)},

R(1)(C⊙B‾)=A(CTC∗BTB‾)−X(1)(C⊙B‾)\mathbf{R}_{(1)}(\mathbf{C}\odot\overline{\mathbf{B}})=\mathbf{A}(\mathbf{C}^{\mathsf{T}}\mathbf{C}*\mathbf{B}^{\mathsf{T}}\overline{\mathbf{B}})-\mathbf{X}_{(1)}(\mathbf{C}\odot\overline{\mathbf{B}})

follows from Prop. 3.

Note the similarities of these expressions to the CP gradient given by Lem. 1. In particular, unlike the computation of JTJv‾\mathbf{J}^{\mathsf{T}}\mathbf{J}\overline{\mathbf{v}} in eq. (2), Kv‾\mathbf{K}\overline{\mathbf{v}} involves the data tensor X\mathcal{X} in the form of MTTKRPs. Evaluating these MTTKRPs directly would make every iteration of an iterative solve for sk\mathbf{s}_{k} 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 v\mathbf{v} (the fixed Newton iterate) and one factor matrix from v‾\overline{\mathbf{v}} (the arbitrary vector that varies over iterations). For example, KABvec(A‾)\mathbf{K}_{AB}^{\mathsf{vec}}(\overline{\mathbf{A}}) involves the MTTKRP M=X(2)(C⊙A‾)\mathbf{M}=\mathbf{X}_{(2)}(\mathbf{C}\odot\overline{\mathbf{A}}). As described in [3 Sec. 3.5.1], we can compute the MTTKRP using the following two steps: (1) YAB=X×3CT\mathcal{Y}_{AB}=\mathcal{X}\times_{3}\mathbf{C}^{\mathsf{T}} and (2) vec⁡(M)=blkdiag⁡3(YAB)Tvec⁡(A‾)\operatorname{vec}(\mathbf{M})=\operatorname{blkdiag}_{3}(\mathcal{Y}_{AB})^{\mathsf{T}}\operatorname{vec}(\overline{\mathbf{A}}), which is computed as batched matrix-vector products. In fact, the six terms can all be computed from three precomputations involving X\mathcal{X} and v\mathbf{v}: YBC=X×1AT\mathcal{Y}_{BC}=\mathcal{X}\times_{1}\mathbf{A}^{\mathsf{T}}, YAC=X×2BT\mathcal{Y}_{AC}=\mathcal{X}\times_{2}\mathbf{B}^{\mathsf{T}}, and YAB=X×3CT\mathcal{Y}_{AB}=\mathcal{X}\times_{3}\mathbf{C}^{\mathsf{T}}. Because of the overlap, we can also use these intermediate quantities (as well as ATA\mathbf{A}^{\mathsf{T}}\mathbf{A}, BTB\mathbf{B}^{\mathsf{T}}\mathbf{B}, and CTC\mathbf{C}^{\mathsf{T}}\mathbf{C}) to evaluate the gradient.

Complexity Analysis. The cost of applying H(v)\mathbf{H}(\mathbf{v}) 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 6mnpr6mnpr 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 JT(v)J(v)\mathbf{J}^{\mathsf{T}}(\mathbf{v})\mathbf{J}(\mathbf{v}) and completing the application of K(v)\mathbf{K}(\mathbf{v}). The cost of applying JT(v)J(v)\mathbf{J}^{\mathsf{T}}(\mathbf{v})\mathbf{J}(\mathbf{v}) is O((m+n+p)r2)O((m+n+p)r^2) (see § 2.5). The six batched matrix-vector products to complete the application of K(v)\mathbf{K}(\mathbf{v}) have cost O((mn+np+mp)r)O((mn+np+mp)r), and the other operations cost O((m+n+p)r2)O((m+n+p)r^2). Therefore, assuming rr 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 vk\mathbf{v}_k, and the inner iteration corresponds to a step of the Krylov method GLRT used to compute the update sk\mathbf{s}_k. 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 sk\mathbf{s}_k. The latter involves multiple iterations of the GLRT algorithm, whose cost is dominated by applying the K\mathbf{K} 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

  1. function {Y}=Precompute⁡(X,v)\{\mathcal{Y}\} = \operatorname{Precompute}(\mathcal{X},\mathbf{v})

  2. Unpack v\mathbf{v} into A,B,C\mathbf{A},\mathbf{B},\mathbf{C}

  3. SA←ATA,SB←BTB,SC←CTC\mathbf{S}_A \leftarrow\mathbf{A}^{\mathsf{T}}\mathbf{A},\quad\mathbf{S}_B \leftarrow\mathbf{B}^{\mathsf{T}}\mathbf{B},\quad\mathbf{S}_C \leftarrow\mathbf{C}^{\mathsf{T}}\mathbf{C}

  4. YAB←X×3CT\mathcal{Y}_{AB} \leftarrow\mathcal{X} \times_3 \mathbf{C}^{\mathsf{T}}

  5. YAC←X×2BT\mathcal{Y}_{AC} \leftarrow\mathcal{X} \times_2 \mathbf{B}^{\mathsf{T}}

  6. YBC←X×1AT\mathcal{Y}_{BC} \leftarrow\mathcal{X} \times_1 \mathbf{A}^{\mathsf{T}}

  7. return {YAB,YAC,YBC},{SA,SB,SC}\{\mathcal{Y}_{AB},\mathcal{Y}_{AC},\mathcal{Y}_{BC}\},\{\mathbf{S}_A,\mathbf{S}_B,\mathbf{S}_C\}

  8. end function

For the gradient computation, each MTTKRP is completed by one batched matrix-vector product involving a TTM intermediate from {Y}\{\mathcal{Y}\} that has all modes except two contracted (see Alg. 2). To apply K\mathbf{K}, for each nonzero block we apply one input-vector factor matrix to an intermediate from {Y}\{\mathcal{Y}\} as shown in § 3.3. The pseudocode is given in Alg. 3. Therefore, by precomputing the {Y}\{\mathcal{Y}\} intermediates once per Newton step, we avoid redundant computation across the gradient and all K\mathbf{K} applications.

Algorithm 2 Completion of Gradient Evaluation

  1. function gg = COMP-GRADIENT(vv, {Y}\{\mathcal{Y}\}, {S}\{\mathcal{S}\})

  2. Unpack vv into A,B,C\mathbf{A}, \mathbf{B}, \mathbf{C}

  3. vec⁡(UA)←blkdiag⁡3(YAB)vec⁡(B)\operatorname{vec}(U_A) \leftarrow\operatorname{blkdiag}_3(\mathcal{Y}_{AB})\operatorname{vec}(\mathbf{B})

  4. vec⁡(UB)←blkdiag⁡1(YBC)vec⁡(C)\operatorname{vec}(U_B) \leftarrow\operatorname{blkdiag}_1(\mathcal{Y}_{BC})\operatorname{vec}(\mathbf{C})

  5. vec⁡(UC)←blkdiag⁡2(YAC)Tvec⁡(A)\operatorname{vec}(U_C) \leftarrow\operatorname{blkdiag}_2(\mathcal{Y}_{AC})^{\mathsf{T}}\operatorname{vec}(\mathbf{A})

  6. GA←A(SB∗SC)−UA\mathbf{G}_A \leftarrow\mathbf{A}(S_B * S_C) - U_A ▷ GA=∂f∂A\mathbf{G}_A = \frac{\partial f}{\partial\mathbf{A}}

  7. GB←B(SA∗SC)−UB\mathbf{G}_B \leftarrow\mathbf{B}(S_A * S_C) - U_B ▷ GB=∂f∂B\mathbf{G}_B = \frac{\partial f}{\partial\mathbf{B}}

  8. GC←C(SA∗SB)−UC\mathbf{G}_C \leftarrow\mathbf{C}(S_A * S_B) - U_C ▷ GC=∂f∂C\mathbf{G}_C = \frac{\partial f}{\partial\mathbf{C}}

  9. Pack GA,GB,GC\mathbf{G}_A,\mathbf{G}_B,\mathbf{G}_C into gg

  10. return gg

  11. end function

Algorithm 3 Completion of Application of K Term of Hessian to a Vector

  1. function ss = COMP-APPLY-K(vv, vˉ\bar{v}, {Y}\{\mathcal{Y}\}, {S}\{\mathcal{S}\})

  2. Unpack vv into A,B,C\mathbf{A},\mathbf{B},\mathbf{C}, unpack vˉ\bar{v} into Aˉ,Bˉ,Cˉ\bar{\mathbf{A}},\bar{\mathbf{B}},\bar{\mathbf{C}}

  3. SˉA←ATAˉ,SˉB←BTBˉ,SˉC←CTCˉ\bar{S}_A \leftarrow\mathbf{A}^{\mathsf{T}}\bar{\mathbf{A}},\quad\bar{S}_B \leftarrow\mathbf{B}^{\mathsf{T}}\bar{\mathbf{B}},\quad\bar{S}_C \leftarrow\mathbf{C}^{\mathsf{T}}\bar{\mathbf{C}}

  4. vec⁡(NAB)←blkdiag⁡3(YAB)vec⁡(Bˉ)\operatorname{vec}(N_{AB}) \leftarrow\operatorname{blkdiag}_3(\mathcal{Y}_{AB})\operatorname{vec}(\bar{\mathbf{B}})

  5. vec⁡(NAC)←blkdiag⁡2(YAC)vec⁡(Cˉ)\operatorname{vec}(N_{AC}) \leftarrow\operatorname{blkdiag}_2(\mathcal{Y}_{AC})\operatorname{vec}(\bar{\mathbf{C}})

  6. vec⁡(NBA)←blkdiag⁡3(YAB)Tvec⁡(Aˉ)\operatorname{vec}(N_{BA}) \leftarrow\operatorname{blkdiag}_3(\mathcal{Y}_{AB})^{\mathsf{T}}\operatorname{vec}(\bar{\mathbf{A}})

  7. vec⁡(NBC)←blkdiag⁡1(YBC)vec⁡(Cˉ)\operatorname{vec}(N_{BC}) \leftarrow\operatorname{blkdiag}_1(\mathcal{Y}_{BC})\operatorname{vec}(\bar{\mathbf{C}})

  8. vec⁡(NCA)←blkdiag⁡2(YAC)Tvec⁡(Aˉ)\operatorname{vec}(N_{CA}) \leftarrow\operatorname{blkdiag}_2(\mathcal{Y}_{AC})^{\mathsf{T}}\operatorname{vec}(\bar{\mathbf{A}})

  9. vec⁡(NCB)←blkdiag⁡1(YBC)Tvec⁡(Bˉ)\operatorname{vec}(N_{CB}) \leftarrow\operatorname{blkdiag}_1(\mathcal{Y}_{BC})^{\mathsf{T}}\operatorname{vec}(\bar{\mathbf{B}})

  10. QA←A(SC∗SˉB+SB∗SˉC)−NAB−NAC\mathbf{Q}_A \leftarrow\mathbf{A}(S_C * \bar{S}_B + S_B * \bar{S}_C) - N_{AB} - N_{AC}

  11. QB←B(SC∗SˉA+SA∗SˉC)−NBA−NBC\mathbf{Q}_B \leftarrow\mathbf{B}(S_C * \bar{S}_A + S_A * \bar{S}_C) - N_{BA} - N_{BC}

  12. QC←C(SB∗SˉA+SA∗SˉB)−NCA−NCB\mathbf{Q}_C \leftarrow\mathbf{C}(S_B * \bar{S}_A + S_A * \bar{S}_B) - N_{CA} - N_{CB}

  13. Pack QA,QB,QC\mathbf{Q}_A,\mathbf{Q}_B,\mathbf{Q}_C into ss

  14. return ss

  15. end function

After the search direction sks_k 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 ρ\rho between the true and model decrease found from taking step sks_k. If the ratio is sufficiently high, then we accept the step, equilibrate the new point, and decrease λ\lambda. If the ratio is small or negative, then the step is rejected, and λ\lambda is increased. There are also intermediate values of ρ\rho where the step is accepted, but λ\lambda 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 X\mathcal{X} is an m×n×pm \times n \times p tensor and the CP model has rank rr. 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 JTJ\mathbf{J}^{\mathsf{T}}\mathbf{J} and K\mathbf{K}. We also show the comparison with the complexity of Gauss-Newton methods that rely on a iterative method to compute the step. direction.

CalculationNewton ComplexityGauss-Newton Complexity
Per Outer Iteration:
Precomputed TTMs6mnpr6mnpr4mnpr4mnpr
Gradient CompletionsO((mn+mp+np)r)O((mn+mp+np)r)O((mn+mp+np)r)O((mn+mp+np)r)
Gram MatricesO((m+n+p)r2)O((m+n+p)r^2)O((m+n+p)r2)O((m+n+p)r^2)
Per Rejected Step2mnpr2mnpr2mnpr2mnpr
Per Inner Iteration:
Apply JTJ\mathbf{J}^{\mathsf{T}}\mathbf{J}O((m+n+p)r2)O((m+n+p)r^2)O((m+n+p)r2)O((m+n+p)r^2)
Apply K\mathbf{K} CompletionsO((mn+mp+np)r)O((mn+mp+np)r)−-

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., YAB\mathcal{Y}_{AB}), 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 dd-way case. As usual, the notational complexity of the dd-way case can obscure the key concepts. We briefly introduce dd-way notation and provide examples rather than comprehensive expressions to illustrate the ideas. We consider X\mathcal{X} to be a dd-way data tensor with dimensions n1×⋯×ndn_1 \times\cdots\times n_d and a rank-rr CP model with factor matrices [ ⁣[U1,…,Ud] ⁣][\![\mathbf{U}_1,\ldots,\mathbf{U}_d]\!]. We use iki_k to index dimension nkn_k for 1≤k≤d1 \leq k \leq d and ℓ\ell to index rr (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 dd-way case is given in [3 Ch. 13].

The structure of the K\mathbf{K} term of the dd-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 (d2)=d(d−1)/2\binom{d}{2}=d(d-1)/2 off-diagonal blocks are given by expressions that generalize Lem. 2. In the case of factor matrices jj and kk, the corresponding off-diagonal block is given by Kjk=blkdiag⁡3(Zjk)\mathbf{K}_{jk}=\operatorname{blkdiag}_3(\mathcal{Z}_{jk}) where Zjk\mathcal{Z}_{jk} is the nj×nk×rn_j \times n_k \times r tensor computed from a partial MTTKRP involving the residual tensor and all factor matrices except Uj\mathbf{U}_j and Uk\mathbf{U}_k. Expressed elementwise for the case j=1j=1 and k=2k=2, for example, we have

Z12(i1,i2,ℓ)=∑i3,…,idR(i1,…,id)U3(i3,ℓ)⋯Ud(id,ℓ).\mathcal{Z}_{12}(i_1,i_2,\ell)=\sum_{i_3,\ldots,i_d}\mathcal{R}(i_1,\ldots,i_d)U_3(i_3,\ell)\cdots U_d(i_d,\ell).

Applying the K\mathbf{K} term of the dd-way Hessian to a vector follows the pattern described in § 3.3 and Lem. 3: there are d2−dd^2-d matrix-vector product terms to be computed involving a block of K\mathbf{K} 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

K12vec⁡(U‾2)=vec⁡(R(1)(Ud⊙⋯⊙U3⊙U‾2))=vec⁡(U1(UdTUd∗⋯∗U3TU3∗U2TU‾2))−X(1)(Ud⊙⋯⊙U3⊙U‾2).\mathbf{K}_{12}\operatorname{vec}(\overline{\mathbf{U}}_{2}) = \operatorname{vec}\left(\mathbf{R}_{(1)}\left(\mathbf{U}_{d} \odot\cdots\odot\mathbf{U}_{3} \odot\overline{\mathbf{U}}_{2}\right)\right) = \operatorname{vec}\left(\mathbf{U}_{1}\left(\mathbf{U}_{d}^{\mathsf{T}}\mathbf{U}_{d} * \cdots* \mathbf{U}_{3}^{\mathsf{T}}\mathbf{U}_{3} * \mathbf{U}_{2}^{\mathsf{T}}\overline{\mathbf{U}}_{2}\right)\right) - \mathbf{X}_{(1)}\left(\mathbf{U}_{d} \odot\cdots\odot\mathbf{U}_{3} \odot\overline{\mathbf{U}}_{2}\right).

As in the 3-way case, we must avoid explicitly computing the d2−dd^{2}-d MTTKRPs involving either the residual tensor R\mathbf{R} or the data tensor X\mathbf{X} at every iteration of GLRT. Instead, we precompute the d(d−1)/2d(d-1)/2 partial MTTKRPs involving the data tensor and all but two of the Newton iterate factor matrices. Each of these intermediate tensors {Y}\{\mathbf{Y}\} 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 Z12\mathbf{Z}_{12} above, we have

Y12(i1,i2,ℓ)=∑i3,…,idX(i1,…,id)U3(i3,ℓ)⋯Ud(id,ℓ).\mathbf{Y}_{12}(i_{1},i_{2},\ell) = \sum_{i_{3},\ldots,i_{d}} \mathbf{X}(i_{1},\ldots,i_{d})\mathbf{U}_{3}(i_{3},\ell)\cdots\mathbf{U}_{d}(i_{d},\ell).

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., Sk=UkTUk\mathbf{S}_{k} = \mathbf{U}_{k}^{\mathsf{T}}\mathbf{U}_{k}). Both sets of intermediates are re-used multiple times in evaluating the gradient and applying K\mathbf{K}.

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 dd-way case is to take advantage of memoization in the computation of the {Y}\{\mathbf{Y}\} tensors. Despite the fact that the number of intermediates to be computed is d(d−1)/2d(d-1)/2, 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 dd-way case.

Assuming a cubical dd-way tensor n1=⋯=ndn_{1} = \cdots= n_{d} and a rank-rr 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 6ndr6n^{d}r compared to 4ndr4n^{d}r for Gauss-Newton. The costs of gradient completions (O(dn2r)O(dn^{2}r)), Gram matrices (O(dnr2)O(dnr^{2})), and rejected steps (2ndr2n^{d}r) are the same between methods. In each inner iteration, the cost of applying JTJ\mathbf{J}^{\mathsf{T}}\mathbf{J} shared by both methods is O(d2nr2)O(d^{2}nr^{2}), and the added cost of applying K\mathbf{K} is O(d2nr)O(d^{2}nr). Because the cost of the precomputations in the outer iteration is the only cost exponential in dd, we expect to be even more dominated by that step for d>3d > 3. Thus, the estimate of Newton iterations costing 50% more than Gauss-Newton iterations should be more accurate for larger dd.

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 K(v)\mathbf{K}(\mathbf{v}) 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 λ=0.1\lambda= 0.1. A step is rejected based on the ratio ρ\rho between the true and model decrease: a step is rejected if ρ<10−8\rho< 10^{-8}. Accepted steps with ρ<0.25\rho< 0.25 multiply λ\lambda by 3, and those with ρ≥0.75\rho\ge0.75 divide it by 2. The inner tolerance follows the Eisenstat–Walker forcing terms [11], with γ=0.1\gamma= 0.1, ηmax⁡=10−2\eta_{\max} = 10^{-2}, and exponent α=1\alpha= 1 for GN and α=2\alpha= 2 for Newton. The hybrid method runs Gauss-Newton until ∥g(vk)∥<10−4∥g(v0)∥\lVert g(v_k)\rVert< 10^{-4}\lVert g(v_0)\rVert and then switches permanently to Newton. These three methods stop when ∥g(vk)∥<3×10−8\lVert g(v_k)\rVert< 3 \times10^{-8} 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 tt uses random seed tt, so different values of a swept parameter share the same initial tensor.

Metrics

We report the relative error ∥X−M∥/∥X∥\lVert\mathcal{X}-\mathcal{M}\rVert/\lVert\mathcal{X}\rVert and the gradient norm at each iteration, where X\mathcal{X} is the original data, and M\mathcal{M} 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 200×200×200200 \times200 \times200 tensors with r=rtrue=10r = r_{\mathrm{true}} = 10 and c=0.9c = 0.9, for noise parameter η∈{0.1,0.3,0.5}\eta\in\{0.1, 0.3, 0.5\}. Rows show relative error, gradient norm, and score; the dotted line marks the relative error of the true model, approximately η\eta, and the dashed line marks the gradient tolerance.

Synthetic tensors are 200×200×200200 \times200 \times200, generated with Tensor Toolbox’s create_problem: the factor matrices have unit weights and columns with collinearity cc, and noise is added as

X=M+η1−η2⋅∥M∥⋅N∥N∥(8)\mathcal{X} = \mathcal{M} + \frac{\eta}{\sqrt{1-\eta^2}} \cdot\lVert\mathcal{M}\rVert\cdot\frac{\mathcal{N}}{\lVert\mathcal{N}\rVert} \tag*{(8)}

with N\mathcal{N} Gaussian and 0≤η<10 \le\eta< 1.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 cc of the true factors while keeping the residual at zero (Figure 2). The model rank matches the true rank, r=rtrue=10r = r_{\mathrm{true}} = 10, 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 200×200×200200 \times200 \times200 tensors with r=rtrue=10r = r_{\mathrm{true}} = 10 and η=0\eta= 0, for collinearity c∈{0.5,0.7,0.9}c \in\{0.5, 0.7, 0.9\}. 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 cc increases, ALS slows, and at c=0.9c = 0.9 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 K\mathbf{K}, 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, K\mathbf{K} is not negligible, and Newton wanders before it reaches the region where it converges quickly.

Varying Noise

Next, we fix collinearity at c=0.9c = 0.9 and rank r=rtrue=10r = r_{\mathrm{true}} = 10 and vary the noise parameter η∈{0.1,0.3,0.5}\eta\in\{0.1, 0.3, 0.5\} from (8), so that the true model has relative error approximately η\eta (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 η=0.1\eta= 0.1 and η=0.3\eta= 0.3, both Gauss-Newton and Newton converge in every trial, with Newton again taking roughly twice as many iterations. At η=0.5\eta= 0.5, 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 η=0.5\eta= 0.5, 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 rtrue=12r_{\mathrm{true}} = 12, c=0.9c = 0.9, and η=0\eta= 0, and fit models of rank r∈{10,12,14}r \in\{10, 12, 14\} (Figure 4). Each method runs for at most 200 iterations in this experiment.

Figure 4. Synthetic 200×200×200200 \times200 \times200 tensors with rtrue=12r_{\mathrm{true}} = 12, c=0.9c = 0.9, and η=0\eta= 0, for model rank r∈{10,12,14}r \in\{10, 12, 14\} (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 200×200×200200 \times200 \times200 tensors. Left (Easy): r=rtrue=10r = r_{\mathrm{true}} = 10, c=0.5c = 0.5, and η=0\eta= 0. Right (Hard): r=14r = 14, rtrue=12r_{\mathrm{true}} = 12, c=0.9c = 0.9, and η=0.5\eta= 0.5. 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.

MethodEasy AcceptedEasy RejectedHard AcceptedHard Rejected
Gauss-Newton13–174–72007–13
Tensorlab GN13–172–420020–26
Newton25–349–1576–8930–35
Hybrid12–174–771–10920–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 1036×72×9001036 \times72 \times900 tensor (time ×\times sensor ×\times experiment).3 We fit r=10r = 10, as in [30, 4], and also r=5r = 5, 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 (1036×72×9001036 \times72 \times900), for r∈{5,10}r \in\{5, 10\}. 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 r=5r = 5 and 0.19 for r=10r = 10. For r=5r = 5, 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 r=10r = 10, 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 43×200×8843 \times200 \times88 tensor (neuron ×\times time ×\times 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 r∈{1,2,3}r \in\{1, 2, 3\} (Figure 7). The convergence behavior for r=4r = 4 to 10 is similar to that for r=3r = 3 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 η=0.5\eta= 0.5 synthetic experiment.

Figure 7. Monkey BMI tensor (43×200×8843 \times200 \times88), for r∈{1,2,3}r \in\{1, 2, 3\}. 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 r=1r = 1, every method converges within 25 iterations. For r=2r = 2, Newton converges in about a third as many iterations as Gauss-Newton, and the hybrid method is only slightly slower than Newton. For r=3r = 3, 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 ∼50%\sim50\% 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 dd-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-rr Kruskal tensor with all the ambiguity that it implies. Another possibility is to use the weighted variant ∑i=1rλiai∘bi∘ci\sum_{i=1}^{r} \lambda_i \mathbf{a}_i \circ\mathbf{b}_i \circ\mathbf{c}_i, where now we require that ∥ai∥=∥bi∥=∥ci∥=1\lVert\mathbf{a}_i\rVert= \lVert\mathbf{b}_i\rVert= \lVert\mathbf{c}_i\rVert= 1 and λi≥0\lambda_i \ge0. These norms mean exactly that the unknowns in (ai,bi,ci)(\mathbf{a}_i,\mathbf{b}_i,\mathbf{c}_i) 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. [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. [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. [3]G. Ballard and T. G. Kolda. Tensor Decompositions for Data Science. Cambridge University Press, June 2025. URL: https://tensor-toolbox.com/.DOI
  4. [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. [5]N. Boumal. An Introduction to Optimization on Smooth Manifolds. Cambridge University Press, 2023. doi:10.1017/9781009166164.DOI
  6. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [29]A. Vergara. Gas sensor arrays in open sampling settings, 2013. doi:10.24432/C5JP5N.
  30. [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. [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. [32]N. Vervliet, O. Debals, L. Sorber, M. Van Barel, and L. De Lathauwer. Tensorlab 3.0. https://www.tensorlab.net, 2016.DOI
  33. [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.

Paper details

vlnc:W_7pakyr5f
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude

View statement
Looking for related papers…
Contents