FastICA Algorithm

Summarizing the objective functions discussed above, we see a common goal of maximizing a function $\sum_i E\{ G(y_i) \}$, where $y_i={\mathbf w}_i^T {\mathbf x}$ is a component of ${\mathbf y}={\mathbf Wx}$

$$\sum_i E\{ G(y_i) \}=\sum_i E\{ G( {\mathbf w}_i^T {\mathbf x} ) \}$$

where ${\mathbf w}_i^T$ is the ith row vector in matrix ${\mathbf W}$. We first consider one particular component (with the subscript i dropped). This is an optimization problem which can be solved by Lagrange multiplier method with the objective function

$$O({\mathbf w})=E\{ G( {\mathbf w}^T {\mathbf x} ) \} -\beta( {\mathbf w}^T{\mathbf w}-1)/2$$

The second term is the constraint representing the fact that the rows and columns of the orthogonal matrix ${\mathbf W}$ are normalized, i.e., ${\mathbf w}^T{\mathbf w}=1$. We set the derivative of $O({\mathbf w})$ with respect to ${\mathbf w}$ to zero and get

$$F({\mathbf w})\stackrel{\triangle}{=} \frac{\partial O({\mat... ...mathbf x}g( {\mathbf w}^T {\mathbf x} ) \}-\beta {\mathbf w}=0$$

where $g(z)=dG(z)/dz$ is the derivative of function $G(z)$. This algebraic equation system can be solved iteratively by Newton-Raphson method:

$${\mathbf w} \Leftarrow {\mathbf w}-J_F^{-1}({\mathbf w}) F({\mathbf w})$$

where $J_F({\mathbf w})$ is the Jacobian of function $F({\mathbf w})$:

$$J_F({\mathbf w})=\frac{\partial F}{\partial {\mathbf w}}= E\{{\mathbf xx}^T g'({\mathbf w}^T{\mathbf x})\}-\beta{\mathbf I}$$

The first term on the right can be approximated as

$$E\{{\mathbf xx}^T g'({\mathbf w}^T{\mathbf x})\} \approx E\{... ...\mathbf x})\} =E\{g'({\mathbf w}^T{\mathbf x})\} {\mathbf I}$$

and the Jacobian becomes diagonal

$$J_F({\mathbf w})=[E\{g'({\mathbf w}^T{\mathbf x})\}-\beta] {\mathbf I}$$

and the Newton-Raphson iteration becomes:

$${\mathbf w} \Leftarrow {\mathbf w}-\frac{1}{E\{g'({\mathbf w}... ...mathbf x}g( {\mathbf w}^T {\mathbf x} ) \}-\beta {\mathbf w}]$$

Multiplying both sides by the scaler $\beta-E\{g'({\mathbf w}^T{\mathbf x})\}$, we get

$${\mathbf w} \Leftarrow E\{ {\mathbf x}g( {\mathbf w}^T {\mathbf x} ) \} -E\{g'({\mathbf w}^T{\mathbf x})\} {\mathbf w}$$

Note that we still use the same representation ${\mathbf w}$ for the left-hand side, while its value is actually multiplied by a scaler. This is taken care of by renormalization, as shown in the following FastICA algorithm:

1. Choose an initial random guess for ${\mathbf w}$
2. Iterate:
   
   $${\mathbf w} \Leftarrow E\{ {\mathbf x}g( {\mathbf w}^T {\mathbf x} ) \} -E\{g'({\mathbf w}^T{\mathbf x})\} {\mathbf w}$$
   
   

3. Normalize:
   
   $${\mathbf w} \Leftarrow {\mathbf w}/\vert\vert{\mathbf w}\vert\vert$$
   
   

4. If not converged, go back to step 2.

This is a demo of the FastICA algorithm.