Read an Excerpt
Handbook of Blind Source Separation
Independent Component Analysis and Applications
Academic Press
Copyright © 2010 Pierre Comon and Christian Jutten
All right reserved.
ISBN: 978-0-08-088494-3
Chapter One
Introduction C. Jutten and P. Comon
Blind techniques were born in the 1980s, when the first adaptive equalizers were designed for digital communications. The problem was to compensate for the effects of an unknown linear single input single output (SISO) stationary channel, without knowing the input.
The scientific community used the word "blind" for denoting all identification or inversion methods based on output observations only. In fact, blind techniques in digital communications aimed at working when the "eye was closed"; hence the terminology.
At the beginning, the word "unsupervised" was sometimes used (for instance in French the wording autodidacte), but it seems now better to be consistent with the worldwide terminology, even if this is not ideal, since comprehensible only in the context of digital communications.
The problem of blind source separation (BSS) differs from blind equalization, addressed previously by Sato, Godard and Benveniste, by the fact that the unknown linear system consists of several inputs and outputs: such a system is referred to as multiple inputs multiple outputs (MIMO). Initially restricted to memoryless channels, the BSS problem now encompasses all linear or nonlinear MIMO mixtures, with or without memory.
The BSS problem was first formulated in 1984, although theoretical principles, which drive source separation methods, were understood later. In this chapter, we briefly introduce the principles and main notations used in this book. A few ideas which contributed to the development of this research domain from its birth are reviewed. The present chapter ends with a short description of each of the 18 subsequent chapters.
1.1 GENESIS OF BLIND SOURCE SEPARATION
The source separation problem was formulated around 1982 by Bernard Ans, Jeanny Hérault and Christian Jutten, in the framework of neural modeling, for motion decoding in vertebrates. It seems that the problem has also been sketched independently in the framework of communications. First related contributions to Signal Processing conferences and to Neural Networks conferences appeared around 1985. Immediately, these papers drew the attention of signal processing researchers, mainly in France, and later in Europe. In the neural networks community, interest came much later, in 1995, but very massively.
Since the middle of the 1990s, the BSS problem has been addressed by many researchers, with expertise in various domains: signal processing, statistics, neural networks, etc. Numerous special sessions have been organized on these topics in international conferences, for instance in GRETSI since 1993 (France), NOLTA'95 (Las Vegas, USA), ISCAS (Atlanta, USA), EUSIPCO since 1996, NIPS'97 post workshop (Denver, USA), ESANN'97 (Bruges, Belgique), IWANN'99 (Alicante, Spain), MaxEnt2006 (Paris, France).
The first international workshop fully devoted to this topic, organized in Aussois in the French Alps in January 1999, attracted 130 researchers world-wide. After the first international papers, published in 1991 in the journal Signal Processing, various international journals contributed to the dissemination of BSS: Traitement du Signal (in French), Signal Processing, IEEE Transactions on Signal Processing, IEEE Transactions on Circuits and Systems, Neural Computation, Neural Networks, etc. In addition, a Technical Committee devoted to blind techniques was created in July 2001 in the IEEE Circuits and Systems Society, and BSS is a current "EDICS" in IEEE Transactions on Signal Processing, and in many conferences.
Initially, source separation was investigated for instantaneous (memoryless) linear mixtures. The generalization to convolutive mixtures was considered at the beginning of the 1990s. Finally, nonlinear mixtures, except a few isolated works, were addressed at the end of 1990s. In addition, independent component analysis (ICA), which corresponds to a general framework for solving BSS problems based on statistical independence of the unknown sources, was introduced in 1987, and formalized for linear mixtures by Comon in 1991. Beyond source separation, ICA can also be used for decomposition of complex data (signals, images, etc.) in sparse bases whose components have the mutual independence property. ICA also relates to works on sparse coding in theoretical biology presented by Barlow in 1961, and other works on factor analysis in statistics.
The number of papers published on the subject of BSS or ICA is enormous: in June 2009, 22,000 scientific papers are recorded by Google Scholar in Engineering, Computer Science, and Mathematics. On the other hand, few books present the BSS problem and the main principles for solving it. One can mention a book written by specialists of Neural Networks, containing only algorithms developed within the Machine Learning community. The present book aims at reporting the state of the art more objectively. A book with a wider scope is now certainly needed. Another rather complete book appeared slightly later. However, some ways of addressing the problem were still missing (semi-blind approaches, Bayesian approaches, Sparse Components Analysis, etc.), and we hope the present book will complement it efficiently. More specific problems, i.e. separation of audio sources, or separation in nonlinear mixtures, have been the subject of other contributions.
The present book is hopefully a reference for all aspects of blind source separation: problem statements, principles, algorithms and applications. The problem can be stated in various contexts including fully blind static (ICA), and convolutive or nonlinear mixtures. It can be addressed in blind or semi-blind contexts, using second-order statistics if sources are assumed colored or nonstationary, or using higher order statistics, or else using time-frequency representations. There is a wide variety of mathematical problems, depending on the hypotheses assumed. For instance, the case of underdetermined mixtures is posed in quite different terms for sparse sources; the Bayesian approach is quite different from approaches based on characteristic functions or cumulants, etc.
In the next section, we first present the biological problem which was at the origin of blind source separation, and locate it in the scientific context of the 1980s. Then, we explain how and why a few researchers became interested in this problem: the answers have been given by the researchers themselves, and this section is partly extracted from.
1.1.1 A biological problem
Blind source separation was first considered in 1982 from a simple discussion between Bernard Ans, Jeanny Hérault and Christian Jutten with Jean-Pierre Roll, a neuroscientist, about motion decoding in vertebrates. Joint motion is due to muscle contraction, each muscle fiber being controlled by the brain, through a motoneuron. In addition, on each fiber, the muscle contraction is measured, and transmitted to the central nervous system by two types of sensorial endings, located in tendon, and called primary and secondary endings. The proprioceptive responses of the two types of endings are presented in Figs 1.1 and 1.2 respectively, for simple joint motion, at constant angular speed. For reliability reasons, results are obtained by averaging unit sensory responses coming from a large number of fibers, related to the repetition of the same forced motion. Figures 1.1 and 1.2 present frequencygrams, i.e. a representation where a spike at time t is represented by a point at t on the x axis and with a value on y axis equal to the inverse of the interval between the spike and the previous one, i.e. corresponding to the instantaneous frequency. Following Roll, here are the main comments concerning the frequencygrams:
For a constant joint location, responses of the two endings are constant, i.e. the spike instantaneous frequency is constant. The instantaneous frequency is increasing with muscle stretching. The frequency/stretching ratio is similar, on the average, on the two types of endings. During a joint motion at constant (stretching) speed, the instantaneous frequency appears as the superimposition of the constant signal (for the speed) on the signal related to the muscle stretching. This is true for the two types of endings, with some differences. The response of primary endings is characterized by an initial burst (derivative effect), at the beginning of the motion, while the typical response of secondary endings is low-pass. On average, the ratio frequency/speed is larger for primary endings than for secondary ones.
Surprisingly, while we could imagine that each type of ending only transmits one type of information, either stretching or speed, the proprioceptive information transmitted by endings is a mixture of stretching and speed information.
Neglecting transient phenomena (high and low-pass effects), and denoting p(t) the angular position (related to muscle stretching), v(t) = dp(t)/dt the angular speed, and f1](t) and f2 (t) the instantaneous frequency of primay and secondary endings, respectively, one can propose the following model:
f1(t) = a11v(t) + a12p(t) f2(t) = a21v(t) + a22p(t) (1.1)
in which v(t), p(t) et aij are unknown, with the assumptions a11 > a12 and a22 > a21.
Estimating v(t) and p(t) from f1(t) and f2(t) seems impossible. However, even during forced motion, even with closed eyes, the central nervous system is able to separate joint speed and location while they are arriving as mixtures. As said by Mc Closkey in 1978: "Clearly, if spindle discharges are to be useful for kinesthetic sensations, the central nervous system must be able to distinguish which part of the activity is attributable to muscle stretch and which part is caused by fusimotor activity".
Denoting x(t) = (f1(t), (f2t))T and s(t) = (v(t), p(t))T, where T denotes transpose, and A the (mixing) matrix with general entry [aij, this model is an instantaneous linear mixture:
x(t) = As(t), (1.2)
in which we assume that the components (v(t) and p(t)) of the source vector s(t) are statistically independent. Source separation is then based on estimating a separating matrix B such that the vector y(t) = Bx(t) has mutually independent components. The first source separation algorithm was an adaptive algorithm based on a set of estimating equations, which cancelled higher (than 2) cross-moments of all the component pairs of the vector y(t), which is (under mild conditions) a simple independence criterion, as shown later.
1.1.2 Contextual difficulties
1.1.2.1 Independence
The first difficulty encountered for explaining the problem in the 1980s was related to statistical independence.
At first glance, this assumption seems very strong. In fact, we may think it rarely occurs, and it is more difficult to satisfy than second order independence i.e. noncorrelation. In the above biological problem, it was indeed tricky to explain statistical independence between p(t) and v(t). In fact, one can remark that "speed v(t) is related to location p(t) through v(t) = dp(t)/dt. The two variables then cannot be independent". However, this functional dependence is not a statistical dependence. The knowledge of p(t) at a given instant t does not provide any information on v(t), and vice versa. In other words, while the random vectors of speed and position, [v(t1),v([t2), ..., v(tk)]T and [p(t1), p(t2), ..., p(tk)T are generally not independent, the (marginal) random variables, v(t) and p(t), at any given time t are independent. Therefore, for instantaneous ICA algorithms, the dependence is irrelevant.
1.1.2.2 Second-order or higher-order statistics
Relationships between statistical independence and non-correlation are presented in any textbook on probability. However, in the 1980s, most signal models were assumed to be Gaussian, so that concepts of independence and non-correlation are the same. Fortunately, about at the same time, an increasing interest in methods based on higher order statistics (HOS) manifested itself. As a by-product, differences between statistical independence and lack of second order correlation were recognized and exploited. The first international workshop on HOS was held in Vail (Colorado, USA) in 1989, and contributed to the expansion of blind techniques.
1.1.2.3 Separable or not?
In 1983, Bienvenu and Kopp showed that dominant eigenvectors of the spectral covariance matrix span the signal subspace, but cannot provide the sources. This result is based on algebraic arguments. Considering the extension of the linear model (1.2) from 2 mixtures of 2 sources (v(t) and p(t) in the above neurophysiological problem) to a larger (and equal) number of mixtures and sources, say N = P, the number of equations ((N2-N)/2) is smaller than the number of parameters ((N2-N)). Consequently, source separation has been considered as impossible to solve by most researchers for several years. During the poster session in GRETSI 85, comments on raised surprise or skepticism. Two years later, in 1987, Lacoume, although he agreed with the results of Bienvenu and Kopp, thought that HOS (e.g. 4th order cumulants) could solve the problem, by introducing supplementary equations (like Nikias and others did in other problems). Some years later, he stated relationships governing source separation under the assumption of statistical independence. In particular, he designed (with Gaeta) a method based on maximum likelihood, in which source distributions were approximated by Gram-Charlier expansions. During the same period, others also achieved this with other approaches (see Vail workshop in 1989). However, it can be observed that it took the scientific community nearly three years to realize that the separation problem could indeed be solved.
1.1.2.4 Source separation and neural networks
In 1985 and 1986, the first studies on source separation were presented in neural network conferences, Cognitiva '85 (Paris, France) and Snowbird '86 (Utah, USA). These communications attracted the interest of a few reseachers, but have been outshined by new interesting studies. For instance, at Cognitiva '85, Le Cun [49] published a new learning algorithm for multi-layer perceptrons (MLP) which became famous as the backpropagation algorithm. During Snowbird '86, most researchers were very excited by Hopfield models, Kohonen's self-organizing maps, MLP and backpropagation algorithms. For instance, Terry Sejnowski presented a nice exhibition of NetTalk, showing MLP applications. But during this conference, he began to be interested in source separation as he explained in 2000: "Because I did not understand why your network model could get the results that it did, new students in my lab often were offered that question as a research problem. Shaolin Li, a Chinese postdoc, made some progress by combining beamforming with your algorithm. This project was started around 1991."
1.1.2.5 Terminology
Keywords source separation and independent component analysis (ICA) have not been used from the beginning. For instance, first papers had very long and intricate titles as in GRETSI'85, whose English translation is: Detection of primary signals in a composite message using a neuromimetic architecture with unsupervised learning. In 1986, the word source discrimination was used, but the keyword source separation became accepted only after 1987. Blind techniques also received a strange wording by P. Duvaut in 1990, whose English translation corresponds to: "clairvoyant methods". Concerning ICA, the word was first introduced in 1987 but the concept was formalized later by Comon in 1991.
(Continues...)
Excerpted from Handbook of Blind Source Separation Copyright © 2010 by Pierre Comon and Christian Jutten. Excerpted by permission of Academic Press. All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
