-
Notifications
You must be signed in to change notification settings - Fork 2
/
CANDECOMP.html
56 lines (55 loc) · 3.42 KB
/
CANDECOMP.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
<html><head><meta name="robots" content="index,follow">
<title>CANDECOMP</title></head><body bgcolor="#FFFFFF">
<table border=0 cellpadding=0 cellspacing=0><tr><td bgcolor="#CCCC00"><table border=4 cellpadding=9><tr><td align=middle bgcolor="#000000"><font face="Palatino,Times" size=6 color="#999900"><b>
CANDECOMP
</b></font></table></table>
<h3>
An algorithm to solve the INDSCAL problem.</h3>
<p>
In the analysis of the INDSCAL three-way data matrix (<i>numberOfPoints</i> × <i>numberOfDimensions</i> × <i>numberOfSources</i>) we seek to minimize the function: </p>
<table width="100%"><tr><td align=middle>
<i>f</i>(<i>X</i>, <i>W</i><sub>1</sub>,..., <i>W</i><sub><i>numberOfSources</sub></i>) = ∑<sub><i>i</i>=1..<i>numberOfSources</sub></i> | <i>S</i><sub><i>i</sub></i> – <i>X</i><i>W</i><sub><i>i</sub></i><i>X</i>′ |<sup>2</sup></table>
<p>
where <i>S</i><sub><i>i</sub></i> is a known symmetric <i>numberOfPoints</i> × <i>numberOfPoints</i> matrix with scalar products of distances for source <i>i</i>, <i>X</i> is the unknown configuration <i>numberOfPoints</i> × <i>numberOfDimensions</i> matrix, <i>X</i>′ its transpose, and, <i>W</i><sub><i>i</sub></i> is the diagonal <i>numberOfDimensions</i> × <i>numberOfDimensions</i> weight matrix for source <i>i</i>. The function above has no analytical solution for <i>X</i> and the <i>W</i><sub><i>i</sub></i>. It can be solved, however, by an iterative procedure which Carroll & Chang have christened CANDECOMP (CANonical DECOMPosition). This method minimizes, instead of the function given above, the following function:</p>
<dl>
<dd>
<i>g</i>(<i>X</i>, <i>Y</i>, <i>W</i><sub>1</sub>,..., <i>W</i><sub><i>numberOfSources</sub></i>) = ∑<sub><i>i</i>=1..<i>numberOfSources</sub></i> | <i>S</i><sub><i>i</sub></i> – <i>X</i><i>W</i><sub><i>i</sub></i><i>Y</i>′ |<sup>2</sup>
</dl>
<p>
where <i>X</i> and <i>Y</i> are both <i>numberOfPoints</i> × <i>numberOfDimensions</i> configuration matrices.</p>
<p>
The algorithm proceeds as follows:</p>
<p>
1. Initialize the <code>W</code> matrices and the configuration matrix <i>X</i>. This can for example be done according to a procedure given in <a href="Young__Takane___Lewyckyj__1978_.html">Young, Takane & Lewyckyj (1978)</a>.</p>
<p>
2. An alternating least squares minimization process is started as described that sequentially updates <i>Y</i>, <i>X</i> an <i>W</i> (<a href="Carroll___Chang__1970_.html">Carroll & Chang (1970)</a>):</p>
<dl>
<dd>
2.1. Solve for a new <i>Y</i> given <i>X</i> and the <i>W</i><sub><i>i</sub></i>
<dd>
2.2. Solve for a new <i>X</i> given the <i>W</i><sub><i>i</sub></i> and the new <i>Y</i>.
<dd>
2.3. Solve for the <i>W</i><sub><i>i</sub></i> given the new <i>X</i> and <i>Y</i>.
</dl>
<p>
Evaluate the goodness-of-fit criterion and either repeat the minimization sequence (2.1–2.3) or continue.</p>
<p>
3. Done: make <i>Y</i> equal to <i>X</i> and solve a last time for the <i>W</i><sub><i>i</sub></i>.</p>
<p>
Note: during the minimization the following constraints are effective:</p>
<dl>
<dd>
The configuration must be centered.
<dd>
The sum of squared coordinates in the configuration space is one for each dimension, i.e., the configuration always has unit variance in each dimension.
</dl>
<h3>Links to this page</h3>
<ul>
<li><a href="INDSCAL_analysis.html">INDSCAL analysis</a>
</ul>
<hr>
<address>
<p>© djmw, December 1, 1997</p>
</address>
</body>
</html>