next up previous
Next: SVD-kmodes for and Up: Multiway multidimensional data reduction Previous: Multiway multidimensional data reduction

SVD within tensor algebra framework

The first singular value of a data matrix $A$ is :
$\displaystyle \sigma_1$ $\textstyle =$ $\displaystyle \max_{{\scriptstyle
\begin{array}{l }
\scriptstyle \left\Vert \ps...
...yle \left\Vert \varphi \right\Vert _F =1
\end{array}}}A..(\psi \otimes \varphi)$  
  $\textstyle =$ $\displaystyle A..(\psi_1 \otimes \varphi_1) \quad (\mbox{ in tensor form})$  
  $\textstyle =$ $\displaystyle ^t\psi_1 A \varphi_1 \quad (\mbox{ in matrix form}).$ (5)

$\psi_1$ is termed first principal component, $\varphi_1$ first principal axis, $(\psi_1\otimes\varphi_1)$ will be called first principal tensor. Solving the problem associated with this maximisation leads to transition formulae and then to the classical eigenequations where $\psi_1$, $\varphi_1$ and $\sigma_1^2$ are the first eigenvectors and eigenvalue of the respective symmetric operators:
\begin{displaymath}
\left\{
\begin{array}{ll}
X..\varphi & =\sigma \psi  
...
... \\
^tXX\varphi & =\sigma^2 \varphi
\end{array} \right. .
\end{displaymath} (6)

To compute the solutions one can either use the eigenequations or execute an iterative algorithm using the transition formulae. To find the second and further solutions it is added an orthogonal constraints (uncorrelated vectors) onto the $\psi$ and $\varphi$ :
$\displaystyle \sigma_2$ $\textstyle =$ $\displaystyle \max_{{\scriptstyle
\begin{array}{l}
\scriptstyle \left\Vert \psi...
...box{ \tiny and } \varphi \perp \varphi_1
\end{array}}}A..(\psi \otimes \varphi)$  
  $\textstyle =$ $\displaystyle A..(\psi_2 \otimes \varphi_2).$ (7)

Here with $k=2$, the orthogonality constraint can be written either $\psi \perp \psi_1 \mbox{ and
} \varphi \perp \varphi_1$, or $(\psi \otimes \varphi)\in (\psi_1\otimes \varphi_1)^\perp$, or with the subspace termed orthogonal-tensorial of the first principal tensor $(\psi \otimes \varphi)\in \psi_1^\perp \otimes \varphi_1^\perp$.
The SVD is then written as an orthogonal decomposition of $A$,
\begin{displaymath}
A=\sum_{s=1}^{rank(A)}\sigma_s\psi_s\otimes \varphi_s=\sum_...
...}\sigma_s\psi_s
{\;}^t\varphi_s=\psi\Lambda^1/2{\;}^t\varphi
\end{displaymath} (8)

in tensor form, or in vector form, or in matrix form. Note that here (for 2 modes) the collection of $\psi_s$ and the collection of $\varphi_s$ give also orthogonal systems within the respective spaces ; that will not be generally the case for $k > 2$ modes.

next up previous
Next: SVD-kmodes for and Up: Multiway multidimensional data reduction Previous: Multiway multidimensional data reduction
Didier Leibovici 2001-09-04