Figure 4. CP decomposition of a third-order tensor.
matrices, respectively. The factor
matrices can be initialized
randomly. The pseudoinverse
of a matrix V of size RR×
must be computed at each iteration.
The iterations stop
when some stop conditions
are satisfied, e.g., meeting the
maximum iterations or little
or no change in the factor matrices.
The drawback of this
algorithm is that subtracting
the best rank-one tensor may
The rank of a tensor X is defined as the smallest
number of rank-one tensors that can generate the
original tensor as their sum. Determining the rank of
a specifically given tensor is NP-hard [46]. There is no
straightforward algorithm to solve this problem. For a
general third-order tensor X∈
R ××
IJ K , the weak upper
bound on its largest attainable rank is given by:
rank
()X ≤ min{IJ IK JK,, .
}
Any rank that occurs with positive probability is
called a typical rank. Table 1 from [47] shows known
typical ranks of specific third-order tensors over R.
Given the rank R, there are many algorithms to compute
the CP decomposition. Denton et al. computed
the CP decomposition by the alternating least squares
(ALS) method [16]. The
ALS method was proposed in the original articles by
Carroll and Chang [44] and Harshman et al. [45].
Given the rank R, the ALS procedure for an N -th
order tensor is shown in Algorithm 1 where * and
stand for the Hadamard and Khatri-Rao products of
increase tensor rank [54]. Lebedev et al. [17] used the
non-linear least squares (NLS) method. Given the rank
R , NLS minimizes the L2 -norm of the approximation
error by using GaussNewton optimization. NLS decomposition