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

Stegeman A - Psychometrika (2007)

Bottom Line: We show that (in most cases) the CP objective function does not have a minimum but an infimum.We use the tools developed in Stegeman (2006), who considers pxpx2 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.

View Article: PubMed Central - PubMed

Affiliation: Heijmans Institute of Psychological Research, University of Groningen, Grote Kruisstraat 2/1, 9712 TS Groningen, The Netherlands.

ABSTRACT
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 pxqx3, with a two-valued typical rank. These are the 5x3x3 and 8x4x3 arrays, and the 3x3x4 and 3x3x5 arrays with symmetric 3x3 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 pxpx2 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.

No MeSH data available.


Illustration of problems (3.1) and (3.2). The sets D (rank m) and R\S (rank ≥ m +1) have equal dimensionality and the boundary of D has lower dimensionality. The target array X lies in the set R\S. The boundary point ˜X is the optimal solution of problem (3.2).
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC2806219&req=5

Fig1: Illustration of problems (3.1) and (3.2). The sets D (rank m) and R\S (rank ≥ m +1) have equal dimensionality and the boundary of D has lower dimensionality. The target array X lies in the set R\S. The boundary point ˜X is the optimal solution of problem (3.2).

Mentions: Consider the set D = Dm ∩ R, i.e., D consists of all arrays in R that have rank m. The problem we analyse is\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{gathered} Minimize \left\/ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{X} - \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{Y} } \right\/^2 , \hfill \\ subject \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{Y} \in \mathcal{D} \hfill \\ \end{gathered} $$\end{document}. As explained in the previous section, since X ∉ D, any optimal solution of problem (3.1) is a boundary point of D. Next, define the set S as the closure of D within the set R, i.e., S contains D and all its boundary points which lie in R. Hence, by definition, S is a closed subset of R and the interior of S is contained in the set D. We also consider the following problem:\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\eqalign{ & {\rm{Minimize }}{\left\/ {{\rm{ - }}} \right\/^2}, \cr & {\rm<Superscript>bject to </Superscript>} \in {\rm{ }}S \cr} $$\end{document}. Since X ∉ D and S is closed, problem (3.2) always has an optimal solution ˜X which is a boundary point of S and of D. See Figure 1 for an illustration. The key question is whether ˜X lies in D or not. If it does, then problem (3.1) has an optimal solution ˜X and the objective function in (3.1) has a minimum. If ˜X does not lie in D and neither does any optimal solution of problem (3.2), then problem (3.1) has no optimal solution and the objective function in (3.1) has no minimum. For Cases 3, 4, 5, and 6 of Table 1, it will be shown that the latter is true almost everywhere, because the boundary points of D have rank larger than m almost everywhere. The next step is to show that any sequence of CP updates in D, which converges to ˜X, necessarily becomes degenerate.Figure 1


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

Stegeman A - Psychometrika (2007)

Illustration of problems (3.1) and (3.2). The sets D (rank m) and R\S (rank ≥ m +1) have equal dimensionality and the boundary of D has lower dimensionality. The target array X lies in the set R\S. The boundary point ˜X is the optimal solution of problem (3.2).
© Copyright Policy
Related In: Results  -  Collection

Show All Figures
getmorefigures.php?uid=PMC2806219&req=5

Fig1: Illustration of problems (3.1) and (3.2). The sets D (rank m) and R\S (rank ≥ m +1) have equal dimensionality and the boundary of D has lower dimensionality. The target array X lies in the set R\S. The boundary point ˜X is the optimal solution of problem (3.2).
Mentions: Consider the set D = Dm ∩ R, i.e., D consists of all arrays in R that have rank m. The problem we analyse is\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{gathered} Minimize \left\/ {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{X} - \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{Y} } \right\/^2 , \hfill \\ subject \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{Y} \in \mathcal{D} \hfill \\ \end{gathered} $$\end{document}. As explained in the previous section, since X ∉ D, any optimal solution of problem (3.1) is a boundary point of D. Next, define the set S as the closure of D within the set R, i.e., S contains D and all its boundary points which lie in R. Hence, by definition, S is a closed subset of R and the interior of S is contained in the set D. We also consider the following problem:\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\eqalign{ & {\rm{Minimize }}{\left\/ {{\rm{ - }}} \right\/^2}, \cr & {\rm<Superscript>bject to </Superscript>} \in {\rm{ }}S \cr} $$\end{document}. Since X ∉ D and S is closed, problem (3.2) always has an optimal solution ˜X which is a boundary point of S and of D. See Figure 1 for an illustration. The key question is whether ˜X lies in D or not. If it does, then problem (3.1) has an optimal solution ˜X and the objective function in (3.1) has a minimum. If ˜X does not lie in D and neither does any optimal solution of problem (3.2), then problem (3.1) has no optimal solution and the objective function in (3.1) has no minimum. For Cases 3, 4, 5, and 6 of Table 1, it will be shown that the latter is true almost everywhere, because the boundary points of D have rank larger than m almost everywhere. The next step is to show that any sequence of CP updates in D, which converges to ˜X, necessarily becomes degenerate.Figure 1

Bottom Line: We show that (in most cases) the CP objective function does not have a minimum but an infimum.We use the tools developed in Stegeman (2006), who considers pxpx2 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.

View Article: PubMed Central - PubMed

Affiliation: Heijmans Institute of Psychological Research, University of Groningen, Grote Kruisstraat 2/1, 9712 TS Groningen, The Netherlands.

ABSTRACT
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 pxqx3, with a two-valued typical rank. These are the 5x3x3 and 8x4x3 arrays, and the 3x3x4 and 3x3x5 arrays with symmetric 3x3 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 pxpx2 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.

No MeSH data available.