Sequential blind extraction of instantaneously mixed sources

This paper presents a general approach to sequential blind extraction of instantaneously mixed sources for several major ill-conditioned cases as well as the regular case of full column rank mixing matrices. Four ill-conditioned cases are considered: The mixing matrix is square but singular; the number of sensors is less than that of sources; the number of sensors is larger than that of sources, but the column rank of the mixing matrix is deficient; and the number of sources is unknown and the column rank of the mixing matrix is deficient. First, a solvability analysis is presented for a general case. A necessary and sufficient condition for extractability is derived. A sequential blind extraction approach is then proposed to extract all theoretically separable sources. Next, a principle and a cost function based on fourth-order cumulants are presented for blind source extraction. By minimizing the cost function under a nonsingularity constraint of the extraction matrix, all theoretically separable sources can be extracted sequentially. Finally, simulation results are presented to demonstrate the validity and performance of the blind source extraction approach.

Related papers:

title: Independent component analysis, A new concept?
abstract: The independent component analysis (ICA) of a random vector consists of searching for a linear transformation that minimizes the statistical dependence between its components. In order to define suitable search criteria, the expansion of mutual information is utilized as a function of cumulants of increasing orders. An efficient algorithm is proposed, which allows the computation of the ICA of a data matrix within a polynomial time. The concept of ICA may actually be seen as an extension of the principal component analysis (PCA), which can only impose independence up to the second order and, consequently, defines directions that are orthogonal. Potential applications of ICA include data analysis and compression, Bayesian detection, localization of sources, and blind identification and deconvolution.

title: An Information-Maximization Approach to Blind Separation and Blind Deconvolution
abstract: We derive a new self-organizing learning algorithm that maximizes the information transferred in a network of nonlinear units. The algorithm does not assume any knowledge of the input distributions, and is defined here for the zero-noise limit. Under these conditions, information maximization has extra properties not found in the linear case (Linsker 1989). The nonlinearities in the transfer function are able to pick up higher-order moments of the input distributions and perform something akin to true redundancy reduction between units in the output representation. This enables the network to separate statistically independent components in the inputs: a higher-order generalization of principal components analysis. We apply the network to the source separation (or cocktail party) problem, successfully separating unknown mixtures of up to 10 speakers. We also show that a variant on the network architecture is able to perform blind deconvolution (cancellation of unknown echoes and reverberation in a speech signal). Finally, we derive dependencies of information transfer on time delays. We suggest that information maximization provides a unifying framework for problems in "blind" signal processing.

title: A novel blind deconvolution scheme for image restoration using recursive filtering
abstract: We present a novel blind deconvolution technique for the restoration of linearly degraded images without explicit knowledge of either the original image or the point spread function. The technique applies to situations in which the scene consists of a finite support object against a uniformly black, grey, or white background. This occurs in certain types of astronomical imaging, medical imaging, and one-dimensional (1-D) gamma ray spectra processing, among others. The only information required are the nonnegativity of the true image and the support size of the original object. The restoration procedure involves recursive filtering of the blurred image to minimize a convex cost function. We prove convexity of the cost function, establish sufficient conditions to guarantee a unique solution, and examine the performance of the technique in the presence of noise. The new approach is experimentally shown to be more reliable and to have faster convergence than existing nonparametric finite support blind deconvolution methods. For situations in which the exact object support is unknown, we propose a novel support-finding algorithm.

title: Blind separation of sources, part I: An adaptive algorithm based on neuromimetic architecture
abstract: The separation of independent sources from an array of sensors is a classical but difficult problem in signal processing. Based on some biological observations, an adaptive algorithm is proposed to separate simultaneously all the unknown independent sources. The adaptive rule, which constitutes an independence test using non-linear functions, is the main original point of this blind identification procedure. Moreover, a new concept, that of INdependent Components Analysis (INCA), more powerful than the classical Principal Components Analysis (in decision tasks) emerges from this work.

title: Adaptive Online Learning Algorithms for Blind Separation: Maximum Entropy and Minimum Mutual Information
abstract: There are two major approaches for blind separation: maximum entropy (ME) and minimum mutual information (MMI). Both can be implemented by the stochastic gradient descent method for obtaining the demixing matrix. The MI is the contrast function for blind separation; the entropy is not. To justify the ME, the relation between ME and MMI is first elucidated by calculating the first derivative of the entropy and proving that the mean subtraction is necessary in applying the ME and at the solution points determined by the MI, the ME will not update the demixing matrix in the directions of increasing the cross-talking. Second, the natural gradient instead of the ordinary gradient is introduced to obtain efficient algorithms, because the parameter space is a Riemannian space consisting of matrices. The mutual information is calculated by applying the Gram-Charlier expansion to approximate probability density functions of the outputs. Finally, we propose an efficient learning algorithm that incorporates with an adaptive method of estimating the unknown cumulants. It is shown by computer simulation that the convergence of the stochastic descent algorithms is improved by using the natural gradient and the adaptively estimated cumulants.

title: Blind identification and equalization based on second-order statistics: a time domain approach
abstract: A new blind channel identification and equalization method is proposed that exploits the cyclostationarity of oversampled communication signals to achieve identification and equalization of possibly nonminimum phase (multipath) channels without using training signals. Unlike most adaptive blind equalization methods for which the convergence properties are often problematic, the channel estimation algorithm proposed here is asymptotically ex-set. Moreover, since it is based on second-order statistics, the new approach may achieve equalization with fewer symbols than most techniques based only on higher-order statistics. Simulations have demonstrated promising performance of the proposed algorithm for the blind equalization of a three-ray multipath channel.

title: EVAM: an eigenvector-based algorithm for multichannel blind deconvolution of input colored signals
abstract: A new algorithm is proposed for the deconvolution of an unknown, possibly colored, Gaussian or nonstationary signal that is observed through two or more unknown channels described by rational system transfer functions. More specifically, not only the root (pole and zero) locations but also the orders of the channel transfer functions are unknown. It is assumed that the channel orders may be overestimated. The proposed algorithm estimates the orders and root locations of the channel transfer functions, therefore it can also be used in multichannel system identification problems. The input signal is allowed to be nonstationary and the channel transfer functions may be a nonminimum phase as well as noncausal, hence the proposed algorithm is particularly suitable for applications such as dereverberation of speech signals recorded through multiple microphones. Several experimental results indicate improvement compared to the existing methods in the literature.

title: Self-adaptive source separation. II. Comparison of the direct, feedback, and mixed linear network
abstract: For pt.I see ibid., vol.45, p.918-26 (1997). Macchi and Moreau (1997) investigated stability and convergence of a new direct linear adaptive neural network intended for separating independent sources when it is controlled by the well-known Herault-Jutten algorithm. In this second part, we study the corresponding feedback adaptive network. For two globally sub-Gaussian sources, the network achieves quasi-convergence in the mean square sense toward a separating state. A novel mixed adaptive direct/feedback network that is free of implementation constraints is investigated from the points of view of stability and convergence and compared with the direct and feedback networks. The three networks have the same (low) complexity. The mixed one achieves the best trade-off between convergence speed and steady-state separation performance, independently of the specific mixture.

title: Blind separation of sources using higher-order cumulants
abstract: In this paper, we propose a novel method of blind signal separation using a new performance criterion with nonlinear separating functions, and derive an adaptive algorithm. The criterion consists of nonlinear mappings of output signals and their cumulants for independence of the signals. We show that our method requires a weak condition for stable separation through the ODE analysis. Simulation results are given to verify the validity and advantage of the proposed algorithm.

title: Fourth-order criteria for blind sources separation
abstract: Various criteria based on contrast functions as well as higher order statistics are used for solving the problem of blind separation of sources. In the paper, for the case of instantaneous mixtures of two sources, it is proved that the minimization or the cancellation of a really simple criterion, a fourth-order cross-cumulant, leads to a set of solutions whose spurious ones can be simply cancelled by using a decorrelation.

title: Source separation using a criterion based on second-order statistics
abstract: It is often assumed that blind separation of dynamically mixed sources cannot be done with second-order statistics. It is shown that separation of dynamically mixed sources indeed can be performed using second-order statistics only. A criterion based on second-order statistics for the purpose of separating crosswise mixtures is stated. The criterion is used in order to derive a gradient-based separation algorithm, as well as a Newton-type separation algorithm. The uniqueness of the solution representing the separation is also investigated. This reveals that (1) the channel system is parameter identifiable under weak conditions, and (2) if the sources have the same color, there exists at most two solutions. The local convergence behavior of the proposed algorithm is studied and reveals a sufficient condition for local convergence. Furthermore, the estimates of the channel system are shown to be consistent or to locally minimize the criterion.

title: Adaptive blind separation of independent sources: A deflation approach
abstract: In this paper, we address the adaptive blind source separation of independent sources using higher order statistics. Although this problem was considered in numerous works, none of the existing algorithms is guaranteed to converge to a relevant solution. Here, we propose a new separation scheme whose convergence is proved analytically. It is based on the observation that it is possible to extract one of the source signals by a simple algorithm obtained by extending to the source separation context some of the ideas developed by Shalvi-Weinstein in the framework of blind deconvolution. A low cost deflation procedure allows the extraction of the other source signals by means of the same algorithm. A statistical study of the performance of the new method is also presented.

title: Simple Neuron Models for Independent Component Analysis
abstract: Recently, several neural algorithms have been introduced for Independent component Analysis. Here we approach the problem from the point of view of a single neuron. First, simple Hebbian-like learning rules are introduced for estimating one of the independent components from sphered data. Some of the learning rules can be used to estimate an independent components which has a negative kurtosis, and the others estimate a component of positive kurtosis. Next, a two-unit system is introduced to estimate an independent component of any kurtosis. The results are then generalized to estimate independent components from non-sphered (raw) mixtures. To separate several independent components, a system of several neurons with linear negative feedback is used. The convergence of the learning rules is rigorously proven without any unnecessary hypotheses on the distribution of the independent components.

title: Blind signal extraction using self-adaptive nonlinear Hebbian learning rule
abstract: A simple neural network with local, biologically plausible , non-linear Hebbian learning rule is developed to perform sequential extraction of independent signals from a linear mixture of them. Instead of separating all signals simultaneously, we rather extract them sequentially using a new de BLOCKINation technique. It is shown that with suitable designed nonlinear functions and applying self-normalization principle, we are able to extract source signals with (specied) predened order (e.g., extracting signals according to the maximum absolute value of normalized kurtosis). Computer simulation experiments conrm the validity of the proposed algorithm and demonstrate that it is useful extension of existing neural network solutions to blind separation problem as extraction of particular source signals with predened stochastic characteristic is possible.

title: Adaptive unsupervised extraction of one component of a linear mixture with a single neuron
abstract: Extracting one specific component of a linear mixture is to isolate it due to the observation of several mixtures of all the components. This is done in an unsupervised way, based on the sole knowledge that the components are independent. The classical solution is independent component analysis which extracts the components all at the same time. In this paper, given at least as many sensors as components, we propose a simpler approach which independently extracts each component with one neuron. The weights of the neuron are optimized by minimizing an even polynomial of its output. The corresponding adaptive algorithm is an extended anti-Hebbian rule with very low complexity. It can extract any specific negative kurtosis component. Global stability of the algorithm is investigated as well as steady-state fluctuations. The influence of additive noise is also considered. These theoretical results are thoroughly confirmed by computer simulations.

title: Blind extraction of singularly mixed source signals
abstract: This paper introduces a novel technique for sequential blind extraction of singularly mixed sources. First, a neural-network model and an adaptive algorithm for single-source blind extraction are introduced. Next, extractability analysis is presented for singular mixing matrix, and two sets of necessary and sufficient extractability conditions are derived. The adaptive algorithm and neural-network model for sequential blind extraction are then presented. The stability of the algorithm is discussed. Simulation results are presented to illustrate the validity of the adaptive algorithm and the stability analysis. The proposed algorithm is suitable for the case of nonsingular mixing matrix as well as for singular mixing matrix.

title: Blind extraction of source signals with specified stochastic features
abstract: We present a neural-network approach which allows sequential extraction of source signals from a linear mixture of multiple sources in the order determined by absolute values of normalized kurtosis. To achieve this, we develop a non-linear Hebbian learning rule for extraction of a single signal. We discuss several techniques which enable extraction of signals not randomly but in the desired order. To prevent the same signals from being extracted several times, a robust deflation technique is used which eliminates from the mixture the already extracted signals. Extensive computer simulations confirm the validity and high performance of our method.

title: General approach to blind source separation
abstract: This paper identifies and studies two major issues in the blind source separation problem: separability and separation principles. We show that separability is an intrinsic property of the measured signals and can be described by the concept of m-row decomposability introduced in this paper; we also show that separation principles can be developed by using the structure characterization theory of random variables. In particular, we show that these principles can be derived concisely and intuitively by applying the Darmois-Skitovich theorem, which is well known in statistical inference theory and psychology. Some new insights are gained for designing blind source separation filters.

title: A cumulant-based super-exponential algorithm for blind deconvolution of multi-input multi-output systems
abstract: In this paper, a cumulant-based method for blind deconvolution of a multi-input multi-output system is proposed. The core of the method is an algorithm which extracts one of the input signals using the output signals as data only. This algorithm is a non-trivial generalization of the Shalvi–Weinstein algorithm for single-input single-output blind deconvolution and converges in super-exponential rate after a finite number of iterations. By using this algorithm recursively, all the input signals can be extracted. In its basic form, the algorithm applies when the input signals are non-Gaussian independent identical distributed. The algorithm is also extended to the case where the input signals are general regular processes. Computer simulation results are presented to demonstrate the convergence behavior of the proposed method as well as its efficacy for blind deconvolution.

title: Equivariant adaptive source separation
abstract: Source separation consists of recovering a set of independent signals when only mixtures with unknown coefficients are observed. This paper introduces a class of adaptive algorithms for source separation that implements an adaptive version of equivariant estimation and is henceforth called equivariant adaptive separation via independence (EASI). The EASI algorithms are based on the idea of serial updating. This specific form of matrix updates systematically yields algorithms with a simple structure for both real and complex mixtures. Most importantly, the performance of an EASI algorithm does not depend on the mixing matrix. In particular, convergence rates, stability conditions, and interference rejection levels depend only on the (normalized) distributions of the source signals. Closed-form expressions of these quantities are given via an asymptotic performance analysis. The theme of equivariance is stressed throughout the paper. The source separation problem has an underlying multiplicative structure. The parameter space forms a (matrix) multiplicative group. We explore the (favorable) consequences of this fact on implementation, performance, and optimization of EASI algorithms.

title: Cumulant-based blind identification of linear multi-input-multi-output systems driven by colored inputs
abstract: The blind identification problem of a linear multi-input-multi-output (MIMO) system is widely noticed by many researchers in diverse fields due to its relevance to blind signal separation. However, such a problem is ill-posed and has no unique solution. Therefore, we can only find a solution of the problem within an equivalence class. We address the blind identification problem of the linear MIMO system driven by unobservable colored inputs using higher order statistics (HOS), particularly the fourth-order cumulants, of the outputs, where the unobservable inputs are mutually independent but temporally colored linear processes. We first define the set, which is denoted by S, of stable scalar transfer functions and then define the notion of a generalized permutation matrix (which is abbreviated by a g-matrix) over S. Then, it is shown that the transfer function matrix of an unknown system is identified only up to post-multiplication by a g matrix. This result is applied to identifying FIR systems for blind signal separation.

title: Blind source separation for convolutive mixtures
abstract: Blind separation of sources is now a well known problem, and various methods have been proposed for instantaneous mixtures, and convolutive mixtures of narrow-band sources. In this paper, we present adaptive algorithms for separation of wide-band signals, for convolutive mixtures modeled by Finite Impulse Response (FIR) filters. The algorithms estimate coefficients of FIR filters using independence criteria. Under the condition of fourth-order white noise, we prove in this paper that the estimation of filter coefficients may be based on the cancellation of 4th-order output cross-cumulants. However, simpler algorithms only using a few fourth-order cross-cumulants or moments, and 2nd-order moments have the same efficacy. Finally, experimental results point out good performance (about -20 dB of residual crosstalk) even with nonwhite and nonstationary signals like speech signal for simulated mixtures. For recorded mixtures, results are not as good and suggest that the FIR model of mixtures is not realistic enough and must be improved.

title: High order contrasts for self-adaptive source separation criteria for complex source separation
abstract: This paper is concerned with the problem of separating independent non-Gaussian sources. This is done by adaptively maximizing a contrast function based on fourth-order cumulants of the (mixed) observations. The first class of solutions involves a first stage where the signal vector is adaptively whitened. In order to implement in the second stage the proper separating task, new contrast functions are proposed, especially when all the source kurtosises have the same sign. These contrasts involve only self-cumulants of the outputs. The second class of solutions requires a single separating stage. However, the associated contrasts involve cross-cumulants in addition to self-cumulants. They essentially apply to correlated vectors with normalized powers (rather than to white vectors). The resulting adaptive one-stage and two-stage systems achieve satisfactory separation performance independently of the statistics of sources and of the kind of linear mixture.

title: Sequential blind signal extraction in order specified by stochastic properties
abstract: A new neural-network adaptive algorithm is proposed for performing extraction of independent source signals from a linear mixture of them. Using a suitable nonlinear Hebbian learning rule and a new deflation technique, the developed neural network is able to extract the source signals (sub-Gaussian and/or super-Gaussian) one-by-one with specified order according to their stochastic properties, namely, in decreasing order of absolute normalised kurtosis. The validity and performance of the algorithm are confirmed through extensive computer simulations.

title: Neural networks for blind decorrelation of signals
abstract: We analyze and extend a class of adaptive networks for second-order blind decorrelation of instantaneous signal mixtures. First, we compare the performance of the single-layer neural network employing global knowledge of the adaptive coefficients with a similar structure whose coefficients are adapted via local output connections. Through statistical analyzes, the convergence behaviors and stability bounds for the algorithms' step sizes are studied and derived. Second, we analyze the behaviors of locally adaptive multilayer decorrelation networks and quantify their performances for poorly conditioned signal mixtures. Third, we derive a robust locally adaptive network structure based on a posteriori output signals that remains stable for any step-size value. Finally, we present an extension of the locally adaptive network for linear-phase temporal and spatial whitening of multichannel signals. Simulations verify the analyses and indicate the usefulness of the locally adaptive networks for decorrelating signals in space and time.