FastICA

FastICA is an efficient and popular algorithm for independent component analysis invented by Aapo Hyvärinen at Helsinki University of Technology.^[1]^[2] Like most ICA algorithms, FastICA seeks an orthogonal rotation of prewhitened data, through a fixed-point iteration scheme, that maximizes a measure of non-Gaussianity of the rotated components. Non-gaussianity serves as a proxy for statistical independence, which is a very strong condition and requires infinite data to verify. FastICA can also be alternatively derived as an approximative Newton iteration.

Algorithm

Prewhitening the data

Let the $𝐗 := (x_{i j}) \in ℝ^{N \times M}$ denote the input data matrix, $M$ the number of columns corresponding with the number of samples of mixed signals and $N$ the number of rows corresponding with the number of independent source signals. The input data matrix $𝐗$ must be prewhitened, or centered and whitened, before applying the FastICA algorithm to it.

Centering the data entails demeaning each component of the input data $𝐗$ , that is,

x_{i j} \leftarrow x_{i j} - \frac{1}{M} \sum_{j^{'}} x_{i j^{'}}

for each

i = 1, \dots, N

and

j = 1, \dots, M

. After centering, each row of

𝐗

has an expected value of

0

.

Whitening the data requires a linear transformation $𝐋 : ℝ^{N \times M} \to ℝ^{N \times M}$ of the centered data so that the components of $𝐋 (𝐗)$ are uncorrelated and have variance one. More precisely, if $𝐗$ is a centered data matrix, the covariance of $𝐋_{𝐱} := 𝐋 (𝐗)$ is the $(N \times N)$ -dimensional identity matrix, that is,

E {𝐋_{𝐱} 𝐋_{𝐱}^{T}} = 𝐈_{N}

A common method for whitening is by performing an eigenvalue decomposition on the covariance matrix of the centered data

𝐗

,

E {𝐗 𝐗^{T}} = 𝐄 𝐃 𝐄^{T}

, where

𝐄

is the matrix of eigenvectors and

𝐃

is the diagonal matrix of eigenvalues. The whitened data matrix is defined thus by

𝐗 \leftarrow 𝐃^{- 1 / 2} 𝐄^{T} 𝐗 .

Single component extraction

The iterative algorithm finds the direction for the weight vector $𝐰 \in ℝ^{N}$ that maximizes a measure of non-Gaussianity of the projection $𝐰^{T} 𝐗$ , with $𝐗 \in ℝ^{N \times M}$ denoting a prewhitened data matrix as described above. Note that $𝐰$ is a column vector. To measure non-Gaussianity, FastICA relies on a nonquadratic nonlinear function $f (u)$ , its first derivative $g (u)$ , and its second derivative $g^{'} (u)$ . Hyvärinen states that the functions

f (u) = \log \cosh (u), g (u) = \tanh (u), and g^{'} (u) = 1 - \tanh^{2} (u),

are useful for general purposes, while

f (u) = - e^{- u^{2} / 2}, g (u) = u e^{- u^{2} / 2}, and g^{'} (u) = (1 - u^{2}) e^{- u^{2} / 2}

may be highly robust.^[1] The steps for extracting the weight vector $𝐰$ for single component in FastICA are the following:

Randomize the initial weight vector $𝐰$
Let $𝐰^{+} \leftarrow E {𝐗 g (𝐰^{T} 𝐗)^{T}} - E {g^{'} (𝐰^{T} 𝐗)} 𝐰$ , where $E {...}$ means averaging over all column-vectors of matrix $𝐗$
Let $𝐰 \leftarrow 𝐰^{+} / ‖ 𝐰^{+} ‖$
If not converged, go back to 2

Multiple component extraction

The single unit iterative algorithm estimates only one weight vector which extracts a single component. Estimating additional components that are mutually "independent" requires repeating the algorithm to obtain linearly independent projection vectors - note that the notion of independence here refers to maximizing non-Gaussianity in the estimated components. Hyvärinen provides several ways of extracting multiple components with the simplest being the following. Here, $𝟏_{𝐌}$ is a column vector of 1's of dimension $M$ .

Algorithm FastICA

Input:

C

Number of desired components

Input:

𝐗 \in ℝ^{N \times M}

Prewhitened matrix, where each column represents an

N

-dimensional sample, where

C < = N

Output:

𝐖 \in ℝ^{N \times C}

Un-mixing matrix where each column projects

𝐗

onto independent component.

Output:

𝐒 \in ℝ^{C \times M}

Independent components matrix, with

M

columns representing a sample with

C

dimensions.

 for p in 1 to C:
     $𝐰_{𝐩} \leftarrow$  Random vector of length N
    while  $𝐰_{𝐩}$  changes
         $𝐰_{𝐩} \leftarrow \frac{1}{M} 𝐗 g ({𝐰_{𝐩}}^{T} 𝐗)^{T} - \frac{1}{M} g^{'} ({𝐰_{𝐩}}^{T} 𝐗) 𝟏_{𝐌} 𝐰_{𝐩}$ 
         $𝐰_{𝐩} \leftarrow 𝐰_{𝐩} - \sum_{j = 1}^{p - 1} ({𝐰_{𝐩}}^{T} 𝐰_{𝐣}) 𝐰_{𝐣}$ 
         $𝐰_{𝐩} \leftarrow \frac{𝐰_{𝐩}}{‖ 𝐰_{𝐩} ‖}$ 

 output  $𝐖 \leftarrow [\begin{matrix} 𝐰_{𝟏}, \dots, 𝐰_{𝐂} \end{matrix}]$ 

 output  $𝐒 \leftarrow 𝐖^{𝐓} 𝐗$

References

1 2 Hyvärinen, A.; Oja, E. (2000). "Independent component analysis: Algorithms and applications" (PDF). Neural Networks. 13 (4–5): 411–430. doi:10.1016/S0893-6080(00)00026-5. PMID 10946390.
↑ Hyvarinen, A. (1999). "Fast and robust fixed-point algorithms for independent component analysis" (PDF). IEEE Transactions on Neural Networks. 10 (3): 626–634. doi:10.1109/72.761722. PMID 18252563.

External links

[Hyvarinen-1] 1 2 Hyvärinen, A.; Oja, E. (2000). "Independent component analysis: Algorithms and applications" (PDF). Neural Networks. 13 (4–5): 411–430. doi:10.1016/S0893-6080(00)00026-5. PMID 10946390.

[2] Hyvarinen, A. (1999). "Fast and robust fixed-point algorithms for independent component analysis" (PDF). IEEE Transactions on Neural Networks. 10 (3): 626–634. doi:10.1109/72.761722. PMID 18252563.

[1]

[2]