next up previous
Next: Handling PTA-kmodes method Up: Multiway multidimensional data reduction Previous: SVD within tensor algebra

SVD-kmodes for $k=3$ and $k \geq 3$

Following a similar expression of a singular value one can write the maximisation problem to find the first singular value of $A \in E \otimes F \otimes G$ :
$\displaystyle \sigma_1$ $\textstyle =$ $\displaystyle \max_{{\scriptstyle
\begin{array}{l }
\scriptstyle \left\Vert \ps...
...Vert \phi \right\Vert _G =1
\end{array}}}A..(\psi \otimes \varphi \otimes \phi)$  
  $\textstyle =$ $\displaystyle A..(\psi_1 \otimes \varphi_1 \otimes \phi_1).$ (9)

Solving the Lagrange problem allows to compute the first solution using the following iterative algorithm (the iteration $(n+1)$ has three steps) where one can recognise a generalisation of the transition formula (6) :
$\displaystyle (X..\varphi_{(n)})..\phi_{(n)}$ $\textstyle =$ $\displaystyle ^1\sigma_{(n+1)}\psi_{(n+1)}$  
$\displaystyle (X..\phi_{(n)})..\psi_{(n)}$ $\textstyle =$ $\displaystyle ^2\sigma_{(n+1)}\varphi_{(n+1)}$  
$\displaystyle (X..\psi_{(n)})..\varphi_{(n)}$ $\textstyle =$ $\displaystyle ^3\sigma_{(n+1)}\phi_{(n+1)}$ (10)

For the second and other solution an orthogonality constraint is added, but unlike for two modes we do not have only the constraint of belonging to the orthogonal-tensorial of the first principal tensor. For example one can put the constraint of belonging to the subspace $(\psi_1
\otimes \varphi_1^\perp \otimes \phi_1^\perp)$ ; these solutions associated to $\psi_1$ are easily obtained from a SVD (SVD-(k-1)modes in general) after contracting the tensor $A$ by $\psi_1$. The straightforward generalisation of (9), (10) and of the second solution aspect, to the $k \geq 3$ case can be found in [16]. Through this recursive algorithm, two types of principal tensors can be found: the k-modes solutions when the constraint is expressed with an orthogonal-tensorial, and their associated k-modes solutions obtained by SVD-(k-1)modes. For example if $k=3$ one has for each 3-modes solutions, $3$ sets of associated 3-modes solutions: one set for each component of the 3-modes solution. If $k=4$ there are two levels of associations: each 4-modes principal tensor will have $4$ sets of associated principal tensors, each set being obtained by the tensor product of a component $s_h$ of this 4-modes principal tensor and the SVD-3modes solutions of $X..s_h$ (where $X$ is the initial tensor to analyse, and $s_h$ is the component in question), and then each SVD-3modes will also have associated solutions as described before. One can write the SVD-3modes of $A$ as an orthogonal decomposition :
\begin{displaymath}A=\sum_s \sigma_s \psi_s \otimes \varphi_s \otimes \phi_s
\end{displaymath} (11)

Because of some good properties of this method, mainly a generalised Eckart-Young theorem [16](i.e. nested model optimisation3, not usually found in other generalisation in the literature) we will confound the PTA-kmodes and SVD-kmodes like we do with PCA and SVD. The singular values obtained on k-modes solutions are treated in decreasing order, but for example, it happens often that a singular value obtained with an associated solution of the first (or $m^{th}$) k -modes solution is bigger than the singular value obtained with the second (or next one) k -modes solution. In the listings one must notice that for this reason, we kept the logical order of computation instead of the ``true" decreasing order of the singular values.
next up previous
Next: Handling PTA-kmodes method Up: Multiway multidimensional data reduction Previous: SVD within tensor algebra
Didier Leibovici 2001-09-04