数理解析研究所講究録 1246 巻 2002 年 19-30

19

On Some New Ideas and Algorithms for
Independent Component Analysis
Pando Georgiev \dag er and Andrzej Cichocki \dager
Abstract
arising
For every integer $p\geq 4$ , even, we consider aspecific optimization problem
from the blind source extraction problem (BSE) and prove that every local maximum ofis asolution of (BSE) in sense that it extracts one source signal from alinear mixture of$\mathrm{O}\mathrm{P}(\mathrm{p})$$\mathrm{O}\mathrm{P}(\mathrm{p})$with
unknown statistically independent signals. We construct an algorithm for solving
rate of convergence $p-1$ . We propose new sufficient conditions for separation of source signals,
stating that the separation is possible, if the source signals have different autocorrelation or
cumulant functions (depending on time delay). We show that the problem of blind source
separation of signals can be qonverted to asymmetric eigenvalue problem of ageneralized
cumulant matrices if these matrices have distinct eigenvalues. We propose new algorithms,
based on non-smooth analysis and optimization theory, which disperse the eigenvalues of thesegeneralized cumulant matrices.
$\mathrm{O}\mathrm{P}(\mathrm{p})$1Introduction
The problem of independent component analysis is formulated as follows: we observe sensor
signals (random variables) $\mathrm{x}(t)=[x_{1}(t), \ldots, x_{m}(t)]^{T}$ and want to represent them as linear
mixture of random variables $\mathrm{s}(t)=[s_{1}(t), \ldots, s_{n}(t)]^{T}$ , which are independent, as much as
possible:$\mathrm{x}(t)=\mathrm{A}\mathrm{s}$$(t)$$t\geq 0$(1),

where Ais $n\cross n$ non-singular matrix.
The problem of blind source extraction (BSE), which we shall consider, is formulated asfollows: for given source signals (random variables) $\mathrm{x}(t)=[x_{1}(t), \ldots, x_{m}(t)]^{T}$ and knowing thatthey are obtained as alinear mixture (1), the task is to findand the matrix A. In general thisis impossible, but if , $i=1$ , , are statistically independent and Ais nonsingular, then this ispossible up to permutation and scaling, i.e. we can obtain ADP, whereandare unknown, wherediagonal and permutation matrices respectively. Therefore, we can obtain
is a(unknown).
permutation of 1, ,(unknown) andare scaling coefficients
The literature about independent component analysis and BSE problem is huge (see for
instance [16] and references therein).
Here we generalize the algorithm of Hyvarinen and Oja [17] and prove rigorously its conditions for convergence. Even as amathematical problem this algorithm is interesting, since it
provides an example of an algorithm with arbitrarily fast convergence (defined in the beginning).
wheremeans the selfby
Define the function:(see [22] for definition and properties of the cumulants). Consider the
cumulant of ordermaximization problem$\mathrm{s}(t)$$s_{i}$$\ldots$$n$$\mathrm{D}$$\mathrm{P}$$d_{i}s_{p}.\cdot(t)$$\{$$\ldots$$n\}$$p_{i}$$d_{i}$$1\mathrm{R}^{n}arrow \mathrm{R}$$\varphi_{p}(\mathrm{w})=\mathrm{c}\mathrm{u}\mathrm{m}_{p}(\mathrm{w}^{T}\mathrm{x})$$\mathrm{c}\mathrm{u}\mathrm{m}_{p}$$\varphi_{p}$$p$$\mathrm{O}\mathrm{P}(\mathrm{p})$$n$:maximize$|\varphi_{p}(\mathrm{w})|$under constraint$||\mathrm{w}||=1$.

We shall see that this maximization problem has interesting properties, namely, it has exactly, ,, which are orthonormal. We can recover the original source signals up to
solutions$\mathrm{w}_{1}$$\ldots$$\mathrm{w}_{n}$20, $r_{i}\in\{1, \ldots, n\}$ . We construct an algorithm forsign and permutation:
one by one, which has rate of convergence $p-1$ .
, ,findingin order to extract one source from a
the idea of maximizing of cum4
that
We note[9].
linear mixture is already considered in
We need the following lemma, which is generalization of alemma in [9] (considered there
the case $p=4$ ).
$y_{i}(t)=\mathrm{w}_{i}^{T}\mathrm{x}(t)=\pm s_{r_{i}}(t)$$\mathrm{w}_{1}$$\ldots$$\mathrm{w}_{n}$$(\mathrm{w}^{T}\mathrm{x})$Lemma 1Consider the optimization problem: minimize (maximize)subject to $||\mathrm{v}||=c>0$ , where $p>2$ is even, where$\sum_{\dot{l}=1}^{n}k:v_{\dot{1}}^{\rho}$$\mathrm{v}=(v_{1}, \ldots, v_{n})$.

Denote $I^{+}=\{i\in\{1, \ldots, n\} : k_{i}>0\}$ , $I^{-}=\{i\in\{1, \ldots, n\} : k_{i}<0\}$ and $e:=(0, \ldots 0,1,0, \ldots, 0)$ , (1.
andis the -th place). Assume that$=\pm ce:$ , $i\in I^{-}$ and the points
Then the points of local minimum are exactly the vectors.
of local maxirnum are exactly the vectors $M_{j}^{\pm}=\pm cej,J*$$I^{-}\neq\emptyset$$I^{+}\neq\emptyset$$i$$m_{\dot{1}}^{\pm}$$\in I^{+}$

Proof. Applying the Lagrange multipliers theorem for apoint of alocal optimum$(\overline{v}_{1}, \ldots, \overline{v}_{m})$, we write:$k_{\dot{1}}d_{\dot{l}}^{-1}-2\lambda\overline{v}_{\dot{l}}=0$, $i=1$ ,$\ldots$$\overline{v}=$(2), $m$ ,

where Ais aLagrange multiplyer.
and summing, we obtain:
Multiplying (1) by$\overline{v}_{\dot{1}}$$pf_{\varphi t}$.

$=2\lambda c^{2}$,

where fapt. means the value of $f$ at the local optimum. Hence(3)$\lambda=\frac{p}{2c^{2}}f_{\varphi t}.\cdot$

From (1) we obtain$\overline{v}_{\dot{1}}(t:\Psi_{\dot{1}}^{-2}-\frac{p}{c^{2}}f_{\varphi t}.)=0$

whence$\overline{v}_{\dot{1}}$is either 0, or(4)$\pm(\frac{f_{\varphi t}}{k_{\dot{l}}c^{2}}.)^{\frac{1}{p-2}}$

Case 1. Assume that $k_{i_{0}}<0$ for some index and is alocal minimum. Then obviously
is local minimum. $<0$ . According to the second order optimality condition [1], apoint$i_{0}$$\overline{v}$$x^{0}$$f_{loc.\min}$if$h^{T}L’(x^{0})h>0$$\forall h\in K(x^{0})=\{h:h^{T}x^{0}=0\}$, $h\neq 0$ ,where
$L(x)= \sum_{i=1}^{n}k:x_{i}^{p}-\lambda(||x||^{2}-c^{2})$is the Lagrange function.
In our case, by (2) and (3) we obtain$h^{T}L’(\overline{v})h$

$=$

$=$

(5)

$\sum_{\dot{l}=1}^{n}(p(p-1)k_{\dot{\iota}}\theta_{\dot{l}}^{-2}-2\lambda)h_{\dot{l}}^{2}$$\frac{p}{c^{2}}f_{lo\mathrm{c}.m\dot{\iota}n}.[(p-2)\sum_{i\in J}h_{\mathrm{i}}^{2}-\sum_{\dot{|}\not\in I}h_{i}^{2}]$,21where I is the set of those indeces , for which is different from 0.
We shall check this second order optimality condition for the points
$Vi$

$i$

$K(m_{i_{0}}^{\pm})=\{h :therefore, for$h\in K(m_{i_{0}}^{\pm})$h_{i_{0}}=0\}$$m_{i_{0}}^{\pm}$. We have,, $h\neq 0$ we have$h^{T}L’\langle(m_{i_{0}}^{\pm})h>0$,

since $h_{i_{0}}=0$ and $f_{loc.\min}$ . $<0$ .
}By (4) it follows that any other vecto With at least twoelements is )local
minimum.
Case 2. Assume that $k_{j}>0$ and is alocal maximum. We apply Case 1to the function$-f$ and finish the proof.
’$\mathrm{a}^{1}$$\mathrm{n}\mathrm{o}\mathrm{n}\mathrm{z}\mathrm{e}_{i}\mathrm{r}‘ 0^{l}$$\mathrm{n}\mathrm{l}$$\mathrm{t}$$\mathrm{r}_{1}$.

$\overline{v}$

Theorem 2Assume that the matrix Ain (1) is orthogonal. Then(a) the maximization problem $OP(p)$ has exactly solutions, ,, which are$mal$ ;(b) We can recover the original source signals up to sign and permutation:$n$$\mathrm{w}_{1}$$\ldots$$\mathrm{w}_{n}$$ohh\sigma no\mathit{7}^{L}$$y_{i}(t)=\mathrm{w}_{i}^{T}\mathrm{x}(t)=$$\pm s_{r_{i}}(t)$, $r_{i}\in\{1, \ldots, n\}$ .

$l$

Proof. Consider the maximization problem:
maximize
under constraint
,
where
.
It is easy to see that the problems
andare equivalent in sense thatisasolution of
if and only if
is asolution ofBy.
the properties of the
cumulants [5], we have.’$(\mathrm{D}\mathrm{P}(\mathrm{p}))$$|\psi_{p}(\mathrm{c})|$$||\mathrm{c}||=1$$f$$\psi_{p}(\mathrm{c})=\mathrm{c}\mathrm{u}\mathrm{m}_{p}\sum_{i=1}^{n}c_{i}s_{i}$$(\mathrm{D}\mathrm{P}(\mathrm{p}))$$\mathrm{O}\mathrm{P}(\mathrm{p})$$\mathrm{w}_{0}$$\mathrm{O}\mathrm{P}(\mathrm{p})$$\mathrm{c}_{0}=\mathrm{A}\mathrm{w}\mathrm{o}$$(\mathrm{D}\mathrm{P}(\mathrm{p}))$$\cdot\}$$\psi_{p}(\mathrm{c})=\mathrm{c}\mathrm{u}\mathrm{m}_{p}(\sum_{i=\mathrm{I}}^{n}c_{i}s_{i})=\sum_{i=1_{\mathrm{v}}}^{n}c_{i}^{p}\mathrm{c}\mathrm{u}\mathrm{m}_{p}(s_{i})$Applying Lemma 1we obtain that$\pm \mathrm{e}_{i}$.

$\cdot$,,has solutions, which are exactly the vectors
within -th place and 0in the other places. Now the conclusion of (a) is evident.
(b) The assertion is evident.
$\pm 1$.

$i$

2Algorithm with high order
Denoting,
we have
Consider the following algorithm:$y=\mathrm{w}^{T}\mathrm{x}$$\mathrm{c}=\mathrm{A}^{T}\mathrm{w}$$n$$(\mathrm{D}\mathrm{P}(\mathrm{p}))$$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{e}\mathrm{r}^{\mathrm{I}}\mathrm{g}\mathrm{e}^{t}$$y= \mathrm{c}^{T}\mathrm{s}=\sum_{i=1}^{n}c_{i}s_{i}$$\mathrm{w}(l)=.\frac{\varphi_{p}’(\mathrm{w}(l-1))}{||\varphi_{p}’(\mathrm{w}(l-1))||,\backslash 1}-,$

where$\varphi_{p}(\mathrm{w})=\mathrm{c}\mathrm{u}\mathrm{m}_{p}(.\mathrm{w}^{T}.\mathrm{x})\mathrm{t}$Theorem 3Assume that$g\iota^{1},ven$,$\mathrm{c}\mathrm{u}\mathrm{n}^{\iota}1(p\dot{s}_{i}^{\mathit{1}})r\neq 0$

nce speed’.

$l=1$ , 2,$\ldots$

,

(6)

.

are statistically independent, zero mean signals. Let $p\geq 4$ , even, be, $i=1$ , , $nar\iota dl,et$.
be the set of$s_{i}$$\prime I.(\begin{array}{l}\prime\mathrm{c}\end{array})$$:= \arg\max’ c_{i}|\mathrm{c}\mathrm{u}‘ \mathrm{m}_{p},(s_{i})\uparrow^{\frac{1}{p-2}}1<i\leq n_{f\downarrow}$$\ldots$$L^{\mathrm{I}}etW\circ|$

all elements
such that, the setcontains only
elements sayand. Then(a) The complement ofhas measure zero.
(b) Ifthen $\lim_{l\neg\infty}y_{l}(t)=\pm s_{i_{0}}(t)$ for ever$ryk=1,2$ , ’where y%{t)and $i_{0}=i(\mathrm{w}(0))$ .
(c) The rate of convergence in (b) is of order $p-1$ .
$\mathrm{w}\in 1\mathrm{R}^{n}$$||\mathrm{w}||=1$$I(\mathrm{A}^{\overline{T}}\mathrm{w})$$0\eta e$$i(.\mathrm{w})$,$c_{i(\mathrm{w})}\neq 0$$W_{0}$$\mathrm{w}(0)\in W_{0}$$=\mathrm{w}(l)^{T}\mathrm{x}(t)$$..I_{\backslash }$22
Proof.
,
is afinite union of proper subspaces of(a) It is easy to see that the complement of
therefore this union has measure zero.
(b), (c). By the properties of the cumulants, since , $i=1$ , , are statistically independent(see [22]), we have:$\mathrm{R}^{n}$$W_{0}$$s_{i}$$\mathrm{c}\mathrm{u}\mathrm{m}_{p}(\cdot\sum_{\dot{|}=1}^{n}c.s_{\dot{1}})=\sum_{\dot{\iota}=1}^{n}c_{\dot{1}}^{\rho}\mathrm{c}\mathrm{u}\mathrm{m}_{p}(s:)$

DefineSince$\psi_{p}(\mathrm{A}^{T}\mathrm{w})$with respect to$\varphi_{p}’(\mathrm{w})$$\mathrm{w}$.

is given by (6).
, where, and, using the chain rule for differentiating the composite function$\mathrm{c}(l)=\mathrm{A}^{T}\mathrm{w}(l)$$\psi_{p}(\mathrm{c})=\sum_{\dot{l}=1}^{n}c_{\dot{1}}^{\rho}\mathrm{c}\mathrm{u}\mathrm{m}_{p}(s:)$$\varphi_{p}(\mathrm{w})=\psi_{p}(\mathrm{A}^{T}\mathrm{w})$$n$$\ldots$$\mathrm{w}(l)$, we obtain:$=\mathrm{A}\psi_{p}’(\mathrm{c})=p\mathrm{A}(c_{1}^{\rho-1}\mathrm{c}\mathrm{u}\mathrm{m}_{p}(s_{1}),$,$\ldots$(7)$c_{n}^{\mathrm{p}-1}\mathrm{c}\mathrm{u}\mathrm{m}_{p}(s_{n}))^{T}$

thereforeAc(l)since Ais orthogonal.
Multiplying (8) by$\mathrm{A}^{T}$$=$$\mathrm{w}(l)=\frac{\varphi_{p}’(\mathrm{w}(l-1))}{||\varphi_{p}’(\mathrm{w}(l-1))||}$$=$$\frac{\mathrm{A}\psi_{p}’(\mathrm{c}(l-1))}{||\mathrm{A}\psi_{p}(\mathrm{c}(l-1))||}$$=$$\frac{\mathrm{A}\psi’(\mathrm{c}(l-1))}{||\psi(\mathrm{c}(l-1))||}$

,

(8)

.

,

we obtain$\mathrm{c}(l)$$=$$\frac{\psi’(\mathrm{c}(l-1))}{||\psi(\mathrm{c}(l-1))||}$

(9)

,

or
$\mathrm{q}(l)$$=$$\frac{\sigma_{\dot{1}}p|\mathrm{c}\mathrm{u}\mathrm{m}_{p}(s_{\dot{1}})|\mathrm{q}(l-1)^{p-1}}{||\psi’(\mathrm{c}(l-1))||}$$\forall i=1$,$\ldots,n$

(10)

,

.
where $\sigma:=sign$
Prom (10) we obtain$\mathrm{c}\mathrm{u}\mathrm{m}_{p}(s:)$$\mathrm{q}(l)|\mathrm{c}\mathrm{u}\mathrm{m}_{p}(s_{i})|^{\frac{1}{p-2}}=\frac{\sigma_{\dot{1}}[\mathrm{q}(l-1)|\mathrm{c}\mathrm{u}\mathrm{m}_{p}(s_{\dot{1}})|^{\frac{1}{p-2}}]^{p-1}}{||(c_{1}(l-1)^{p-1}\mathrm{c}\mathrm{u}\mathrm{m}_{p}(s_{1}),\ldots,c_{n}(l-1)^{p-1}\mathrm{c}\mathrm{u}\mathrm{m}_{p}(s_{n}))^{T}||}$

From (11) it follows by induction that if the initial conditions satisfy
some $i\in\{1, \ldots, n\}$ , then the denominator in (11) is not zero for every $l\geq 0$ , so
, we obtain:
defined. Hence, if

.

(11)

for
in (8) is well$\mathrm{q}.(0)\mathrm{c}\mathrm{u}\mathrm{m}_{p}(s:)\neq 0$$\mathrm{w}(l)$$\mathrm{w}(0)\in W_{0}$$\frac{\mathrm{q}(l)}{\%(l)}(\frac{|\mathrm{c}\mathrm{u}\mathrm{m}_{p}(s_{i})|}{|\mathrm{c}\mathrm{u}\mathrm{m}_{p}(s_{\dot{l}_{0}})|})^{\frac{1}{p-2}}=\frac{\sigma_{\dot{l}}}{\sigma_{i_{0}}}[\frac{\mathrm{q}(i-1)}{c_{10}(l-1)}(\frac{|\mathrm{c}\mathrm{u}\mathrm{m}_{p}(s_{\dot{l}})|}{|\mathrm{c}\mathrm{u}\mathrm{m}_{p}(s_{\dot{1}0})|})^{\frac{1}{p-2}}]^{p-1}$

(12)

23
Now by (12) one proves easily by induction that for every $l\geq 0$ and every $i=1$ ,$\frac{c_{i}(l)}{c_{i_{0}}(l)}(\frac{|\mathrm{c}\mathrm{u}\mathrm{m}_{p}(s_{i})|}{|\mathrm{c}\mathrm{u}\mathrm{m}_{p}(s_{i_{0}})|})\frac{1}{\mathrm{p}-2}$$=$$\ldots$

,

$n$

(13)

$( \frac{\sigma_{i}}{\sigma_{i_{0}}})^{l}[\frac{c_{i}(0)}{c_{i_{0}}(0)}(\frac{|\mathrm{c}\mathrm{u}\mathrm{m}_{p}(s_{i})|}{|\mathrm{c}\mathrm{u}\mathrm{m}_{p}(s_{i_{0}})|})\frac{1}{p-2}](p-1)^{l}$

From (13) it follows thatwhenfor
as the speed of the convergence is $p-1$ . Thus we proved:$larrow\infty$$c_{i}(l)arrow \mathrm{O}$$i\neq i_{0}$md(since$|c_{i_{\mathrm{O}}}(l)|arrow 1$$\lim_{larrow\infty}y_{l}(t)=\lim_{larrow\infty}\mathrm{w}^{T}(l)\mathrm{x}(t)=\lim_{larrow\infty}\mathrm{c}^{T}(l)\mathrm{s}(t)=\pm s_{i_{0}}(t)$$\forall k=1$

, 2,$\ldots$$||\mathrm{c}(l)||=1$),.

Similar algorithm can be used for cumulants involving time delays:$\mathrm{c}\mathrm{u}\mathrm{m}_{p}\{s_{i}, s_{i}, s_{i}($. $-p), s_{i}($ . $-p)\}$ .

This will allows to extract signals having non-zero cumulants (depending on time delays).

3

Cumulant matrices

We will consider the case of cumulants of order four for simplicity. Define (like in [6], but here
using time delays) a 4-th order cumulant matrixof the sensor signals as follows:$\mathrm{C}_{\mathrm{x},\mathrm{x}_{p}}^{2,2}(\mathrm{B})$(14)$\mathrm{C}_{\mathrm{x},\mathrm{x}_{p}}^{2,2}(\mathrm{B})=E\{\mathrm{x}\mathrm{x}^{T}\mathrm{x}_{p}^{T}\mathrm{B}\mathrm{x}_{p}\}-E\{\mathrm{x}\mathrm{x}^{T}\}\mathrm{t}\mathrm{r}(\mathrm{B}E\{\mathrm{x}_{p}\mathrm{x}_{p}^{T}\})$$-E\{\mathrm{x}\mathrm{x}_{p}^{T}\}\mathrm{B}E\{\mathrm{x}_{p}\mathrm{x}^{T}\}-E\{\mathrm{x}\mathrm{x}_{p}^{T}\}\mathrm{B}^{T}E\{\mathrm{x}_{p}\mathrm{x}^{T}\}$

,
,
,
where
is a matrix,
and $E$ is themathematical expectation (with respect to ). Similarly, define a fourth order cumulant matrixof the source signals , $i=1$ , , .
Assume that the additive noise has independent Gaussian components (with zero means),
which are independent also with , $i=1$ , , . It is easy to see that the $(i, j)$ -th element ofis$\mathrm{B}\in \mathrm{R}^{n^{2}}$$\mathrm{x}_{p}=\mathrm{x}(t-p)$$\mathrm{x}=\mathrm{x}(t)$$\mathrm{s}_{p}=\mathrm{s}(t-p)$$\mathrm{s}=\mathrm{s}(t)$$t$$\mathrm{C}_{s,\mathrm{s}_{p}}^{2,2}(\mathrm{B})$$\mathrm{s}_{i}$$\ldots$$n$$\mathrm{n}$$s_{i}$$\ldots$$n$$\mathrm{C}_{\mathrm{x},\mathrm{x}_{p}}^{2,2}(\mathrm{B})$$C_{\mathrm{x},\mathrm{x}_{p}}^{2,2}( \mathrm{B})_{i,j}=\sum_{k,l=1}^{n}\mathrm{c}\mathrm{u}\mathrm{m}\{x_{i}(t), x_{j}(t), x(t-p), x(t-p)\}B_{k,l}$where
In the sequel we suppose that,

denotes the fourth order cumulant.
, $i=1$ , , are statistically independent. Then we have:$\mathrm{c}\mathrm{u}\mathrm{m}\{x_{\dot{\iota}}(t), x_{j}(t), x_{k}(t-p), x_{l}(t-p)\}$$\mathrm{s}_{i},$$\ldots$$n$$\mathrm{C}_{\mathrm{x},\mathrm{x}_{p}}^{2,2}(\mathrm{B})=\mathrm{H}\Delta(\mathrm{B})\mathrm{H}^{T}$

,

(15)

$\Delta(\mathrm{B})=diag\{\mathrm{c}\mathrm{u}\mathrm{m}_{s_{1}}(p)\mathrm{h}_{*1}^{T}\mathrm{B}\mathrm{h}_{*1}, \ldots, \mathrm{c}\mathrm{u}\mathrm{m}_{s_{n}}(p)\mathrm{h}_{*n}^{T}\mathrm{B}\mathrm{h}_{*n}\}$

,

(16)

where
and
denotes the -th column of
H. Therefore, if the mixing matrix
is orthogonal, we can separate the sources by eigenvalue
decomposition of(if its eigenvalues are distinct), which estimates up to multiplication
with permutation and diagonal sign matrices. Below we show how to disperse its eigenvalues, if$\mathrm{c}\mathrm{u}\mathrm{m}_{s}(:p)=\mathrm{c}\mathrm{u}\mathrm{m}\{s_{i}(k), s_{i}(k), s_{i}(k-p), s_{i}(k-p)\}$$i$$\mathrm{h}_{*i}$$\mathrm{H}$$\mathrm{C}_{\mathrm{x},\mathrm{x}_{p}}^{2,2}(\mathrm{B})$$\mathrm{H}$24
4Subdifferential algorithms for dispersing the eigenvalues
for which the eigenvalues
Cardoso [6] mentioned (without proof), that the set of matrices) has measure zero.
measure, that is, its complement (inare distinct, hasofis non-empty, due to theThis fact is an easy exercise, based on the observations thatis afinite union of proper subspaces,
non-singularity of , and 2): the complement of inin order to achieve
therefore, with measure zero. This suggests random choice of matrix
separation. But, as it was mentioned by Cardoso in [6], we need more in practice, because thealgorithms use only sample estimates of the cumulant matrices and asmall error in the sample
estimate could produce alarge deviation of the eigenvectors, if the eigenvalues are not well enoughseparated.
We present algorithm which ensures enough separation of the eigenvalues of the matrix. For its derivation (which is omitted because of limited space) we use the notions andfacts from the non-smooth analysis and the optimization theory, contained in [8] and [11].
:Consider the$B$$\mathrm{B}$$\mathrm{R}^{n^{2}}$$\mathrm{f}\mathrm{u}\mathrm{u}$$\mathrm{C}_{\mathrm{z},\mathrm{z}_{p}}^{2,2}(\mathrm{B})$$1\rangle:B$$\mathrm{R}^{n^{2}}$$B$$\mathrm{H}$$\mathrm{B}$$\mathrm{C}_{\mathrm{z},\mathrm{z}_{p}}^{2,2}(\mathrm{B})$$\mathrm{f}\mathrm{u}\mathrm{n}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$‘$\varphi(\mathrm{B})=.\dot{\mathrm{m}}\mathrm{n}\{\lambda:(\mathrm{B})-\lambda 1\leq|\leq m-1:+1(\mathrm{B})\}$

,

(17)

.

$\mathrm{i}$. Every eigenvalue
are the eigenvalues (in decreasing order) of the matrix
where
can be expressed by Fisher’s minimax theorem [18].
, i.e.
for $t>^{-}0$ . It is enough to findThis function is positively
eigenvalues.
separation
Below we proposeof thean accent direction of this function to achieve
an algorithm for finding an accent direction. We point out that this not the steepest accent
direction, although we qan find this steepest accent direction with amore complicated algorithm.
The following lemma gives accent directions of anonsmooth function.
$\mathrm{C}_{\mathrm{z},\mathrm{z}_{p}}^{2,2}(\mathrm{B})$$\lambda_{i}(\mathrm{B})$$\varphi(t\mathrm{B})=t\varphi(\mathrm{B})$$\mathrm{h}\mathrm{o}\mathrm{m}\mathrm{o}\mathrm{g}\mathrm{e}^{\mathrm{t}}\mathrm{n}\mathrm{e}\mathrm{o}\mathrm{u}\mathrm{s}$$\mathrm{d}$$\mathrm{l}\mathrm{i}\mathrm{s}$is a localfy Lipschitz fun.c tion, regular in sense of Clarkq
Lemma 4Assume that :be any nonzero $ele$ ment
. Let Of (b) mean the Clarke subdifferential of at and$i.e$,. is direction in which the function can increaseof Of(b). Then$\mathrm{R}^{L}arrow \mathrm{R}$

$f$

$f$

$/\mathit{8}J$$\sup_{t>0}f(\mathrm{b}+t\mathrm{d})>f(\mathrm{b})$$\mathrm{b}$$\mathrm{d}\in\partial f(\mathrm{b})$$\mathrm{d}$strictly.

1

Proof. By the properties of the regular locally Lipschitz functions (see [8]), we have:$\lim_{tarrow 0_{+}}\frac{f(\mathrm{b}+t\mathrm{d})-f(\mathrm{b})}{t}--f’(\mathrm{b};\mathrm{d})=\max_{\mathrm{c}\in\partial f(\mathrm{b})}\cdot \mathrm{d}^{T}\mathrm{c}\geq||\mathrm{d}||^{\mathfrak{B}}>0$

The derivation of the$\mathrm{s}_{1}\mathrm{u}$bdifferential$\partial\varphi(\mathrm{B})$.

$\blacksquare$

is complicated and is given by the formull:

(18)
,
,
},
.
,
is the set where theis amatrix with $(k, l)$ -th element
where
corresponding toeigenvectors
unit
of
,
of
ail
is the set
minimum in (17) is$zk(t-p)$ , $zl(t-p))$element,
is the matrix withthe eigenvalue
uses subdifferential calculus for functions
and $co$ denotes the closed convex hull.
of -type, applied in our case for the function in Fisher minimax formula.
The foUowing.algorithm is based on formlla la (18) and Lemma (4).
.
1. Start from arbitrary, where Ais adiago
2. Perform an EVD of the matrix
are
of
and
the columns ofeigenvalues
nal matrix whose diagonal elements are the, then stop. Otherwise go to 3.
. If
eigenvectors of$\partial\varphi(\mathrm{B})=\overline{co}\{\mathrm{R}(\mathrm{u},.\mathrm{v})\}$:$\mathrm{u}\in \mathrm{y}_{:}$$\cdot \mathrm{v}$$\in \mathrm{v}_{i^{:}}$$i\in I_{0}$$\mathrm{v}^{T}\mathrm{Q}_{k,l}\mathrm{v}-\mathrm{u}^{T}\mathrm{Q}_{k,l}\mathrm{u}$$\mathrm{R}(\mathrm{u}, \mathrm{v})$$\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{a}\tilde{\mathrm{l}}\mathrm{n}\mathrm{e}.\mathrm{d}$$\lambda_{i}(\mathrm{B})$$\mathrm{C}_{\mathrm{z},\mathrm{z}_{p}}^{2,2}(\mathrm{B})$$\mathrm{V}_{i}$$(r, s)- \mathrm{t}\mathrm{h}|$$\mathrm{Q}k,l$$I_{0}$$\mathrm{c}\mathrm{u}\mathrm{m}(z_{r}(t), z_{s}(t),$$\mathrm{T}\mathrm{b}\mathrm{e}\mathrm{d}\mathrm{e}\mathrm{r}_{1}\mathrm{i}\mathrm{v}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$$\sup$$\mathrm{B}\in \mathrm{R}^{n^{2}}$$\mathrm{C}_{\mathrm{z},\mathrm{z}_{p}}^{2,2}(\mathrm{B}):\mathrm{C}_{\mathrm{z},\mathrm{z}_{\mathrm{p}}}^{2,2}(\mathrm{B})=\mathrm{U}\mathrm{A}\mathrm{U}^{T}$$\mathrm{C}_{\mathrm{z},\mathrm{z}_{p}}^{2,2}(\mathrm{B})$$\mathrm{C}_{\mathrm{z},\mathrm{z}_{p}}^{2,2}(\mathrm{B})$$\varphi(\mathrm{B})>0$$\mathrm{U}$25
3. Let, i cE I c{1,
, C I has multiplicity$A_{z}\ovalbox{\tt\small REJECT}(\mathrm{B})$be the set of non-distinct eigenvalues of
2. Calculate the-matriceswith$77\mathrm{Z}_{\ovalbox{\tt\small REJECT}}\ovalbox{\tt\small REJECT}’\}$\ldots ,$\ovalbox{\tt\small REJECT}$$\mathrm{A}_{\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}},(\mathrm{B})$$m_{\ovalbox{\tt\small REJECT}},\ovalbox{\tt\small REJECT}$, i.e. every-th element$\mathrm{C}:_{\ovalbox{\tt\small REJECT}}:_{p}(\mathrm{B})$$77_{\ovalbox{\tt\small REJECT}}\mathrm{x}\mathrm{y}\mathrm{z}$$\mathrm{W}.\ovalbox{\tt\small REJECT}$$(k\ovalbox{\tt\small REJECT}, \mathrm{X})$$W_{i,j}(k, l)=\mathrm{u}_{i,j}^{T}\mathrm{Q}_{k,l}\mathrm{u}_{i,j}$

where $Uij,j=1$ , ,are the eigenvectors among the columns ofcorresponding to theeigenvalue, $i\in I$ .
4. Choose amatrix (denoted by D) with maximal norm among.the matrices {:, $r=1$ , ,, $i\in I$ } and compute the new matrix as, where $0<\theta\leq 1$ .
Then
, i.e. the eigenvalues ofare distinct.
In the following theorem we show how to disperse two equal eigenvalues. This is an independent proof for the validity of the above algorithm for this case and gives an idea why the$m_{i}$$\ldots$$\mathrm{U}$$lj$$\lambda_{i}(\mathrm{B})$$\mathrm{W}_{i,j}-\mathrm{W}_{i,r}$$j$$\mathrm{B}_{*}=\mathrm{B}+\#\mathrm{D}$$m_{i}$$\ldots$$\varphi(\mathrm{B}_{*})>0$

matrix$\mathrm{D}$$\mathrm{c}_{\mathrm{z},\mathrm{z}_{p}}^{2,2}(\mathrm{B}_{*})$

has such aform.

Theorem 5Assume that the eigenvalues, $i=1$ , , yn of the matrix,
are ordered in decreasing order, Aj (B) has multiplicity 2, $i.e$ .
,
some
,
for
are $two$ unit linearly independent eigenvectors of
responding toand. Then, for any
we have, where the components ofareI$\lambda_{i}(\mathrm{B})$$\mathrm{C}_{\mathrm{z},\mathrm{z}_{\mathrm{p}}}^{2,2}(\mathrm{B})$$\mathrm{B}\in \mathrm{R}^{n^{2}}$$\ldots$$\lambda_{j}(\mathrm{B})=\lambda_{j+1}(\mathrm{B})$$j$$\mathrm{u}_{j}$$\mathrm{u}j+1$$\mathrm{C}_{\mathrm{z},\mathrm{z}_{p}}^{2,2}(\mathrm{B})co$$\lambda_{j}(\mathrm{B})$$\lambda_{j}(\mathrm{B}+\theta \mathrm{D})$$\theta\neq 0$$\mathrm{c}\mathrm{u}\mathrm{m}_{s_{i}}(p).\mathrm{c}\mathrm{u}\mathrm{m}_{s_{i+1}}(p)\neq 0$$\mathrm{D}$$\lambda_{j\dagger 1},(\mathrm{B}+\theta \mathrm{D})$(19)$D_{k,l}=\mathrm{u}_{j}^{T}\mathrm{Q}_{k,l}\mathrm{u}_{j}-\mathrm{u}_{j+1}^{T}\mathrm{Q}_{k,l}\mathrm{u}_{j+1}$

and$Q_{k,l}$are defined after for mula (18).

Proof. We have$\mathrm{C}_{\mathrm{z},\mathrm{z}_{p}}^{2,2}(\mathrm{B})=\mathrm{A}\triangle(\mathrm{B})\mathrm{A}^{T}$$\triangle(\mathrm{B})\cdot=diag$$(\mathrm{c}\mathrm{u}\mathrm{m}_{s_{1}}(p)\mathrm{a}_{*1}^{T}\mathrm{B}\mathrm{a}_{*1}$,$\ldots$

Since Ais orthogonal, the eigenvalues of the matrices
Since
has multiplicity 2, we have

,

,

(20)

$\mathrm{c}\mathrm{u}\mathrm{m}_{s_{n}}(p)\mathrm{a}_{*n}^{T}\mathrm{B}\mathrm{a}_{*n})$$\mathrm{C}_{\mathrm{z},\mathrm{z}_{p}}^{2,2}(\mathrm{B}+\theta \mathrm{D})$

and

.

(21)

$\Delta(\mathrm{B}+\theta \mathrm{D})$coincide.

$\lambda_{j}(\mathrm{B})$$\mathrm{A}^{T}\mathrm{u}_{j}=\alpha_{1}\mathrm{e}_{\mathrm{j}}+\alpha_{2}\mathrm{e}_{j+1}$

for some , , ,. By (19) we have$\alpha_{1}$$\alpha_{2}$$\beta_{1}$$\beta_{2}$, where$\mathrm{e}_{j}=$,$\mathrm{A}^{T}\mathrm{u}_{j^{1}+1}=\beta_{1}.\mathrm{e}_{j}+\beta_{2}\mathrm{e}_{j+1}$$(0, \ldots 0,1, 0, \ldots, 0)$,, 1 is in the -th place and$j$$\alpha_{1}^{2}+\alpha_{2}^{2}=\beta_{1}^{2}.+\beta_{2}^{2}||=$$1$$D_{k,l}=\mathrm{u}_{j}^{T}\mathrm{Q}_{k,l}\mathrm{u}_{j}$”$\mathrm{u}_{j+1}^{T}\mathrm{Q}_{k,l}\mathrm{u}_{j+1}-\neg$.

$\sum \mathrm{c}\mathrm{u}\mathrm{m}\{z_{r}(t), z_{s}^{i}(t), z_{k}(t-p), z_{l}(t-(P)\}(u_{j,r},u_{j,s}-u_{j+1,r},u_{j+1,s})n$$r,s=1$Hence we obtain:”$\mathrm{D}=\mathrm{A}diag$ $\{\mathrm{c}\mathrm{u}\mathrm{m}_{s_{1}}(p)\mathrm{a}_{*1}^{T}\mathrm{V}\mathrm{a}_{*1}$,$\ldots$,$\mathrm{c}\mathrm{u}\mathrm{m}_{\mathrm{s}_{\mathrm{n}}}$$(p)\mathrm{a}_{*n}^{T}\mathrm{V}\mathrm{a}_{*n}\}\mathrm{A}^{T}$

where
is amatrix with elements $V_{r,s}\downarrow=u_{j,r}u_{j,s}-u_{j+1,r}u_{j+1,s}$ andBy (20), (21) we have$\mathrm{V}$$\mathrm{C}_{\mathrm{z},\mathrm{z}_{p}}^{2,2}(\mathrm{B}+\theta \mathrm{D})$$=$$\mathrm{A}^{\mathrm{t}}diag\{\mathrm{c}\mathrm{u}\mathrm{m}_{s_{1}}(p)\mathrm{a}_{*1}^{T}(\mathrm{B}+\theta \mathrm{D})\mathrm{a}_{*1},$$=$$\mathrm{A}(\mathrm{C}_{\mathrm{z},\mathrm{z}_{p}}^{2,2}(\mathrm{B})+\theta diag\{\mathrm{c}\mathrm{u}\mathrm{m}_{s_{1}}(p)\mathrm{a}_{*1}^{T}\mathrm{D}\mathrm{a}_{*1},$,is the -ih column of A.
$\mathrm{i}$$\mathrm{a}_{*i}$!

$\mathrm{c}\mathrm{u}\mathrm{m}_{s_{n}}(p)\mathrm{a}_{*n}^{T}(\mathrm{B}+\theta \mathrm{D})\mathrm{a}_{*n}\}\mathrm{A}^{T}$\ldots ,\ldots ,.

$\mathrm{c}\mathrm{u}\mathrm{m}_{s_{n}}\mathrm{a}_{*n}^{T}\mathrm{D}\mathrm{a}_{*n}\})\mathrm{A}^{T}$

26
The theorem$\mathrm{w}\mathrm{i}\mathrm{U}$be proved, if$\mathrm{c}\mathrm{u}\mathrm{m}_{s_{j}}(p)\mathrm{a}_{*j}^{T}\mathrm{D}\mathrm{a}_{*j}\neq \mathrm{c}\mathrm{u}\mathrm{m}_{s_{j+1}}(p)\mathrm{a}_{*j+1}^{T}\mathrm{D}\mathrm{a}_{*j+1}$.

We calculate:$\mathrm{c}\mathrm{u}\mathrm{m}_{s_{j}}(p)\mathrm{a}_{*j}^{T}\mathrm{D}\mathrm{a}_{*j}$$=$$\mathrm{c}\mathrm{u}\mathrm{m}_{s_{j}}(p)\mathrm{a}_{*j}^{T}\mathrm{A}diag\{\mathrm{c}\mathrm{u}\mathrm{m}_{s_{1}}(p)\mathrm{a}_{*1}^{T}\mathrm{V}\mathrm{a}_{\mathrm{s}1}, \ldots, \mathrm{c}\mathrm{u}\mathrm{m}_{s_{n}}(p)\mathrm{a}_{*n}^{T}\mathrm{V}\mathrm{a}_{\mathrm{s}n}\}\mathrm{A}^{T}\mathrm{a}_{*j}$$=$$\mathrm{c}\mathrm{u}\mathrm{m}_{s_{j}}(p)\mathrm{e}_{j}^{T}diag\{\mathrm{c}\mathrm{u}\mathrm{m}_{s_{1}}(p)\mathrm{a}_{*1}^{T}\mathrm{V}\mathrm{a}_{*1}, \ldots, \mathrm{c}\mathrm{u}\mathrm{m}_{s_{n}}(p)\mathrm{c}\mathrm{u}\mathrm{m}_{s_{\mathfrak{n}}}(p)\mathrm{a}_{*n}^{T}\mathrm{V}\mathrm{a}_{*n}\}\mathrm{e}_{j}$$=$$\mathrm{c}\mathrm{u}\mathrm{m}_{s_{\mathrm{j}}}(p)^{2}\mathrm{a}_{*j}^{T}\mathrm{V}\mathrm{a}_{*j}\mathrm{c}\mathrm{u}\mathrm{m}_{s_{j}}(p)^{2}\sum_{k,l=1}^{n}a_{k,j}u_{j,k}a_{li}u_{j,l}-a_{k,j}u_{j+1,k}a_{l,j}u_{j+1,l}$$=$$\mathrm{c}\mathrm{u}\mathrm{m}_{s_{j}}(p)^{2}(\alpha_{1}^{2}-\beta_{1}^{2})$.

Analogously we obtain:.

$\mathrm{c}\mathrm{u}\mathrm{m}_{s_{j+1}}(p)\mathrm{a}_{\mathrm{s}j+1}^{T}\mathrm{D}\mathrm{a}_{*j+1}=\mathrm{c}\mathrm{u}\mathrm{m}_{s_{j+1}}(p)^{2}(\alpha_{2}^{2}-\beta_{2}^{2})$Since$\alpha_{1}^{2}-\beta_{1}^{2}=-(\alpha_{2}^{2}-\beta_{2}^{2})$, we obtain.

$\mathrm{c}\mathrm{u}\mathrm{m}_{s_{j}}(p)\mathrm{a}_{*j}^{T}\mathrm{D}\mathrm{a}_{*j}-\mathrm{c}\mathrm{u}\mathrm{m}_{s_{j+1}}(p)\mathrm{a}_{*j+1}^{T}\mathrm{D}\mathrm{a}_{*j+1}=(\alpha_{1}^{2}-\beta_{1}^{2})(\mathrm{c}\mathrm{u}\mathrm{m}_{s_{\mathrm{j}}}(p)^{2}+\mathrm{c}\mathrm{u}\mathrm{m}_{s_{\mathrm{j}+1}}(p)^{2})$are lnearly independent. So, the above expression isand, since
Note that
nonzero, which finishes the proof of the theorem.
$\alpha_{1}^{2}\neq\beta_{1}^{2}$$\mathrm{u}_{j}$$\mathrm{u}_{j+1}$$\blacksquare$

5Blind Source Extraction using time delays
In this section we prove that BSS problem can be converted to asymmetric eigenvector prob
. So, any algorithm for eigenvector problem can be used to estimate the mixing matrix
and therefore, to separate simultaneously sources with different temporal structures, or different
cumulants.
The use of second statistics approach for blind separation of temporally correlated sources
has been developed and analyzed by many researchers, including $[3]-[5]$ , [19]-[23], etc.
Our approach has unified form for the second order statistic and high order statistics using
matrix cumulants with time delays and it allows to extract colored or signals with different cumulant functions. Even for second order statistics our approach has some advantages that may
not be found in others known results at the same time. It allows us to control successfulnessof the separation by observing the eigenvalues; it provides relative fast convergence (since several algorithm has been developed for the EVD with cubic convergence [10] ; it can solve large
scale problems due to efficiency of available EVD algorithms; it extracts the components simultaneously; does not need the sources to be stationary; does not need that all but one signal to
be Gaussian; and it is robust with respect to additive noise what often leads to smaller errors(cross-talking between estimated sources).
In our method below we need the global mixing matrix to be orthogonal. We use either
standard orthogonalzation procedure, or robust (to additive white noise) one [4], when it issuch that thepossible. We perform such an orthogonalzation by alinear transformation.
, so our model isis orthogonal, i.e.
matrix
We shall consider aconcrete form of fourth order cumulants and note that generalzations
to high order cumulants is straightforward.
be aset of positive integers with elements. We introduce the followingLet$\mathrm{l}\mathrm{e}\mathrm{m}$$)$$\mathrm{z}=\mathrm{Q}\mathrm{x}$$\mathrm{A}=\mathrm{Q}\mathrm{H}$$P=\{p\mathrm{i}, \ldots,p_{L}\}$conditions$\mathrm{A}^{T}\mathrm{A}=\mathrm{I}$$\mathrm{z}(k)=\mathrm{A}\mathrm{s}(k)+\overline{\mathrm{n}}(k)(\overline{\mathrm{n}}=\mathrm{Q}\mathrm{n})$

$L$

27
$\forall i,$j$\neq i$$\exists l_{i,j}\in\{1,$\ldots ,L} :(DAF(P))$E\{s_{i}(t)s_{i}(t-p_{l_{ij}})\}\neq E\{sj(t)sj(t-p_{l_{ij}})\}$

i.e. the sources have different autocorrelation functions on P;$\forall i,j\neq i\exists l_{i,j}\in\{1,$\ldots ,L} :$\mathrm{c}\mathrm{u}\mathrm{m}_{s_{i}}(p\iota_{i,j})\neq \mathrm{c}\mathrm{u}\mathrm{m}_{s_{j}}(pl_{ij})$,(DCF(P))

where$\mathrm{c}\mathrm{u}\mathrm{m}_{s_{i}}(p)=\mathrm{c}\mathrm{u}\mathrm{m}\{s:(k), s_{i}(k), s_{i}(k-p), s_{i}(k-p)\}$i.e. the sources have different cumulant functions of fourth order on the set $P$ .
Define a covariance matrix of the sensor (resp. source) signals by$\mathrm{R}_{\mathrm{z}}(p)=E\{\mathrm{z}\mathrm{z}_{p}^{T}\}$, (resp.

$\mathrm{R}_{\mathrm{s}}(p)=E\{\mathrm{s}\mathrm{s}_{p}^{T}\}$

),

(22)

where
$\mathrm{z}_{p}=\mathrm{z}\{k-p$),$\mathrm{z}=\mathrm{z}(k)$Define a fourth order cumulant matrix$\mathrm{c}_{\mathrm{z},\mathrm{z}_{\mathrm{p}}}^{2,2}=$,$\mathrm{s}_{p}=\mathrm{s}(k-p)$$\mathrm{c}_{\mathrm{z},\mathrm{z}_{p}}^{2,2}$,$\mathrm{s}=\mathrm{s}(k)$

.

(23)

of the sensor signals as follows:(24)$E\{\mathrm{z}\mathrm{z}^{T}\mathrm{z}_{p}^{T}\mathrm{z}_{p}\}-E\{\mathrm{z}\mathrm{z}^{T}\}\mathrm{t}\mathrm{r}E\{\mathrm{z}_{p}\mathrm{z}_{p}^{T}\}-2E\{\mathrm{z}\mathrm{z}_{p}^{T}\}E\{\mathrm{z}_{p}\mathrm{z}^{T}\}$

where $E$ is the mathematical expectation (with respect to in (23)) and similarly, a fourth order
cumulant matrixof the source signals , $i=1$ , , . It is easy to see that the $(i,j)$ -thelement ofis$k$$\mathrm{c}_{\mathrm{s},\mathrm{s}_{p}}^{2,2}$$\mathrm{s}_{i}$$\ldots$$n$$\mathrm{c}_{\mathrm{z},\mathrm{z}_{p}}^{2,2}$.

$C_{\mathrm{z},\mathrm{z}_{p}}^{2,2}(i,j)= \sum_{l=1}^{n}\mathrm{c}\mathrm{u}\mathrm{m}\{z_{i}(k), z_{j}(k), z_{l}(k-p), z_{l}(k-p)\}$

It is clear that
For a given vector$\mathrm{b}\in 1\mathrm{R}^{L}$, according to (14), whereis the unit $n\cross n$ matrix.
define the following matrices for the chosen set $P$ of time deIays .

$\mathrm{c}_{\mathrm{z},\mathrm{z}_{p}}^{2,2}=\mathrm{C}_{\mathrm{z},\mathrm{z}_{p}}^{2,2}(\mathrm{I}_{n})$$\mathrm{I}_{n}$$\cdot$$\mathrm{Z}(\mathrm{b})$$=$$\sum_{i=1}^{L}b_{i}\mathrm{R}_{z}(p_{i})$

;

(25)

$\overline{\mathrm{Z}}(\mathrm{b})=\sum_{i=1}^{L}b_{i}\mathrm{C}_{\mathrm{z},\mathrm{z}_{p:}}^{2,2}$

and similarly for the source signals$\mathrm{S}(\mathrm{b})$$=$$\sum_{i=1}^{L}b_{\dot{\iota}}\mathrm{R}_{s}(p_{i})$;$\overline{\mathrm{S}}(\mathrm{b})=\sum_{i=1}^{L}b_{i}\mathrm{C}_{\mathrm{s},\mathrm{s}_{p:}}^{2,2}$.

$(2\theta)$

We recall that the source signals are uncorrelated, if
are diagonal matrices for every. If the source signals are statistically independent, then this condition is satisfied, but theconverse assertion is not always true. Note that the diagonal elements of $Rs(p)$ are $E\{si(k)si(k$$p)\}$ .
We say that the source signals are colored, if for some $p0\geq 1$ the matrix
has anonzero diagonal element. We shall say that the source signals are uncorrelated of order 4, if
are diagonal matrices for every $p\geq 1$ with diagonal elements. If the source signals
are statistically independent, then this condition is satisfied, but the converse assertion is notalways true. We shall say that the sources are colored of order 4, if for some,is nonzero. So, if , $i=1$ , , are uncorrelated of order 4 and colored of order 4, then for some, the matrix
is a nonzero diagonal matrix.
$\mathrm{R}_{s}(p)$$p\geq 1$$\mathrm{R}_{s}(p\mathrm{o})$$\mathrm{c}_{\mathrm{s},\mathrm{s}_{p}}^{2,2}$$\mathrm{c}\mathrm{u}\mathrm{m}_{s_{i}}(p)$$p_{0}\geq 1$$s_{i}$$P\mathrm{o}\geq 1$$\mathrm{c}_{\mathrm{s},\mathrm{s}_{p_{0}}}^{2,2}$$\ldots$$n$$\mathrm{c}\mathrm{u}\mathrm{m}_{s}(:p_{0})$28Assume that the additive noise n has independent components (with zero means), which
are independent also with , i $=1$ , n. Recall that a signal s is white (resp. white of order 4) if$s_{i}$\ldots ,$E\{s(k)s(k-p)\}=0$ ,$\forall p\geq 1$(resp. $\mathrm{c}\mathrm{u}\mathrm{m}\{s(k-p_{1}), s(k-p_{2})., s(k-p_{3}), s(k-p_{4})\}‘=0$, $i=1$ , , 4).
for every
The proof of the following lemma is straightforward and is omitted.
$p_{i}\geq 1$$\ldots$$mat\dot{m}$ A is $0\hslash hogmal$, the noiseisis white andLemma 6 Assume that theThentheis a diagonal matrix).
is white of order 4 anddiagonal matrix (resp. theis $symmet\sqrt.cal$ and can be decomposed as
matrixmatrix and A is a diagonal
is an), where(resp.
atrix can be estimated as
mixing
the
then
A
are
djstinct,matrix. If the diagonal elements of
up to multiplication with arbitrary pemutation and diagonal sign matrices.
$m\ddot{m}ng$$a$$\mathrm{S}(\mathrm{b})$$\mathrm{n}$$\overline{\mathrm{S}}(\mathrm{b})$$noise\mathrm{n}|$$\mathrm{Z}(\grave{\mathrm{b}})=\mathrm{A}\mathrm{S}(\mathrm{b})\mathrm{A}^{T}=\mathrm{I}\mathrm{J}\Lambda \mathrm{U}^{T}$$\mathrm{Z}(\mathrm{b})(resp_{-}.\overline{\mathrm{Z}}(\mathrm{b}))$$\mathit{0}\ddot{\hslash}hogonal$$\mathrm{U}$$\overline{\mathrm{Z}}(\mathrm{b})=\mathrm{A}\mathrm{S}(\mathrm{b})\mathrm{A}^{T}=\mathrm{U}\mathrm{A}\mathrm{U}^{T}$$m\backslash$$\backslash \hat{\mathrm{A}}=\mathrm{U}$Theorem 7 Assume that the $m\ddot{m}ng$ matrix A is orthogonal and (i): the source
colored and uncomlated, the noise is white and condition (DAF(P)) is satisfied (resp. (ii):the source signals are colored of order 4 and uncorrelated of order 4, condition (DCF(P)) issatisfied and the noise is white of order 4). Then( )) has distinct(resp.
such that the mat(a) there exists \‘a vector$B(L)$$fom$ an open
thispropertywithvectors
eigenvalues. unde,r ore, the setof all, whose complement has a measure zero.
subset of$signal\dot{s}a\dot{r}e$$\mathrm{n}$$\mathrm{n}$$\dot{\mathrm{b}}$$\tilde{\mathrm{Z}}$$\mathrm{b}\in \mathrm{R}^{\mathrm{L}}$$\dot{m}\mathrm{Z}(\mathrm{b})$$\mathrm{b}\in \mathrm{R}^{\mathrm{L}}$$\mathrm{R}^{\mathrm{L}}$$(resp.thematr\dot{.}\dot{\mathrm{v}}x\overline{\mathrm{Z}}(\mathrm{b}))fosomethentheesstimatingmixingmatr\dot{\tau}x$$\mathrm{b}\in B(L),i.e(b)If\mathrm{U}.is$$\mathrm{Z}(\mathrm{b})=\mathrm{U}\Lambda \mathrm{U}^{T},(resp.\overline{\mathrm{Z}}(\mathrm{b})=\mathrm{U}\mathrm{A}\mathrm{U}^{T})givenfromanEVDofthemat7\mathrm{i}x\mathrm{Z}(\mathrm{b}),$and the separating matrix isis).
pemutation and diagbnal sign$\hat{\mathrm{A}}=\mathrm{U}$$\mathrm{W}=\hat{\mathrm{A}}^{T}=\mathrm{U}^{T}$(uP to multiplication with arbitrary$matr\dot{\mathrm{v}}ces$

Proof. We shall prove the theorem under condition (i) (the proof is similar under condition(ii) .
$)$

is a diagonal matrix and by Lemma 1,, $i=1$ , , are uncorrelated,have the same eigenvalues. It
and. Observe that the matrices. If we prove
finite union of subspaces ofis easy to see that the complement of $B$ } )
),
(i.e.
ffom
propersubspacesmustbedifferent
every
these
of
nonempty,
theniscomplement
of
),
the
therefore
consequently, with a measure zero (with respect tohave a measure zero too.
. Assume, wherebe the diagonal elements of the matrix
Let
. Let
equal, for example
that two diagonal elements of the matrix
is defined by the
be a vector, which is different from only in the component, because of the condition (DAF(P)).
condition (DAF(P)) . Thenthat
different,
we finish the proof. If riot,
are
If all diagonal elements of$.(\mathrm{a})$

Since

$s:$

$\ldots$$\mathrm{S}(\mathrm{b})$$n$$\mathrm{Z}(\mathrm{b})$$\mathrm{Z}(\mathrm{b})=\mathrm{A}\mathrm{S}(\mathrm{b})\mathrm{A}^{T}$$\mathrm{S}(\mathrm{b})$$\mathrm{R}^{L}$$L.$$\mathrm{i}\mathrm{s}‘ \mathrm{a}$$\mathrm{R}^{L}$$\mathrm{t}\grave{\mathrm{h}}\mathrm{a}\mathrm{t}B(L)$st.

$\mathrm{R}^{L}$$B(L)\mathrm{m}_{_{\backslash }}\mathrm{u}.$$\mathrm{b}\in \mathrm{R}^{L}$$\mathrm{S}(\mathrm{b})$$\{\sigma_{i}(\mathrm{b})\}_{i=1}^{n}$$\sigma_{1}(\mathrm{b})=\sigma_{2}(\mathrm{b})$$\mathrm{S}(\mathrm{b})\mathrm{a}\mathrm{r}\mathrm{e}_{1}$$\mathrm{b}$$\mathrm{b}(1,2)$$b_{l_{12}}(l_{1,2}$$\sigma_{1}(\mathrm{b}(1,, 2))\neq\sigma_{2}(\mathrm{b}(1,2))$$)$$\mathrm{S}(\mathrm{b}(1,2))$$\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}_{t}\mathrm{o}_{1}\mathrm{s}\mathrm{e}$.
(because of condition (DAF(P)) and$k\neqr$$(k,r)$(where,for whichContinuing in such a way, for any couple
keeping thered in the previous step), we make small change ofis the vector
diffetence of the diagonal elements considered in the previous steps and obtain. So, after finite number of steps we obtain a vector
for which.
are distinct. This proves the non-emptiness of the setoffor which the diagonal elements$B(L)$ and finishes the proof of (a).
known facts of linear algebra [14].
(b) This follows from thebe satisfied$\sigma_{1}(\mathrm{b}(i,j))\neq\sigma_{2}(\mathrm{b}(i,j))$$‘\sigma_{i}(\mathrm{b}(i,j))\neq\sigma_{j}(\mathrm{b}(i,j))$$\sigma k(\mathrm{b}(k’, r’))=\sigma_{r}(\mathrm{b}(k’, r’))$$\mathrm{b}(k’, r’)9$$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{d}^{\mathrm{I}}\mathrm{e}$$b_{l_{k\iota \mathrm{r}}}$$\dot{\mathrm{v}}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}$$\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}- \mathrm{w}^{\backslash }\mathrm{i}\mathrm{s}\mathrm{e}$$\mathrm{b}(\mathrm{i}, r)$$(\mathrm{k}_{k}(\mathrm{b}(k)r))\neq$$\mathrm{b}^{*}$$\sigma_{r}(\mathrm{b}(k, r))$$\mathrm{S}(\mathrm{b}^{*})$$\mathrm{w}\mathrm{e}\mathrm{u}$$\blacksquare$

29(resp.
Remark 1If the matrix) is non-symmetric (due to some numerical errors
and finite number of samples) the following procedure can ’be applied. Construct symmetric$\mathrm{Z}(/7)$

matrix:$\mathrm{U}(\mathrm{b})\ovalbox{\tt\small REJECT}$

4$[\mathrm{Z}(\mathrm{b})+\mathrm{Z}^{T}(\mathrm{b})]$$\mathrm{Z}(/7)$(resp.

$\mathrm{t}\mathrm{v}\mathrm{t}(\mathrm{b})\ovalbox{\tt\small REJECT}$

M$[\ovalbox{\tt\small REJECT}(\mathrm{b})+\ovalbox{\tt\small REJECT}^{T}(\mathrm{b})\ovalbox{\tt\small REJECT}$) and then apply EVD.

6Subdifferential dispersing algorithm for sources with distinct
cumulant functions
We assume in section that the mixing matrix is orthogonal (after robust ortogonalization [4]) andthe source signals have distinct cumulant functions, i.e.
and
as functions of$j\neqi$any,). (If the mixing matrix is not orthogonal, the normalized cumulant
are different forfunctions should be different.) This condition could be considered as large generalization of theconditions given in [23], [7].
(resp.
) has
We have proved that the set of vectors
for which the matrix
distinct eigenvalues and an EVD of it leads to separation of the mixing signals, ha afull measure(i.e. its complement has measure zero). This suggests arandom choice of to achieve separation.
Nevertheless, here we propose asubdifferential disperqing algorithm for the eigenvalues of.
When these cumulant functions are very different (i.e. if we can find apriori asmall set of indexes$P=\{p_{1}, \ldots,p_{L}\}$ such thatfor some $pij\in P$ ) the following algorithm
has an advantage for large scale problems (because the parameter here is vector, not matrix).
, whereare the eigenvalues
Consider the function:(in decreasing order) of the matrix. This function has properties similar to those of (17)and the algorithm for its maximization is the same as those of with the only difference thatin the above algorithm is replaced with the vector , and Wij are replaced with the vectors$\mathrm{c}\mathrm{u}\mathrm{m}_{s_{i}}(p)$$\mathrm{c}\mathrm{u}\mathrm{m}_{s_{j}}(p)$

$i$

$p$

$\mathrm{b}\in \mathrm{R}^{L}$$\overline{\mathrm{Z}}(\mathrm{b})$$\mathrm{Z}(\mathrm{b})$$\mathrm{s}$$\mathrm{b}$$\overline{\mathrm{Z}}(\mathrm{b})$$\mathrm{c}\mathrm{u}\mathrm{m}_{s_{i}}(p_{i,j})\neq \mathrm{c}\mathrm{u}\mathrm{m}_{s}(:p_{i,j})$$\psi(\mathrm{b})=\min_{1\leq i\leq m-1}\{\lambda_{i}(\mathrm{b})-\lambda_{i+1}(\mathrm{b})\}$$\lambda_{i}(\mathrm{b})$$\overline{\mathrm{Z}}(\mathrm{b})$$\varphi$$\mathrm{B}$$\mathrm{b}$$with=[\mathrm{u}_{i,k}^{T}\mathrm{C}_{\mathrm{z},\mathrm{z}_{p_{1}}}^{2,2}(\mathrm{I}_{n})\mathrm{u}_{i,k}, \ldots, \mathrm{u}_{i,k}^{T}\mathrm{C}_{\mathrm{z},\mathrm{z}_{p_{L}}}^{2,2}(\mathrm{I}_{n})\mathrm{u}_{i,k}]^{T}$

The subdifferential$\partial\psi(\mathrm{b})$.

is given by the formula:$\partial\psi(\mathrm{b})=\overline{co}\{(\mathrm{v}^{T}\mathrm{R}_{z}(p_{1})\mathrm{v}, \ldots, \mathrm{v}^{T}\mathrm{R}_{z}(p_{L})\mathrm{v})-(\mathrm{u}^{T}\mathrm{R}_{z}(p_{1})\mathrm{u}, \ldots, \mathrm{u}^{T}\mathrm{R}_{\mathit{2}}(pL)\mathrm{u}) :\mathrm{v}\in \mathrm{V}_{i}, \mathrm{u}\in \mathrm{V}_{i},\dot{n}\in I_{0}\}$

where
is the set where the minimum in the definition of is attained,is the set of all unit
eigenvectors corresponding to the eigenvalueanddenotes the closed convex hull.
$\psi$$I\circ$$\lambda_{i}$$\mathrm{V}_{i}$$\overline{co}$References[1] V.M. Alekseev, V.M. Tihomirov and S.V. Fomin, Optimal Control, Nauka, 1979 (in R.ussian).
[2] S. Amari and A. Cichocki “Adaptive blind signal processing-netiral network approaches”.
Proceedings IEEE (invited paper), 86(10): 2016-2048, 1999.

[3] S. Amari “ICA of temporally correlated signals -learning algorithm”. Proc. ICA’99:International workshop on blind signal separation ’and independent component analysis, Aussois,
Prance, pp. 13-18, Jan. 1999.
[4] A. Belouchrani and A. Cichocki A. “Robust whitening procedure in blind separation context”. Electronics Letters, Vol. 36 N0.24, pp. 2050-2051, 2000.
1[5] A. Belouchrani, K. A. Meraim, J.-P. Cardoso and E. Moulines “A blind source separation
technique using second order statistics.” IEEE Trans, on Signal Processing, Vol. 45, ’no. 2,
pp. 434-44, Feb. 1997.
[6] J.-F. Cardoso, “High-0rder contrasts for independent component analysis” Neural Computation, vol. 11, no 1, pp. 157-192, Jan. 1999.

,

30[7] C. Chang, S.F. Yau, P. Kwok, F.H.Y. Chan, F.K. Lam, Uncor related and component analysis
for blind source separation, Circuits Systems and Signal Processsing, Vol. 18, N0.3, PP. 225239, 1999.
[8] Clarke F.S. Optimization and Nonsmooth Analysis. J. Wiley and Sons, 1983.

[9] N. Delfosse and P. Loubaton “Adaptive blind separation of independent sources: adeflation
approach”. Signal Processing, 45: 59-83, 1995.
[10] A. Edelman, T. A. Arias and A. T. Smith “The geometry of algorithms with orthogonality
constraints”. SIAM J. Matrix Anal APPl, Vo. 20, N0.2, PP. 303-353, 1998.

[11] P. Gr. Georgiev “Submonotone Mappings in Banach Spaces and Applications”. Set- Valued
Analysis, 5: 1-35, 1997.

[12] P. Gr. Georgiev, A. Cichocki “Robust Blind Source Separation via Symmetric Eigenvalue
Decomposition” (submitted).
[13] P. Gr. Georgiev, A. Cichocki, “BUnd Source Separation via Symmetric Eigenvalue Decomposition” , in Proc. ISSPA (Kuala Lumpur, Malaysia), pp. 17-20, 2001.
[14] G. H. Golub and C. F. Van Loan Matrix Computation. J. Hopkins Univ. Press, 1989.

[15] Y. Hua and J. K. Tugnait “Blind Identifiability of FIR-MIMO Systems with Colored Input
Using Second Order Statistics”. IEEE Signal Processing Letters, Vol. 7No. 12, pp. 348350,
Dec. 2000.
[16] A. Hyvarinen, J. Karhunen and E. Oja, “Independent Component Analysis”, John Wiley&Sons, 2001.
[17] A. Hyvarinen and E. Oja A fast fixed-point algorithm for independent component analysis,
Neural Comp., 9: 1483-1492,1997.
[18] J. R. Magnus, H. Neudecker, Matrix Differential Calculus with Applications in Statistics andEconometrics, Wiley, 1999.
[19] L. Molgedey and H. G. Schuster “Separation of amixture of independent signals using
time-delayed correlations. Physical Revi ew Letters, Vol. 72, No. 23, pP. 3634-3637,1994.
[20] K.-R. Mueller, P. Philips and A. Ziehe “JADETD: Combining higher-0rder statistics andtemporal information for blind source separation (with noise)”. Proc. IEEE International
Conference on Independent Component Analysis and Signal Separation, Aussois, France,
pp. 312-316, Jan. 1999.

[21] D. T. Pham and P. Garat “Blind separation of mixtures of independent sources through aquasi-uaaximum likelihood approach”. IEEE Trans, on Signal Processing, Vol. 45, No. 7,
pp. 1712-1725, 1997.
[22] A. N. Shiryaev, Probability, Graduate Texts in Mathematics, Springer, 1996.
[23] L. Tong, R. Liu, V.C. Soon and Y.F. Huang, Indeterminacy and Identifiability of Blind
Identification, IEEE Transactions on Circuits and Systems, Vol. 38, N0.5, PP. 499-509, May