Hostname: page-component-745bb68f8f-lrblm Total loading time: 0 Render date: 2025-01-08T05:30:29.772Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Non-Existence of Optimal Solutions and the Occurrence of “Degeneracy” in the CANDECOMP/PARAFAC Model

Published online by Cambridge University Press:  01 January 2025

Wim P. Krijnen ,
Theo K. Dijkstra  and
Alwin Stegeman
Wim P. Krijnen
Affiliation:
Hanze University Groningen
Theo K. Dijkstra
Affiliation:
University of Groningen
Alwin Stegeman*
Affiliation:
University of Groningen
*
Requests for reprints should be sent to Alwin Stegeman, Heymans Institute for Psychological Research, University of Groningen, Grote Kruisstraat 2/1, 9712 TS Groningen, The Netherlands. E-mail: [email protected];
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The CANDECOMP/PARAFAC (CP) model decomposes a three-way array into a prespecified number of R factors and a residual array by minimizing the sum of squares of the latter. It is well known that an optimal solution for CP need not exist. We show that if an optimal CP solution does not exist, then any sequence of CP factors monotonically decreasing the CP criterion value to its infimum will exhibit the features of a so-called “degeneracy”. That is, the parameter matrices become nearly rank deficient and the Euclidean norm of some factors tends to infinity. We also show that the CP criterion function does attain its infimum if one of the parameter matrices is constrained to be column-wise orthonormal.

Keywords

CandecompParafaclevel setsbounded sequencesfactor analysis
Type
Theory and Methods
Information
Psychometrika , Volume 73 , Issue 3 , September 2008 , pp. 431 - 439
Creative Commons
Creative Common License - CCCreative Common License - BYCreative Common License - NC
This article distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Copyright
Copyright © 2008 The Author(s)

Footnotes

A. Stegeman is supported by the Dutch Organisation for Scientific Research (NWO), Veni grant 451-04-102.

References

Andersen, A.H., & Rayens, W.S. (2004). Structure-seeking multilinear methods for the analysis of fMRI data. NeuroImage, 22, 728–739.CrossRefGoogle ScholarPubMed
Beckmann, C.F., & Smith, S.M. (2005). Tensorial extensions of independent component analysis for multisubject FMRI analysis. NeuroImage, 25, 294–311.CrossRefGoogle ScholarPubMed
Bro, R., & De Jong, S. (1997). A Fast non-negativity-constrained least squares algorithm. Journal of Chemometrics, 11, 393–401.3.0.CO;2-L>CrossRefGoogle Scholar
Carroll, J.D., & Chang, J.J. (1970). Analysis of individual differences in multidimensional scaling via an N-way generalization of ‘Eckart-Young’ decomposition. Psychometrika, 35, 283–319.CrossRefGoogle Scholar
DeSarbo, W.S., & Carroll, J.D. (1985). Three-way metric unfolding via alternating weighted least squares. Psychometrika, 50, 275–300.CrossRefGoogle Scholar
De Silva, V., & Lim, L.-H. (2006). Tensor rank and the ill-posedness of the best low-rank approximation problem. (SCCM Technical Report, 06-06). Preprint.Google Scholar
Harshman, R.A. (1970). Foundations of the PARAFAC procedure: models and conditions for an “exploratory” multi-modal factor analysis. UCLA Working Papers in Phonetics, 16, 1–84.Google Scholar
Harshman, R.A. (1972). Determination and proof of minimum uniqueness conditions for PARAFAC1. UCLA Working Papers in Phonetics, 22, 111–117.Google Scholar
Harshman, R.A., & DeSarbo, W.S. (1984). An application of PARAFAC to a small sample problem, demonstrating preprocessing, orthogonality constraints, and split-half diagnostic techniques. In Law, H.G., Snyder, C.W., Hattie, J.A., & McDonald, R.P. (Eds.), Research methods for multi-mode data analysis (pp. 602–642). New York: Praeger.Google Scholar
Harshman, R.A., & Lundy, M.E. (1984). Data preprocessing and the Extended PARAFAC model. In Law, H.G., Snyder, C.W., Hattie, J.A., & McDonald, R.P. (Eds.), Research methods for multi-mode data analysis (pp. 216–284). New York: Praeger.Google Scholar
Harshman, R.A., Ladefoged, P., & Goldstein, L. (1977). Factor analysis of tongue shapes. Journal of the Acoustical Society of America, 62, 693–707.CrossRefGoogle ScholarPubMed
Hopke, P.K., Paatero, P., Jia, H., Ross, R.T., & Harshman, R.A. (1998). Three-way (Parafac) factor analysis: examination and comparison of alternative computational methods as applied to ill-conditioned data. Chemometrics and Intelligent Laboratory Systems, 43, 25–42.CrossRefGoogle Scholar
Kiers, H.A.L. (1989). A computational short-cut for INDSCAL with orthonormality constraints on positive semi-definite matrices of lower rank. Computational Statistics Quarterly, 2, 119–135.Google Scholar
Kiers, H.A.L. (1989). An alternating least squares algorithm for fitting the two- and three-way DEDICOM model and the INDIOSCAL model. Psychometrika, 54, 515–521.CrossRefGoogle Scholar
Kiers, H.A.L. (1991). Simple structure in component analysis techniques for mixtures of qualitative and quantitative variables. Psychometrika, 56, 197–212.CrossRefGoogle Scholar
Krijnen, W.P. (2006). Convergence of the sequence of parameters generated by alternating least squares algorithms. Computational Statistics and Data Analysis, 51, 481–489.CrossRefGoogle Scholar
Krijnen, W.P., & Ten Berge, J.M.F. (1992). A constrained PARAFAC method for positive manifold data. Applied Psychological Measurement, 16, 295–305.CrossRefGoogle Scholar
Krijnen, W.P., & Kiers, H.A.L. (1993). A confirmatory and an exploratory approach to simple structure in PARAFAC. In Oud, J.H.L., & van Blokland-Vogelesang, R.A.W. (Eds.), Advances in longitudinal and multivariate analysis in the behavioral sciences (pp. 165–177). Leiden: DSWO Press.Google Scholar
Kruskal, J.B. (1976). More factors than subjects, tests and treatments: an indeterminacy theorem for canonical decomposition & individual differences scaling. Psychometrika, 41, 281–293.CrossRefGoogle Scholar
Kruskal, J.B. (1977). Three-way arrays: rank and uniqueness of trilinear decompositions, with applications to arithmetic complexity and statistics. Linear Algebra and Its Applications, 18, 95–138.CrossRefGoogle Scholar
Kruskal, J.B. (1989). Rank, decomposition, and uniqueness for 3-way and n-way arrays. In Coppi, R., & Bolasco, S. (Eds.), Multiway data analysis (pp. 7–18). Amsterdam: Elsevier.Google Scholar
Kruskal, J.B., Harshman, R.A., & Lundy, M.E. (1983). Some relationships between Tucker’s three-mode factor analysis and PARAFAC/CANDECOMP. Paper presented at the annual meeting of the Psychometric Society, Los Angeles.Google Scholar
Kruskal, J.B., Harshman, R.A., & Lundy, M.E. (1985). Several mathematical relationships between PARAFAC/CANDECOMP and three-mode factor analysis. Paper presented at the annual meeting of the classification society, St. John’s, Newfoundland.Google Scholar
Kruskal, J.B., Harshman, R.A., & Lundy, M.E. (1989). How 3-MFA data can cause degenerate PARAFAC solutions, among other relationships. In Coppi, R., & Bolasco, S. (Eds.), Multiway data analysis (pp. 115–122). Amsterdam: Elsevier.Google Scholar
Leurgans, S., & Ross, R.T. (1992). Multilinear models: applications in spectroscopy. Statistical Science, 7, 289–319.CrossRefGoogle Scholar
Lim, L.-H. (2005). Optimal solutions to non-negative Parafac/multilinear NMF always exist. Talk at the Workshop on tensor decompositions and applications, CIRM, Luminy, Marseille, France. Available online at http://www.etis.ensea.fr/~wtda.Google Scholar
Luenberger, D.G. (1969). Optimization by vector space methods, New York: Wiley.Google Scholar
Magnus, J.R., & Neudecker, H. (1979). The commutation matrix: some properties for applications. The Annals of Statistics, 7, 381–394.CrossRefGoogle Scholar
Meyer, J.P. (1980). Causal attribution for success and failure. A multivariate investigation of dimensionally, formation, and consequences. Journal of Personality and Social Psychology, 38, 704–718.CrossRefGoogle Scholar
Mitchell, B.C., & Burdick, D.S. (1994). Slowly converging PARAFAC sequences: swamps and two-factor degeneracies. Journal of Chemometrics, 8, 155–168.CrossRefGoogle Scholar
Ortega, J.M., & Rheinboldt, W.C. (1970). Iterative solution of nonlinear equations in several variables, San Diego: Academic Press.Google Scholar
Paatero, P. (1999). The multilinear engine—a table-driven least squares program for solving multilinear problems, including the n-way parallel factor analysis model. Journal of Computational and Graphical Statistics, 8, 854–888.Google Scholar
Paatero, P. (2000). Construction and analysis of degenerate PARAFAC models. Journal of Chemometrics, 14, 285–299.3.0.CO;2-1>CrossRefGoogle Scholar
Rudin, W. (1976). Principles of mathematical analysis, (3rd ed.). New York: McGraw-Hill.Google Scholar
Schur, J. (1911). Bemerkungen zur Theorie der beschränkten Bilinearformen mit unendlich vielen Veränderlichen. Journal für die Reine und Angewante Mathematiek, 140, 1–28.Google Scholar
Smilde, A. (1992). Three-way analysis: Problems and prospects. Chemometrics and Intelligent Laboratory Systems, 15, 143–157.CrossRefGoogle Scholar
Stegeman, A. (2006). Degeneracy in Candecomp/Parafac explained for p×p×2 arrays of rank p+1 or higher. Psychometrika, 71, 483–501.CrossRefGoogle Scholar
Stegeman, A. (2008a). Low-rank approximation of generic p×q×2 arrays and diverging components in the Candecomp/Parafac model. SIAM Journal on Matrix Analysis and Applications, to appear.CrossRefGoogle Scholar
Stegeman, A. (2008b). Degeneracy in Candecomp/Parafac and Indscal explained for several three-sliced arrays with a two-valued typical rank. Psychometrika, to appear.CrossRefGoogle Scholar
Stegeman, A., & Sidiropoulos, N.D. (2007). On Kruskal’s uniqueness condition for the Candecomp/Parafac decomposition. Linear Algebra and Its Applications, 420, 540–552.CrossRefGoogle Scholar
Styan, G.P.H. (1973). Hadamard products and multivariate statistical analysis. Linear Algebra and Its Applications, 6, 217–240.CrossRefGoogle Scholar
Ten Berge, J.M.F., Kiers, H.A.L., & De Leeuw, J. (1988). Explicit CANDECOMP-PARAFAC solutions for a contrived 2×2×2 array of rank three. Psychometrika, 53, 579–584.CrossRefGoogle Scholar
Ten Berge, J.M.F., Kiers, H.A.L., & Krijnen, W.P. (1993). The problem of negative saliences and asymmetry in INDSCAL. Journal of Classification, 10, 115–124.CrossRefGoogle Scholar
Tomasi, G., & Bro, R. (2006). A comparison of algorithms for fitting the Parafac model. Computational Statistics and Data Analysis, 50, 1700–1734.CrossRefGoogle Scholar
Zijlstra, B.J.H., & Kiers, H.A.L. (2002). Degenerate solutions obtained from several variants of factor analysis. Journal of Chemometrics, 16, 596–605.CrossRefGoogle Scholar