Independent component analysis

In signal processing, independent component analysis (ICA) is a computational method for separating a multivariate signal into additive subcomponents. This is done by assuming that at most one subcomponent is Gaussian and that the subcomponents are statistically independent from each other. ICA is a special case of blind source separation. A common example application is the "cocktail party problem" of listening in on one person's speech in a noisy room.
Introduction.
Independent component analysis attempts to decompose a multivariate signal into independent non-Gaussian signals. As an example, sound is usually a signal that is composed of the numerical addition, at each time t, of signals from several sources. The question then is whether it is possible to separate these contributing sources from the observed total signal. When the statistical independence assumption is correct, blind ICA separation of a mixed signal gives very good results. It is also used for signals that are not supposed to be generated by mixing for analysis purposes.
A simple application of ICA is the "cocktail party problem", where the underlying speech signals are separated from a sample data consisting of people talking simultaneously in a room. Usually the problem is simplified by assuming no time delays or echoes. Note that a filtered and delayed signal is a copy of a dependent component, and thus the statistical independence assumption is not violated.
Mixing weights for constructing the "formula_1" observed signals from the formula_2 components can be placed in an formula_3 matrix. An important thing to consider is that if formula_2 sources are present, at least formula_2 observations (e.g. microphones if the observed signal is audio) are needed to recover the original signals. When there are an equal number of observations and source signals, the mixing matrix is square ("formula_6"). Other cases of underdetermined ("formula_7") and overdetermined ("formula_8") have been investigated.
That the ICA separation of mixed signals gives very good results is based on two assumptions and three effects of mixing source signals. Two assumptions:
Three effects of mixing source signals:
Those principles contribute to the basic establishment of ICA. If the signals extracted from a set of mixtures are independent, and have non-Gaussian histograms or have low complexity, then they must be source signals.
Defining component independence.
ICA finds the independent components (also called factors, latent variables or sources) by maximizing the statistical independence of the estimated components. We may choose one of many ways to define a proxy for independence, and this choice governs the form of the ICA algorithm. The two broadest definitions of independence for ICA are
The Minimization-of-Mutual information (MMI) family of ICA algorithms uses measures like Kullback-Leibler Divergence and maximum entropy. The non-Gaussianity family of ICA algorithms, motivated by the central limit theorem, uses kurtosis and negentropy.
Typical algorithms for ICA use centering (subtract the mean to create a zero mean signal), whitening (usually with the eigenvalue decomposition), and dimensionality reduction as preprocessing steps in order to simplify and reduce the complexity of the problem for the actual iterative algorithm. Whitening and dimension reduction can be achieved with principal component analysis or singular value decomposition. Whitening ensures that all dimensions are treated equally "a priori" before the algorithm is run. Well-known algorithms for ICA include infomax, FastICA, JADE, and kernel-independent component analysis, among others. In general, ICA cannot identify the actual number of source signals, a uniquely correct ordering of the source signals, nor the proper scaling (including sign) of the source signals.
ICA is important to blind signal separation and has many practical applications. It is closely related to (or even a special case of) the search for a factorial code of the data, i.e., a new vector-valued representation of each data vector such that it gets uniquely encoded by the resulting code vector (loss-free coding), but the code components are statistically independent.
Mathematical definitions.
Linear independent component analysis can be divided into noiseless and noisy cases, where noiseless ICA is a special case of noisy ICA. Nonlinear ICA should be considered as a separate case.
General definition.
The data are represented by the observed random vector formula_9 and the hidden components as the random vector formula_10 The task is to transform the observed data formula_11 using a linear static transformation formula_12 as formula_13 into a vector of maximally independent components formula_14 measured by some function formula_15 of independence.
Generative model.
Linear noiseless ICA.
The components formula_16 of the observed random vector formula_9 are generated as a sum of the independent components formula_18, formula_19:
formula_20
weighted by the mixing weights formula_21.
The same generative model can be written in vector form as formula_22, where the observed random vector formula_23 is represented by the basis vectors formula_24. The basis vectors formula_25 form the columns of the mixing matrix formula_26 and the generative formula can be written as formula_27, where formula_28.
Given the model and realizations (samples) formula_29 of the random vector formula_23, the task is to estimate both the mixing matrix formula_31 and the sources formula_14. This is done by adaptively calculating the formula_33 vectors and setting up a cost function which either maximizes the non-gaussianity of the calculated formula_34 or minimizes the mutual information. In some cases, a priori knowledge of the probability distributions of the sources can be used in the cost function.
The original sources formula_14 can be recovered by multiplying the observed signals formula_23 with the inverse of the mixing matrix formula_37, also known as the unmixing matrix. Here it is assumed that the mixing matrix is square (formula_38). If the number of basis vectors is greater than the dimensionality of the observed vectors, formula_39, the task is overcomplete but is still solvable with the pseudo inverse.
Linear noisy ICA.
With the added assumption of zero-mean and uncorrelated Gaussian noise formula_40, the ICA model takes the form formula_41.
Nonlinear ICA.
The mixing of the sources does not need to be linear. Using a nonlinear mixing function formula_42 with parameters formula_43 the nonlinear ICA model is formula_44.
Identifiability.
The independent components are identifiable up to a permutation and scaling of the sources. This identifiability requires that:
Binary ICA.
A special variant of ICA is binary ICA in which both signal sources and monitors are in binary form and observations from monitors are disjunctive mixtures of binary independent sources. The problem was shown to have applications in many domains including medical diagnosis, multi-cluster assignment, network tomography and internet resource management.
Let formula_50 be the set of binary variables from formula_46 monitors and formula_52 be the set of binary variables from formula_47 sources. Source-monitor connections are represented by the (unknown) mixing matrix formula_54, where formula_55 indicates that signal from the "i"-th source can be observed by the "j"-th monitor. The system works as follows: at any time, if a source formula_56 is active (formula_57) and it is connected to the monitor formula_58 (formula_59) then the monitor formula_58 will observe some activity (formula_61). Formally we have:
where formula_63 is Boolean AND and formula_64 is Boolean OR. Note that noise is not explicitly modelled, rather, can be treated as independent sources.
The above problem can be heuristically solved by assuming variables are continuous and running FastICA on binary observation data to get the mixing matrix formula_54 (real values), then apply round number techniques on formula_54 to obtain the binary values. This approach has been shown to produce a highly inaccurate result.
Another method is to use dynamic programming: recursively breaking the observation matrix formula_67 into its sub-matrices and run the inference algorithm on these sub-matrices. The key observation which leads to this algorithm is the sub-matrix formula_68 of formula_67 where formula_70 corresponds to the unbiased observation matrix of hidden components that do not have connection to the formula_56-th monitor. Experimental results from show that this approach is accurate under moderate noise levels.
The Generalized Binary ICA framework introduces a broader problem formulation which does not necessitate any knowledge on the generative model. In other words, this method attempts to decompose a source into its independent components (as much as possible, and without losing any information) with no prior assumption on the way it was generated. Although this problem appears quite complex, it can be accurately solved with a branch and bound search tree algorithm or tightly upper bounded with a single multiplication of a matrix with a vector.
Methods for blind source separation.
Projection pursuit.
Signal mixtures tend to have Gaussian probability density functions, and source signals tend to have non-Gaussian probability density functions. Each source signal can be extracted from a set of signal mixtures by taking the inner product of a weight vector and those signal mixtures where this inner product provides an orthogonal projection of the signal mixtures. The remaining challenge is finding such a weight vector. One type of method for doing so is projection pursuit.
Projection pursuit seeks one projection at a time such that the extracted signal is as non-Gaussian as possible. This contrasts with ICA, which typically extracts "M" signals simultaneously from "M" signal mixtures, which requires estimating a "M" × "M" unmixing matrix. One practical advantage of projection pursuit over ICA is that fewer than "M" signals can be extracted if required, where each source signal is extracted from "M" signal mixtures using an "M"-element weight vector.
We can use kurtosis to recover the multiple source signal by finding the correct weight vectors with the use of projection pursuit.
The kurtosis of the probability density function of a signal, for a finite sample, is computed as
where formula_73 is the sample mean of formula_74, the extracted signals. The constant 3 ensures that Gaussian signals have zero kurtosis, Super-Gaussian signals have positive kurtosis, and Sub-Gaussian signals have negative kurtosis. The denominator is the variance of formula_74, and ensures that the measured kurtosis takes account of signal variance. The goal of projection pursuit is to maximize the kurtosis, and make the extracted signal as non-normal as possible.
Using kurtosis as a measure of non-normality, we can now examine how the kurtosis of a signal formula_76 extracted from a set of "M" mixtures formula_77 varies as the weight vector formula_78 is rotated around the origin. Given our assumption that each source signal formula_79 is super-gaussian we would expect:
For multiple source mixture signals, we can use kurtosis and Gram-Schmidt Orthogonalization (GSO) to recover the signals. Given "M" signal mixtures in an "M"-dimensional space, GSO project these data points onto an ("M-1")-dimensional space by using the weight vector. We can guarantee the independence of the extracted signals with the use of GSO.
In order to find the correct value of formula_78, we can use gradient descent method. We first of all whiten the data, and transform formula_89 into a new mixture formula_90, which has unit variance, and formula_91. This process can be achieved by applying Singular value decomposition to formula_89,
Rescaling each vector formula_94, and let formula_95. The signal extracted by a weighted vector formula_78 is formula_97. If the weight vector w has unit length, then the variance of y is also 1, that is formula_98. The kurtosis can thus be written as:
The updating process for formula_78 is:
where formula_102 is a small constant to guarantee that formula_78 converges to the optimal solution. After each update, we normalize formula_104, and set formula_105, and repeat the updating process until convergence. We can also use another algorithm to update the weight vector formula_78.
Another approach is using negentropy instead of kurtosis. Using negentropy is a more robust method than kurtosis, as kurtosis is very sensitive to outliers. The negentropy methods are based on an important property of Gaussian distribution: a Gaussian variable has the largest entropy among all continuous random variables of equal variance. This is also the reason why we want to find the most nongaussian variables. A simple proof can be found in Differential entropy.
y is a Gaussian random variable of the same covariance matrix as x
An approximation for negentropy is
A proof can be found in the original papers of Comon; it has been reproduced in the book "Independent Component Analysis" by Aapo Hyvärinen, Juha Karhunen, and Erkki Oja This approximation also suffers from the same problem as kurtosis (sensitivity to outliers). Other approaches have been developed. 
A choice of formula_111 and formula_112 are 
Based on infomax.
Infomax ICA is essentially a multivariate, parallel version of projection pursuit. Whereas projection pursuit extracts a series of signals one at a time from a set of "M" signal mixtures, ICA extracts "M" signals in parallel. This tends to make ICA more robust than projection pursuit.
The projection pursuit method uses Gram-Schmidt orthogonalization to ensure the independence of the extracted signal, while ICA use infomax and maximum likelihood estimate to ensure the independence of the extracted signal. The Non-Normality of the extracted signal is achieved by assigning an appropriate model, or prior, for the signal.
The process of ICA based on infomax in short is: given a set of signal mixtures formula_89 and a set of identical independent model cumulative distribution functions(cdfs) formula_116, we seek the unmixing matrix formula_117 which maximizes the joint entropy of the signals formula_118, where formula_119 are the signals extracted by formula_117. Given the optimal formula_117, the signals formula_122 have maximum entropy and are therefore independent, which ensures that the extracted signals formula_123 are also independent. formula_116 is an invertible function, and is the signal model. Note that if the source signal model probability density function formula_125 matches the probability density function of the extracted signal formula_126, then maximizing the joint entropy of formula_127 also maximizes the amount of mutual information between formula_89 and formula_122. For this reason, using entropy to extract independent signals is known as infomax.
Consider the entropy of the vector variable formula_118, where formula_119 is the set of signals extracted by the unmixing matrix formula_117. For a finite set of values sampled from a distribution with pdf formula_126, the entropy of formula_122 can be estimated as:
The joint pdf formula_136 can be shown to be related to the joint pdf formula_126 of the extracted signals by the multivariate form:
where formula_139 is the Jacobian matrix. We have formula_140, and formula_141 is the pdf assumed for source signals formula_142, therefore,
therefore,
We know that when formula_145, formula_136 is of uniform distribution, and formula_147 is maximized. Since
where formula_149 is the absolute value of the determinant of the unmixing matrix formula_117. Therefore,
so,
since formula_153, and maximizing formula_117 does not affect formula_155, so we can maximize the function
to achieve the independence of extracted signal.
If there are "M" marginal pdfs of the model joint pdf formula_157 are independent and use the commonly super-gaussian model pdf for the source signals formula_158, then we have
In the sum, given an observed signal mixture formula_89, the corresponding set of extracted signals formula_74 and source signal model formula_162, we can find the optimal unmixing matrix formula_117, and make the extracted signals independent and non-gaussian. Like the projection pursuit situation, we can use gradient descent method to find the optimal solution of the unmixing matrix.
Based on maximum likelihood estimation.
Maximum likelihood estimation (MLE) is a standard statistical tool for finding parameter values (e.g. the unmixing matrix formula_117) that provide the best fit of some data (e.g., the extracted signals formula_165) to a given a model (e.g., the assumed joint probability density function (pdf) formula_125 of source signals).
The ML "model" includes a specification of a pdf, which in this case is the pdf formula_125 of the unknown source signals formula_168. Using ML ICA, the objective is to find an unmixing matrix that yields extracted signals formula_169 with a joint pdf as similar as possible to the joint pdf formula_125 of the unknown source signals formula_168.
MLE is thus based on the assumption that if the model pdf formula_125 and the model parameters formula_173 are correct then a high probability should be obtained for the data formula_174 that were actually observed. Conversely, if formula_173 is far from the correct parameter values then a low probability of the observed data would be expected.
Using MLE, we call the probability of the observed data for a given set of model parameter values (e.g., a pdf formula_125 and a matrix formula_173) the "likelihood" of the model parameter values given the observed data.
We define a "likelihood" function formula_178 of formula_117:
formula_180
This equals to the probability density at formula_174, since formula_182.
Thus, if we wish to find a formula_117 that is most likely to have generated the observed mixtures formula_174 from the unknown source signals formula_168 with pdf formula_125 then we need only find that formula_117 which maximizes the "likelihood" formula_178. The unmixing matrix that maximizes equation is known as the MLE of the optimal unmixing matrix.
It is common practice to use the log "likelihood", because this is easier to evaluate. As the logarithm is a monotonic function, the formula_117 that maximizes the function formula_178 also maximizes its logarithm formula_191. This allows us to take the logarithm of equation above, which yields the log "likelihood" function
formula_192
If we substitute a commonly used high-Kurtosis model pdf for the source signals formula_193 then we have
formula_194
This matrix formula_117 that maximizes this function is the maximum likelihood estimation.
History and background.
The early general framework for independent component analysis was introduced by Jeanny Hérault and Bernard Ans from 1984, further developed by Christian Jutten in 1985 and 1986, and refined by Pierre Comon in 1991, and popularized in his paper of 1994. In 1995, Tony Bell and Terry Sejnowski introduced a fast and efficient ICA algorithm based on infomax, a principle introduced by Ralph Linsker in 1987.
There are many algorithms available in the literature which do ICA. A largely used one, including in industrial applications, is the FastICA algorithm, developed by Hyvärinen and Oja, which uses the negentropy as cost function. Other examples are rather related to blind source separation where a more general approach is used. For example, one can drop the independence assumption and separate mutually correlated signals, thus, statistically "dependent" signals. Sepp Hochreiter and Jürgen Schmidhuber showed how to obtain non-linear ICA or source separation as a by-product of regularization (1999). Their method does not require a priori knowledge about the number of independent sources.
Applications.
ICA can be extended to analyze non-physical signals. For instance, ICA has been applied to discover discussion topics on a bag of news list archives.
Some ICA applications are listed below:
Availability.
ICA can be applied through the following software: