1. dimensionality reduction;

2. determination of linear combinations of variables;

3. feature selection: the choice of the most useful variables;

4. visualization of multi-dimensional data;

5. identification of underlying variables;

6. identification of groups of objects or of outliers.

1. Given random vectors , with finite second order moments and zero mean, find the reduced J-dimensional () linear subspace that minimizes the expected distance of from the subspace. This problem arises in the area of data compression, where the task is to represent all the data with a reduced number of parameters while assuring minimum distortion due to the projection.

2. Given random vectors , find the J-dimensional linear subspace that captures most of the variance of the data. This problem is related to feature extraction, where the objective is to reduce the dimension of the data while retaining most of its information content.

1.21.2.1 Standard PCA

Without loss of generality let us consider a data matrix with T samples and I variables and with the columns centered (zero mean) and scaled. Equivalently, it is sometimes convenient to consider the data matrix . The standard PCA can be written in terms of the scaled sample covariance matrix as follows: Find orthonormal vectors by solving the following optimization problem

(21.8)

PCA can be converted to the eigenvalue problem of the covariance matrix of , and it is essentially equivalent to the Karhunen-Loève transform used in image and signal processing. In other words, PCA is a technique for the computation of eigenvectors and eigenvalues for the scaled estimated covariance matrix

(21.9)

where is a diagonal matrix containing the I eigenvalues (ordered in decreasing values) and is the corresponding orthogonal or unitary matrix consisting of the unit length eigenvectors referred to as principal eigenvectors. It should be noted that the covariance matrix is symmetric positive definite, that is why the eigenvalues are nonnegative. We assume that for noisy data all eigenvalues are positive and we put them in descending order.

The basic problem we try to solve is the standard eigenvalue problem which can be formulated using the equations

(21.10)

where are the orthonormal eigenvectors, are the corresponding eigenvalues and is the covariance matrix of zero-mean signals and E is the expectation operator. Note that (21.10) can be written in matrix form as , where is the diagonal matrix of eigenvalues (ranked in descending order) of the estimated covariance matrix .

The Karhunen-Loéve-transform determines a linear transformation of an input vector as

(21.11)

where is the zero-mean input vector, is the output vector called the vector of principal components (PCs), and , with , is the set of signal subspace eigenvectors, with the orthonormal vectors , (i.e., for , where is the Kronecker delta that equals 1 for , and zero otherwise. The vectors are eigenvectors of the covariance matrix, while the variances of the PCs are the corresponding principal eigenvalues, i.e., .

On the other hand, the minor components are given by

(21.12)

where consists of the eigenvectors associated with the smallest eigenvalues.

1.21.2.2 Determining the number of principal components

A quite important problem arising in many application areas is the determination of the dimensions of the signal and noise subspaces. In other words, a central issue in PCA is choosing the number of principal components to be retained [42–44]. To solve this problem, we usually exploit a fundamental property of PCA: It projects the sensor data from the original I-dimensional space onto a J-dimensional output subspace (typically, with ), thus performing a dimensionality reduction which retains most of the intrinsic information in the input data vectors. In other words, the principal components are estimated in such a way that, for , although the dimensionality of data is strongly reduced, the most relevant information is retained in the sense that the input data can be approximately reconstructed from the output data (signals) by using the transformation , that minimizes a suitable cost function. A commonly used criterion is the minimization of the mean squared error subject to orthogonality constraint .

Under the assumption that the power of the signals is larger than the power of the noise, the PCA enables us to divide observed (measured) sensor signals: into two subspaces: the signal subspace corresponding to principal components associated with the largest eigenvalues called the principal eigenvalues: , () and associated eigenvectors called the principal eigenvectors and the noise subspace corresponding to the minor components associated with the eigenvalues . The subspace spanned by the J first eigenvectors can be considered as an approximation of the noiseless signal subspace. One important advantage of this approach is that it enables not only a reduction in the noise level, but also allows us to estimate the number of sources on the basis of distribution of the eigenvalues. However, a problem arising from this approach is how to correctly set or estimate the threshold which divides eigenvalues into the two subspaces, especially when the noise is large (i.e., the SNR is low). The scaled covariance matrix of the observed data can be written as

(21.13)

where is a rank-J matrix, contains the eigenvectors associated with J principal (signal + noise subspace) eigenvalues of in a descending order. Similarly, the matrix contains the (noise subspace) eigenvectors that correspond to the noise eigenvalues . This means that, theoretically, the smallest eigenvalues of are equal to , so we can theoretically (in the ideal case) determine the dimension of the signal subspace from the multiplicity of the smallest eigenvalues under the assumption that the variance of the noise is relatively low and we have a perfect estimate of the covariance matrix. However, in practice, we estimate the sample covariance matrix from a limited number of samples and the (estimated) smallest eigenvalues are usually different, so the determination of the dimension of the signal subspace is not an easy task. Usually we set the threshold between the signal and noise eigenvalues by using some heuristic procedure or a rule of thumb. A simple ad hoc rule is to plot the eigenvalues in decreasing order and search for an elbow, where the signal eigenvalues are on the left side and the noise eigenvalues are on the right side. Another simple technique is to compute the cumulative percentage of the total variation explained by the PCs and retain the number of PCs that represent, say 95% of the total variation. Such techniques often work well in practice, but their disadvantage is that they need a subjective decision from the user [44].

Alternatively, can use one of the several well-known information theoretic criteria, namely, Akaike’s Information Criterion (AIC), the Minimum Description Length (MDL) criterion and Bayesian Information Criterion (BIC) [43,45,46]. To do this, we compute the probability distribution of the data for each possible dimension (see [46]).

Unfortunately, AIC and MDL criteria provide only rough estimates (of the number of sources) that are rather very sensitive to variations in the SNR and the number of available data samples.

Many sophisticated methods have been introduced such as a Bayesian model selection method, which is referred to as the Laplace method. It is based on computing the evidence for the data and it requires integrating out all the model parameters. The BIC method can be thought of as an approximation to the Laplace criterion. The calculation involves an integral over the Stiefel manifold which is approximated by the Laplace method [43]. One problem with the AIC, MDL and BIC criteria mentioned above is that they have been derived by assuming that the data vectors have a Gaussian distribution [46]. This is done for mathematical tractability, by making it possible to derive closed form expressions. The Gaussianity assumption does not usually hold exactly in the BSS and other signal processing applications. For setting the threshold between the signal and noise eigenvalues, one might even suppose that the AIC, MDL and BIC criteria cannot be used for the BSS, particularly ICA problems, because in those cases we assume that the source signals are non-Gaussian. However, it should be noted that the components of the data vectors are mixtures of the sources, and therefore they often have distributions that are not too far from a Gaussian distribution.

An alternative simple heuristic method [42,47] computes the GAP (smoothness) index between consecutive eigenvalues defined as

(21.14)

where and are the eigenvalues of the covariance matrix for the noisy data and the sample variances are computed as follows:

(21.15)

The number of components (for each mode) are selected using the following criterion:

(21.16)

Recently, Ulfarsson and Solo [44] proposed an alternative more sophisticated method called SURE (Stein’s Unbiased Risk Estimator) which allows to estimate the number of PC components.

Extensive numerical experiments indicate that the Laplace method usually outperforms the BIC method while the GAP and SURE methods can often achieve significantly better performance than the Laplace method.

1.21.2.3 Whitening

Some adaptive algorithms for blind separation require prewhitening (also called sphering or normalized spatial decorrelation) of mixed (sensor) signals. A random, zero-mean vector is said to be white if its covariance matrix is an identity matrix, i.e., or , where is the Kronecker delta. In whitening, the sensor vectors are pre-processed using the following transformation:

(21.17)

Here denotes the whitened vector, and is an whitening matrix. For , where J is known in advance, simultaneously reduces the dimension of the data vectors from I to J. In whitening, the matrix is chosen such that the scaled covariance matrix E becomes the unit matrix . Thus, the components of the whitened vectors are mutually uncorrelated and have unit variance, i.e.,

(21.18)

Generally, the sensor signals are mutually correlated, i.e., the covariance matrix is a full (not diagonal) matrix. It should be noted that the matrix is not unique, since multiplying it by an arbitrary orthogonal matrix from the left still preserves property (21.18). Since the covariance matrix of sensor signals is symmetric positive semi-definite, it can be decomposed as follows:

(21.19)

where is an orthogonal matrix and is a diagonal matrix with positive eigenvalues . Hence, under the condition that the covariance matrix is positive definite, the required decorrelation matrix (also called a whitening matrix or Mahalanobis transform) can be computed as follows:

(21.20)

or

(21.21)

where is an arbitrary orthogonal matrix. This can be easily verified by substituting (21.20) or (21.21) into (21.18):

(21.22)

or

(21.23)

Alternatively, we can apply the Cholesky decomposition

(21.24)

where is a lower triangular matrix. The whitening (decorrelation) matrix in this case is

(21.25)

where is an arbitrary orthogonal matrix, since

(21.26)

In the special case when is colored Gaussian noise with , the whitening transform converts it into a white noise (i.i.d.) process. If the covariance matrix is positive semi-definite, we can take only the positive eigenvalues and the associated eigenvectors.

It should be noted that after pre-whitening of sensor signals , in the model , the new mixing matrix defined as is orthogonal (i.e., ), if source signals are uncorrelated (i.e., ), since we can write .

1.21.2.4 SVD

The Singular Value Decomposition (SVD) is a tool of both great practical and theoretical importance in signal processing and data analysis [40]. The SVD of a data matrix of rank-J with , assuming without loss of generality that , leads to the following matrix factorization

(21.27)

where the matrix contains the T left singular vectors, has nonnegative elements on the main diagonal representing the singular values and the matrix represents the I right singular vectors called the loading factors. The nonnegative quantities , sorted as can be shown to be the square roots of the eigenvalues of the symmetric matrix . The term is a rank-1 matrix often called the jth eigenimage of . Orthogonality of the SVD expansion ensures that the left and right singular vectors are orthogonal, i.e., and , with the Kronecker delta (or equivalently and ).

In many applications, it is more practical to work with the truncated form of the SVD, where only the first , (where J is the rank of , with ) singular values are used, so that

(21.28)

where and . This is no longer an exact decomposition of the data matrix , but according to the Eckart-Young theorem it is the best rank-P approximation in the least-squares sense and it is still unique (neglecting signs of vectors ambiguity) if the singular values are distinct.

For noiseless data, we can use the following decomposition:

(21.29)

where and . The set of matrices represents this signal subspace and the set of matrices represents the null subspace or, in practice for noisy data, the noise subspace. The J columns of , corresponding to these non-zero singular values that span the column space of , are called the left singular vectors. Similarly, the J columns of are called the right singular vectors and they span the row space of . Using these terms the SVD of can be written in a more compact form as:

(21.30)

Perturbation theory for the SVD is partially based on the link between the SVD and the PCA and symmetric Eigenvalue Decomposition (EVD). It is evident, that from the SVD of the matrix with rank-, we have

(21.31)

(21.32)

where and . This means that the singular values of are the positive square roots of the eigenvalues of and the eigenvectors of are the left singular vectors of . Note that if , the matrix will contain at least additional eigenvalues that are not included as singular values of .

An estimate of the covariance matrix corresponding to a set of (zero-mean) observed vectors may be computed as . An alternative equivalent way of computing is to form a data matrix and represent the estimated covariance matrix by . Hence, the eigenvectors of the sample covariance matrix are the left singular vectors of and the singular values of are the positive square roots of the eigenvalues of .

From this discussion it follows that all the algorithms for PCA and EVD can be applied (after some simple tricks) to the SVD of an arbitrary matrix without any need to directly compute or estimate the covariance matrix. The opposite is also true; the PCA or EVD of the covariance matrix can be performed via the SVD numerical algorithms. However, for large data matrices , the SVD algorithms usually become more costly, than the relatively efficient and fast PCA adaptive algorithms. Several reliable and efficient numerical algorithms for the SVD do however, exist [48].

The approximation of the matrix by a rank-1 matrix of two unknown vectors and , normalized to unit length, with an unknown scaling constant term , can be presented as follows:

(21.33)

where is the matrix of the residual errors . In order to compute the unknown vectors we minimize the squared Euclidean error as [49]

(21.34)

The necessary conditions for the minimization of (21.34) are obtained by equating the gradients to zero:

(21.35)

(21.36)

These equations can be expressed as follows:

(21.37)

It is interesting to note that (taking into account that (see Eq. (21.37)) the cost function (21.34) can be expressed as [49]

(21.38)

In matrix notation the cost function can be written as

(21.39)

where the second term is called the Rayleigh quotient. The maximum value of the Rayleigh quotient is exactly equal to the maximum eigenvalue .

Taking into account that the vectors are normalized to unit length, that is, and , we can write the above equations in a compact matrix form as

(21.40)

or equivalently (by substituting one of Eq. (21.40) into another)

(21.41)

which are classical eigenvalue problems which estimate the maximum eigenvalue with the corresponding eigenvectors and . The solutions of these problems give the best first rank-1 approximation of Eq. (21.27).

In order to estimate the next singular values and the corresponding singular vectors, we may apply a deflation approach, that is,

(21.42)

where . Solving the same optimization problem (21.34) for the residual matrix yields the set of consecutive singular values and corresponding singular vectors. Repeating the reduction of the matrix yields the next set of solution until the deflation matrix becomes zero. In the general case, we have:

(21.43)

Using the property of orthogonality of the eigenvectors and the equality , we can estimate the precision of the matrix approximation with the first pairs of singular vectors [49]:

(21.44)

and the residual error reduces exactly to zero when the number of singular values is equal to the matrix rank, that is, for . Thus, we can write for the rank-J matrix:

(21.45)

Note that the SVD can be formulated as the following constrained optimization problem:

(21.46)

The cost function can be expressed as follows:

(21.47)

Hence, for (with and ) the problem (21.46) (called the best rank-1 approximation):

(21.48)

can be reformulated as an equivalent maximization problem (called the maximization variance approach):

(21.49)

with a maximal singular value .

1.21.2.5 Very large-scale PCA/SVD

Suppose that is the SVD decomposition of an -dimensional matrix, where T is very large and I is moderate. Then matrices and can be obtained form EDV/PCA decomposition of the -dimensional matrix . The orthogonal matrix can be then obtained from .

Moreover, if the vector is an eigenvector of the matrix , then is an eigenvector of , since we can write

(21.51)

In many practical applications dimension could be so large that the data matrix can not be loaded into the memory of moderate class of computers. The simple solution is to partition of data matrix into, say, Q slices as , where the size of the qth slice and can be optimized depending on the available computer memory [50,51]. The scaled covariance matrix (cross matrix product) can be then calculated as

(21.52)

since , where are orthogonal matrices. Instead of computing the whole right singular matrix , we can perform calculations on the slices of the partitioned data matrix as for . The concatenated slices form the matrix of the right singular vectors . Such approach do not require loading the entire data matrix at once in the computer memory but instead use a sequential access to dataset. Of course, this method will work only if the dimension T is moderate, typically less than 10,000 and the dimension I can be theoretically arbitrary large.

1.21.2.6 Basic algorithms for PCA/SVD

There are three basic or fundamental methods to compute PCA/SVD:

All the above approaches are connected or linked and almost equivalent. Often we impose additional constraints such as sparseness and/or nonnegativity (see Section 1.21.2.6.3).

1.21.3.1 The AMUSE algorithm and its properties

AMUSE (Algorithm for Multiple Unknown Signal Extraction) is probably the simplest BSS algorithm which belongs to the group of Second-Order Statistics Spatio-Temporal Decorrelation (SOS-STD) algorithms [14,81]. It provides similar decompositions for noiseless data to the well known and popular SOBI and TDSEP algorithms [82,83]. This class of algorithms are sometimes classified or referred to as ICA algorithms. However, these algorithms do not exploit implicitly or explicitly the statistical independence. Moreover, in contrast to standard higher order statistics ICA algorithms, they are able to estimate colored Gaussian distributed sources and their performance in estimation of original sources is usually better if the sources have temporal structures.

The AMUSE algorithm has some similarity with the standard PCA. The main difference is that the AMUSE employs PCA two times in two separate steps: In the first step, standard PCA is applied for the whitening (sphering) of the data and in the second step PCA is applied to the time delayed covariance matrix of the pre-whitened data. Mathematically the AMUSE algorithm consists of the following two stage procedure: In the first step we apply standard or robust prewhitening as a linear transformation , where of the standard covariance matrix , and is a vector of observed data for time point t. Next, (for the pre-whitened data) the SVD is applied for the time-delayed covariance matrix (typically, with ), where is a diagonal matrix with decreasing singular values and are orthogonal matrices containing the of left and right singular vectors. Then, an unmixing (separating) matrix is estimated as .

The main advantages of the AMUSE algorithm over the other BSS/ICA algorithms is its simplicity and that it allows the automatic ordering of the components, due to application of SVD. In fact, the components are ordered according to the decreasing values of the singular values of the time-delayed covariance matrix. In other words, the AMUSE algorithm exploits the simple principle that the estimated components tends to be less complex or more precisely that they have better linear predictability than any mixture of those sources. It should be emphasized that all components estimated by AMUSE are uniquely defined and consistently ranked. The consistent ranking is due to the fact that these singular values are always ordered in decreasing values. For real-world data probability that two singular values achieve exactly the same value is very small, so ordering is consistent and unique [14]. The one disadvantage of the AMUSE algorithm it is that is very sensitive to additive noise since the algorithm exploits only one time delayed covariance matrix.

1.21.3.2 The SOBI algorithm and its extensions

The second-order blind identification (SOBI) algorithm is a classical blind source separation (BSS) algorithm for wide-sense stationary (WSS) processes with distinct spectra [82]. This algorithm has proven to be very useful in biomedical applications and it has became more popular than the other algorithms.

There is a common practice in ICA/BSS research to exploit the “average eigen-structure” of a large set of data matrices formed as functions of the available data (typically, covariance or cumulant matrices for different time delays). In other words, the objective is to extract reliable information (e.g., estimation of sources and/or of the mixing matrix) from the eigen-structure of a possibly large set of data matrices [14,82,84,85]. However, since in practice we only have a finite number of samples of signals corrupted by noise, the data matrices do not exactly share the same eigen-structure. Furthermore, it should be noted that determining the eigen-structure on the basis of one or even two data matrices usually leads to poor or unsatisfactory results, because such matrices, based usually on an arbitrary choice, may have degenerate eigenvalues leading to loss of the information contained in other data matrices. Therefore, from a statistical point of view, in order to provide robustness and accuracy, it is necessary to consider the average eigen-structure by taking into account simultaneously a possibly large set of data matrices [14,85].

The average eigen-structure can be easily implemented via the linear combination of several time-delayed covariance matrices and by applying the standard EVD or SVD. An alternative approach to EVD/SVD is to apply the approximate joint diagonalization procedure (JAD). The objective of this procedure is to find the orthogonal matrix which diagonalizes a set of matrices [82,84,85]:

(21.113)

where are data matrices (for example, time-delayed covariance matrices), the are diagonal and real, and represent additive errors (as small as possible). If for arbitrary matrices , the problem becomes overdetermined and generally we can not find an exact diagonalizing matrix with . An important advantage of the Joint Approximate Diagonalization (JAD) is that several numerically efficient algorithms exist for its computation, including Jacobi techniques (one sided and two sided), Alternating Least Squares (ALS), PARAFAC (Parallel Factor Analysis) and subspace fitting techniques employing the efficient Gauss–Newton optimization [85]. This idea has been implemented as a robust SOBI algorithm which can be briefly outlined as follows [14,86]:

The main advantage of the SOBI algorithm is its robustness with respect to additive noise if number of covariance matrices is sufficiently large (typically, ).

Several extensions and modifications of the SOBI algorithm have been proposed, e.g., Robust SOBI [14], thinICA [87], and WASOBI [88,89] (the weights-adjusted variant of SOBI), which is asymptotically optimal (in separating Gaussian parametric processes). The WASOBI for the separation of independent stationary sources is modeled as Auto-Regressive (AR) random processes. The matrices are computed for the case of Gaussian sources, for which the resulting separation would be asymptotically optimal approaching the corresponding Cramer-Rao bound (CRB) for the best possible separation [88,90].

1.21.3.3 ICA based on higher order statistics (HOS)

The ICA of a random vector can be performed by finding an , (with ), full rank separating (transformation) matrix , such that the output signal vector (components) estimated by

(21.115)

are as independent as possible as evaluated by an information-theoretic cost function such as the minimum of the Kullback-Leibler divergence [14,17,91,92].

The statistical independence of random variables is a more general concept than decorrelation. Roughly speaking, we say that the random variables and are statistically independent if knowledge of the value of provides no information about the values of . Mathematically, the independence of and can be expressed by the relationship

(21.116)

where denotes the probability density function (pdf) of the random variable x. In other words, signals are independent if their joint pdf can be factorized.

If independent signals are zero-mean, then the generalized covariance matrix of and , where and are different, odd nonlinear activation functions (e.g., and for super-Gaussian sources) is a non-singular diagonal matrix:

(21.117)

i.e., the covariances are all zero. It should be noted that for odd and , if the probability density function of each zero-mean source signal is even, then the terms of the form equal zero. The true general condition for the statistical independence of signals is the vanishing of all high-order cross-cumulants [93–95]. The diagonalization principle can be expressed as

(21.118)

where is any diagonal positive definite matrix (typically, ). By pre-multiplying the above equation by the matrices and , we obtain:

(21.119)

which suggests the following simple iterative multiplicative learning algorithm [96]

(21.120)

(21.121)

where the last equation represents the symmetric orthogonalization that keeps the algorithm stable. The above algorithm is very simple, but it needs the prewhitening of the sensor data and it is sensitive to noise [14,97].

Assuming prior knowledge of the source distributions , we can estimate by using maximum likelihood (ML):

(21.122)

Using the gradient descent of the likelihood we obtain the infomax update rule

(21.123)

where and is an entry-wise nonlinear score function defined by:

(21.124)

Using the natural gradient descent to increase the likelihood we get [98]:

(21.125)

Alternatively, for signals corrupted by additive Gaussian noise, we can use higher order matrix cumulants. As an illustrative example, let us consider the following cost function which is a measure of independence [99]:

(21.126)

where we use the following notations: denotes the q-order cumulants of the signal and denotes the cross-cumulant matrix whose elements are .

The first term in (21.126) assures that the determinant of the global matrix will not approach zero. By including this term we avoid the trivial solution . The second term forces the output signals to be as far as possible from Gaussianity, since the higher order cumulants are a natural measure of non-Gaussianity and they will vanish for Gaussian signals. It can be shown that for such a cost function, we can derive the following equivariant and robust (with respect to the Gaussian noise) algorithm [87,99,102]

(21.127)

where and .

A wide class of equivariant algorithms for ICA can be expressed in a general form as (see Table 21.1) [14]

(21.128)

where and the matrix can take different forms, for example with suitably chosen nonlinearities and [14,95,96,99].

It should be noted that ICA based on HOS can perform blind source separation, i.e., allows us to estimate the true sources only if they are all statistically independent and are non Gaussian (except possibly of one) [14,91].

1.21.3.4 Blind source extraction

There are two main approaches to solve the problem of blind source separation. The first approach, which was mentioned briefly in the previous section, is to simultaneously separate all sources. In the second approach, we extract the sources sequentially in a blind fashion, one by one, rather than separating them all simultaneously. In many applications a large number of sensors (electrodes, sensors, microphones or transducers) are available but only a very few source signals are the subject of interest. For example, in the modern EEG or MEG devices, we typically observe more than 100 sensor signals, but only a few source signals are interesting; the rest can be considered as interfering noise. In another example, the cocktail party problem, it is usually essential to extract the voices of specific persons rather than separate all the source signals of all speakers available (in mixing form) from an array of microphones. For such applications it is essential to apply reliable, robust and effective learning algorithms which enable us to extract only a small number of source signals that are potentially interesting and contain useful information.

The blind source extraction (BSE) approach has several advantages over the simultaneous blind separation/deconvolution, such as