PARAFAC algorithms

Multi-way Analysis With Applications in the Chemical Sciences 

In order to fit the model using alternating least squares it is necessary to come up with an update for A given B and C for B given A and C and for C given A and B. Due to the symmetry of the model, an update for one mode, e.g. A, is essentially identical to an update for any of the modes with the role of the different loading matrices shifted. To estimate A conditionally on B and C formulate the optimization problem as 

From the symmetry of the problem, it follows that B and C can be updated in similar ways. An algorithm follows directly as shown in Algorithm 6.1. 

Given X of size I x J x K and sought dimension R. Superscripts indicating current estimates are omitted for notational convenience 

---

Direct trilinear decomposition (DTLD) is a direct non-iterative and therefore fast algorithm for solving the PARAFAC model providing a non-LS solution. If data are low-rank trilinear, the solution produced by DTLD will be close to identical to that resulting from the PARAFAC algorithm. 

Clearly, these residuals are far from perfect, and thus, even though the data are known to be perfectly trilinear with two components, the sequential PARAFAC algorithm fails to find a reasonable estimate of the parameters. However, this difference between sequential and simultaneous fitting is not related to the three-way nature of the PARAFAC model. Rather it is the orthogonality of the components in principal component analysis that enables the components to be calculated sequentially. A simple two-way example will help in illustrating this. 

The XPS [Do McIntyre 1999] example uses the positive matrix factorization variant of the PARAFAC algorithm [Paatero 1997] and obtains three components with all-positive... 

We have noted that three-way resolution methods generally work with the unfolded matrices. Depending on the algorithm used, all three types of unfolded matrices may be used, or only some of them. In the PARAFAC decomposition of a trilinear data set, all three types of unfolded data matrices are used, whereas in the resolution of a nontrilinear data set by the MCR-ALS method, only one type of unfolded matrix is used. 

In truth, there is no limit to the number of ways that can form a data set. The open-ended description for data with more than three ways is A-way data. For example, a collection of excitation-emission-time decay fluorescence spectra forms four-way data. Add reaction kinetics or varying experimental conditions, and fiveway data, or greater, could easily be formed. Many of the techniques discussed below, in particular the PARAFAC-based algorithms, are readily extended to A-way applications [14, 15]. 

PARAFAC refers both to the parallel factorization of the data set R by Equation 12.1a and Equation 12.lb and to an alternating least-squares algorithm for determining X, Y, and Z in the two equations. The ALS algorithm is known as PARAFAC, emanating from the work by Kroonenberg [31], and as CANDECOMP, for canonical decomposition, based on the work of Harshman [32], In either case, the two basic algorithms are practically identical. 

The PARAFAC/CANDECOMP algorithm begins with an initial guess of the X-way and Y-way starting profiles. The initial Z-way profiles are determined by solving... 

Fitting a two-component PARAFAC model using a least squares simultaneous algorithm provides (unique) estimates of A, B, and C that give a perfect model of X... 

There are relations between the Tucker3 model and the PARAFAC model. These will be dealt with in Chapter 5. Algorithms to calculate the parameters in a Tucker3 model will be discussed in Chapter 6. 

Figure 5.3. Fit values (upper left) and parameter values as a function of iteration number in a PARAFAC-ALS algorithm. For each mode, there are four parameters (2 x 2) which are shown as lines in the plots.

Nonnegativity is a lower bounded problem, where each parameter is bound to be above or equal to zero. Such a bounded problem can be efficiently solved with an active set algorithm [Gill et al. 1981], How this algorithm can be implemented in an alternating least squares algorithm, e.g., for fitting the PARAFAC model is explained. 

Harshman advocates the use of split-half analysis for determining the proper rank of models with unique axes, that is, models with no rotational freedom [Harshman 1984, Harshman De Sarbo 1984], In split-half analysis different subsets of the data are analyzed independently. Due to the uniqueness of the PARAFAC model, the same result - same loadings -will be obtained in the nonsplit modes from models of any suitable subset of the data, if the correct number of components is chosen. To judge whether two models are equal, the indeterminacy in trilinear models has to be remembered the order and scale of components may change if not fixed algorithmically. If too many or too few components are chosen, the model parameters will differ if a different data set is used for fitting the model. 

In order to improve the calibration results, an analyte concentration in the mixture close to the analyte concentration in the standard would be favorable. This is not a practical solution, but an alternative is to use multiple standards. All five standards are used now. The calibration equations become slightly more complicated (i.e. a combination of cases (ii) and (iii) from above, see Appendix 10.C), but end up in a relatively straightforward three-way model. Generalized rank annihilation cannot be used anymore, since there are more than two slices in the three-way array. The authors used direct trilinear decomposition to solve this problem but an ordinary PARAFAC-ALS algorithm can also be used. The results are presented in Table 10.5 and show improvements at low concentrations. 

Kiers HAL, A three-step algorithm for CANDECOMP/PARAFAC analysis of large data sets with multicollinearity, Journal of Chemometrics, 1998, 12, 155-171. 

Kiers HAL, Krijnen WP, An efficient algorithm for PARAFAC of three-way data with large numbers of observation units, Psychometrika, 1991, 56, 147-152. 

Paatero P, A weighted non-negative least squares algorithm for three-way PARAFAC factor analysis, Chemometrics and Intelligent Laboratory Systems, 1997, 38, 223-242. 

---