The Assumption of Proportional Components when Candecomp is Applied to Symmetric Matrices in the Context of Indscal

The use of Candecomp to fit scalar products in the context of INDSCAL is based on the assumption that the symmetry of the data matrices involved causes the component matrices to be equal when Candecomp converges. Ten Berge and Kiers gave examples where this assumption is violated for Gramian data matrices. These examples are believed to be local minima. It is now shown that, in the single-component case, the assumption can only be violated at saddle points. Chances of Candecomp converging to a saddle point are small but still nonzero.     

Some additional results on principal components analysis of three-mode data by means of alternating least squares algorithms

Kroonenberg and de Leeuw (1980) have developed an alternating least-squares method TUCKALS-3 as a solution for Tucker's three-way principal components model. The present paper offers some additional features of their method. Starting from a reanalysis of Tucker's problem in terms of a rank-constrained regression problem, it is shown that the fitted sum of squares in TUCKALS-3 can be partitioned according to elements of each mode of the three-way data matrix. An upper bound to the total fitted sum of squares is derived. Finally, a special case of TUCKALS-3 is related to the Carroll/Harshman CANDECOMP/PARAFAC model.     

Degeneracy in Candecomp/Parafac explained for p × p × 2 arrays of rank p + 1 or higher

The Candecomp/Parafac (CP) model decomposes a three-way array into a prespecified number R of rank-1 arrays and a residual array, in which the sum of squares of the residual array is minimized. The practical use of CP is sometimes complicated by the occurrence of so-called degenerate solutions, in which some components are highly correlated in all three modes and the elements of these components become arbitrarily large. We consider the real-valued CP model in which p × p × 2 arrays of rank p + 1 or higher are decomposed into p rank-1 arrays and a residual array. It is shown that the CP objective function does not have a minimum in these cases, but an infimum. Moreover, any sequence of CP approximations, of which the objective value approaches the infimum, will become degenerate. This result extends Ten Berge, Kiers, & De Leeuw (1988), who consider a particular 2 × 2 × 2 array of rank 3. Request for reprints should be sent to Alwin Stegeman, Heijmans Institute of Psychological Research, University of Groningen, Grote Kruisstraat 2/1, 9712 TS Groningen, The Netherlands. The author is obliged to Jos ten Berge and Henk Kiers for helpful comments. Also, the author would like to thank the Associate Editor and the anonymous reviewers for many suggestions on how to improve the contents and the presentation of the paper.     

Sufficient conditions for uniqueness in Candecomp/Parafac and Indscal with random component matrices

A key feature of the analysis of three-way arrays by Candecomp/Parafac is the essential uniqueness of the trilinear decomposition. We examine the uniqueness of the Candecomp/Parafac and Indscal decompositions. In the latter, the array to be decomposed has symmetric slices. We consider the case where two component matrices are randomly sampled from a continuous distribution, and the third component matrix has full column rank. In this context, we obtain almost sure sufficient uniqueness conditions for the Candecomp/Parafac and Indscal models separately, involving only the order of the three-way array and the number of components in the decomposition. Both uniqueness conditions are closer to necessity than the classical uniqueness condition by Kruskal. Part of this research was supported by (1) the Flemish Government: (a) Research Council K.U. Leuven: GOA-MEFISTO-666, GOA-Ambiorics, (b) F.W.O. project G.0240.99, (c) F.W.O. Research Communities ICCoS and ANMMM, (d) Tournesol project T2004.13; and (2) the Belgian Federal Science Policy Office: IUAP P5/22. Lieven De Lathauwer holds a permanent research position with the French Centre National de la Recherche Scientifique (C.N.R.S.). He also holds an honorary research position with the K.U. Leuven, Leuven, Belgium.     

On uniqueness in candecomp/parafac

One of the basic issues in the analysis of three-way arrays by CANDECOMP/PARAFAC (CP) has been the question of uniqueness of the decomposition. Kruskal (1977) has proved that uniqueness is guaranteed when the sum of thek-ranks of the three component matrices involved is at least twice the rank of the solution plus 2. Since then, little has been achieved that might further qualify Kruskal's sufficient condition. Attempts to prove that it is also necessary for uniqueness (except for rank 1 or 2) have failed, but counterexamples to necessity have not been detected. The present paper gives a method for generating the class of all solutions (or at least a subset of that class), given a CP solution that satisfies certain conditions. This offers the possibility to examine uniqueness for a great variety of specific CP solutions. It will be shown that Kruskal's condition is necessary and sufficient when the rank of the solution is three, but that uniqueness may hold even if the condition is not satisfied, when the rank is four or higher. The authors are obliged to Henk Kiers for commenting on a previous draft, and to Tom Snijders for suggesting a proof mentioned in the appendix.     

Degeneracy in Candecomp/Parafac and Indscal Explained For Several Three-Sliced Arrays With A Two-Valued Typical Rank

The Candecomp/Parafac (CP) method decomposes a three-way array into a prespecified number R of rank-1 arrays, by minimizing the sum of squares of the residual array. The practical use of CP is sometimes complicated by the occurrence of so-called degenerate sequences of solutions, in which several rank-1 arrays become highly correlated in all three modes and some elements of the rank-1 arrays become arbitrarily large. We consider the real-valued CP decomposition of all known three-sliced arrays, i.e., of size p×q×3, with a two-valued typical rank. These are the 5×3×3 and 8×4×3 arrays, and the 3×3×4 and 3×3×5 arrays with symmetric 3×3 slices. In the latter two cases, CP is equivalent to the Indscal model. For a typical rank of {m,m+1}, we consider the CP decomposition with R=m of an array of rank m+1. We show that (in most cases) the CP objective function does not have a minimum but an infimum. Moreover, any sequence of feasible CP solutions in which the objective value approaches the infimum will become degenerate. We use the tools developed in Stegeman (2006), who considers p×p×2 arrays, and present a framework of analysis which is of use to the future study of CP degeneracy related to a two-valued typical rank. Moreover, our examples show that CP uniqueness is not necessary for degenerate solutions to occur. The author is supported by the Dutch Organisation for Scientific Research (NWO), VENI grant 451-04-102.