PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Independent Component Analysis by Iterative Maximization of the Kurtosis Contrast with Algebraic Optimal Step Size

Vicente Zarzoso, Pierre Comon

arXiv:1002.3684v1stat.ML

TL;DR

RobustICA addresses the difficult balance between convergence speed and final accuracy in optimal step-size iterative methods. It uses an optimal step-size approach for kurtosis-based ICA, providing high convergence speed, including single-iteration convergence in the real-valued two-signal case without prewhitening, while supporting real- and complex-valued sources and increased robustness to initialization and saddle points.

  • Problem

    Optimal step-size iterative methods face a difficult balance between convergence speed and final accuracy, or misadjustment.

  • Method

    RobustICA uses an optimal step-size approach in a kurtosis-based ICA method, with the step-size computation forming part of each filter-update iteration.

  • Results

    RobustICA shows very high convergence speed measured by source extraction quality versus number of operations; in the real-valued two-signal case, it converges in a single iteration without prewhitening.

  • Takeaways & Limitations

    The method processes real- and complex-valued, possibly noncircular sources without prewhitening and shows increased robustness to initialization and saddle points, particularly in small observation windows.

Abstract

from arXiv · show

Independent component analysis (ICA) aims at decomposing an observed random vector into statistically independent variables. Deflation-based implementations, such as the popular one-unit FastICA algorithm and its variants, extract the independent components one after another. A novel method for deflationary ICA, referred to as RobustICA, is put forward in this paper. This simple technique consists of performing exact line search optimization of the kurtosis contrast function. The step size leading to the global maximum of the contrast along the search direction is found among the roots of a fourth-degree polynomial. This polynomial rooting can be performed algebraically, and thus at low cost, at each iteration. Among other practical benefits, RobustICA can avoid prewhitening and deals with real- and complex-valued mixtures of possibly noncircular sources alike. The absence of prewhitening improves asymptotic performance. The algorithm is robust to local extrema and shows a very high convergence speed in terms of the computational cost required to reach a given source extraction quality, particularly for short data records. These features are demonstrated by a comparative numerical analysis on synthetic data. RobustICA's capabilities in processing real-world data involving noncircular complex strongly super-Gaussian sources are illustrated by the biomedical problem of atrial activity (AA) extraction in atrial fibrillation (AF) electrocardiograms (ECGs), where it outperforms an alternative ICA-based technique.

I. INTRODUCTION

ICA seeks to recover statistically independent sources from observed mixtures, while kurtosis-based methods offer tractable separation but face limitations involving prewhitening, source type, and finite samples.

  • ICA estimates unobservable source signals from observed mixtures under an independence assumption.
  • Kurtosis is widely used because it is mathematically tractable, computationally convenient, and robust to finite-sample effects.
  • FastICA offers cubic global convergence asymptotically, but short samples can slow convergence and trap iterations near saddle points or local extrema.
  • Conventional higher-order processing commonly relies on prewhitening, which can impose separation-performance limits and introduce estimation bias from residual correlations.

D. The Complex-Valued Scenario

The paper develops RobustICA for deflationary ICA using a general kurtosis contrast, targeting real or complex sources without requiring prewhitening. Its optimal step-size search improves robustness and cost-efficient convergence, including for noncircular complex sources.

  • RobustICA performs exact line search on the kurtosis contrast, selecting an algebraically computed globally optimal step size at each update.
  • The same algorithm handles real- and complex-valued mixtures, including mixtures containing noncircular complex sources.
  • RobustICA does not require prewhitening, avoiding the performance limitations associated with that preprocessing stage.
  • The method can target sub-Gaussian or super-Gaussian sources in a user-specified order, avoiding unnecessary full separation when source characteristics are known.
  • The optimal step-size approach provides robustness to saddle points and spurious local extrema, particularly for short observation windows.
  • In a biomedical application, RobustICA successfully extracts strongly super-Gaussian, noncircular complex atrial activity from atrial-fibrillation ECG recordings.

F. Related Work on Optimal Step-Size Iterative Methods

Prior step-size methods balance convergence speed against final accuracy, often through local or computationally intensive procedures. RobustICA instead uses a simple algebraic optimal-step approach for a general kurtosis contrast in batch ICA.

  • Step-size selection must balance convergence speed against final accuracy or misadjustment.
  • RobustICA globally optimizes a non-quadratic kurtosis contrast on the same stationary signal block through direct source-estimation iterations.
  • Earlier adaptive rules make the step size depend on gradient information but require additional learning coefficients whose selection remains application-dependent.
  • Some batch methods guarantee monotonic convergence, but their step-size bounds require computationally intensive Hessian-eigenspectrum calculations.
  • Its optimal step-size approach is valid for real and complex sources, requires no prewhitening, and is computationally simple.

II. FASTICA REVISITED

FastICA uses kurtosis-based optimization with prewhitening, normalization, and fixed-point or gradient-like updates. Its asymptotic speed is attractive, but short finite samples can produce slow convergence and local trapping.

  • Kurtosis maximization is a scale-invariant contrast, commonly optimized under a unit-norm constraint for numerical convenience.
  • The kurtosis contrast is general for real or complex-valued sources, whereas the fourth-order moment criterion requires prewhitening and real or circular complex sources.
  • FastICA first prewhitens observations, then applies a fixed-point update equivalent to a gradient-based rule with fixed step size µ = 1/12.
  • B. Contrast Optimization: The fixed-point equation is not self-determining because its Lagrange multiplier must satisfy the constraint and depends on the optimal extracting vector.
  • FastICA can achieve cubic convergence for infinite samples, but short samples may slow convergence or trap iterations in saddle areas and local extrema.
  • Deflationary orthogonalization projects each new extracting vector into the orthogonal subspace of previously extracted vectors.

C. The Complex Case

RobustICA applies algebraic exact line search to the kurtosis contrast, extending deflationary ICA to real and complex mixtures, including possibly noncircular sources, without mandatory prewhitening.

  • C. The Complex Case: RobustICA performs exact line-search optimization of the absolute kurtosis contrast along a search direction, typically the gradient.The optimal step size maximizes |K(w + µg)| along the search direction.
  • C. The Complex Case: Exact line search avoids numerical one-dimensional optimization methods that are not guaranteed to find the global optimum along the search direction.The paper identifies the algebraic polynomial formulation as the mechanism enabling practical exact optimization.
  • C. The Complex Case: The optimal step size is obtained from the roots of a fourth-degree polynomial using low-cost algebraic procedures.Ferrari’s formula can find the quartic roots at negligible cost relative to computing the required statistics.
  • C. The Complex Case: At each iteration, RobustICA computes polynomial coefficients, extracts its roots, selects the root giving the maximum contrast, updates w, and normalizes it.Normalization resolves the scale ambiguity of the contrast and is not a prewhitening operation.
  • C. The Complex Case: RobustICA can separate real and complex, possibly noncircular, sources without modification, whereas related complex FastICA variants may require circularity assumptions.The cited complex FastICA extension is valid only for second-order circular sources; nc-FastICA addresses noncircular sources through pseudo-covariance information.

B. Extraction of Sources with Known Kurtosis Sign

RobustICA can target sources with a known kurtosis sign, avoiding unnecessary extraction of other source types and reducing the costs and errors associated with sequential deflation.

  • B. Extraction of Sources with Known Kurtosis Sign: RobustICA maximizes absolute kurtosis by default but can target a source with a specified kurtosis sign.Root selection is modified to favor the required positive or negative kurtosis.
  • B. Extraction of Sources with Known Kurtosis Sign: Extracting only desired source types can avoid unnecessary computation and error accumulation through successive deflation stages.The paper presents exclusive extraction of the desired source type as an alternative to separating the whole mixture.
  • B. Extraction of Sources with Known Kurtosis Sign: If no source has the requested kurtosis sign, RobustICA may converge to a non-extracting local extremum while tending toward maximal or minimal remaining-subspace kurtosis.For ε = 1 it tends toward maximal kurtosis, and for ε = −1 toward minimal kurtosis.
  • B. Extraction of Sources with Known Kurtosis Sign: Known- and unknown-sign extraction can be combined in any desired order by alternating the corresponding global line-maximization criteria.The paper gives separate criteria for specified-sign and absolute-kurtosis extraction.
  • B. Extraction of Sources with Known Kurtosis Sign: For multiple components, RobustICA can use FastICA-style Gram-Schmidt orthogonalization under prewhitening, although prewhitening is not mandatory.A regression-based deflation procedure is also described for nonunitary mixtures without prewhitening.

D. A Quick Look at Convergence

RobustICA’s algebraic optimal-step search gives strong convergence guarantees in simple settings and improves cost-to-accuracy despite more expensive individual iterations.

  • D. A Quick Look at Convergence: The general convergence characteristics of RobustICA remain outside the paper’s theoretical study, and gradient orthogonality may hinder high-dimensional convergence.The strongest formal guarantees supplied here concern monotonic convergence and the real-valued two-signal case.
  • D. A Quick Look at Convergence: In real-valued two-signal mixtures, RobustICA reaches the global optimum in a single iteration, even without prewhitening.This result follows from the contrast’s scale invariance and a geometric analysis of the search direction.
  • D. A Quick Look at Convergence: In the two-signal case, varying the step size spans the full solution space up to sign and scale ambiguities, enabling global optimization in one step.The result is not easily generalized to more than two signals.
  • D. A Quick Look at Convergence: The optimal-step procedure guarantees at least monotonic convergence of the kurtosis contrast to a local extremum for any initialization.The paper notes that gradient-vector orthogonality may slow convergence in high-dimensional extracting-vector spaces.
  • D. A Quick Look at Convergence: Although RobustICA iterations generally cost more than FastICA iterations, overall cost is lower for the same extraction accuracy, and FastICA may not reach that accuracy.The paper evaluates complexity using floating-point operation counts rather than iteration number alone.

IV. EXPERIMENTAL ANALYSIS

Experiments compare RobustICA with FastICA and related variants on synthetic mixtures, showing especially strong robustness and cost-to-accuracy performance for short data records and no prewhitening.

  • IV. EXPERIMENTAL ANALYSIS: The experiments evaluate convergence, source-extraction quality, and computational complexity across several synthetic-data conditions.FastICA with cubic nonlinearity is the real-valued benchmark, while complex experiments compare variants handling noncircular sources.
  • IV. EXPERIMENTAL ANALYSIS: The synthetic evaluations average SMSE over 1000 independent realizations and compare direct processing with SVD-based prewhitening.The experiments use fixed termination and vary mixture size, sample-block length, and algorithmic configuration.
  • IV. EXPERIMENTAL ANALYSIS: RobustICA provides faster and more robust performance, especially for short data sizes, with robustness to initialization also demonstrated.The experiments connect these results to the lower finite-sample variance of kurtosis relative to the fourth-order moment.
  • IV. EXPERIMENTAL ANALYSIS: Without prewhitening, RobustICA achieved the best quality-cost trade-off in the wireless telecommunications simulation.For K = 5 sources, it reached below −60-dB SMSE; prewhitening worsened RobustICA’s trade-off.
  • IV. EXPERIMENTAL ANALYSIS: With prewhitening, FastICA improved considerably and became slightly faster than prewhitened RobustICA as mixture size increased.Avoiding prewhitening still allowed RobustICA to achieve improved performance bounds for short data sizes.

C. Efficiency

Under a fixed complexity budget, RobustICA reaches comparable or better extraction performance with smaller signal blocks and shows improved noise robustness. Prewhitening makes the methods more comparable, while RobustICA remains superior for complex noncircular mixtures without it.

  • Synthetic mixtures: 400 flops/source/sample fixes the overall complexity, so RobustICA uses fewer iterations because each iteration costs more than FastICA’s.The comparison varies block sample size and number of sources under this common computational budget.
  • Synthetic mixtures: For moderate K, RobustICA is considerably more efficient, achieving the same extraction performance with much smaller signal blocks.Its steeper SMSE curve indicates faster improvement as block size increases.
  • Synthetic mixtures: Prewhitening makes FastICA and RobustICA performance trends comparable, while FastICA becomes more efficient as K increases.The reported efficiency relationship changes with both prewhitening and the number of sources.
  • Noise robustness: At the same noise level, RobustICA improves SMSE or tolerates more noise without sacrificing performance.At high SNR it has a lower performance floor than FastICA and, with sufficient sample size, reaches the MMSE bound using three times fewer iterations.
  • Complex mixtures: Without prewhitening, RobustICA outperforms KM-F and nc-FastICA on complex-valued mixtures of noncircular sources.When both methods are prewhitened, their performances become similar because FastICA improves while RobustICA degrades.
  • Biomedical application: In the biomedical application, RobustICA’s kurtosis contrast gives satisfactory results for noncircular complex strongly super-Gaussian sources.This application addresses a setting where kurtosis-based methods had previously been discouraged because of concerns restricted to FastICA.

A. Atrial Activity Extraction in Atrial Fibrillation Episodes

Atrial fibrillation produces disorganized atrial activation, and extracting atrial activity from ECGs requires suppressing ventricular activity, artifacts, and noise. RobustICA separates frequency-domain components and identifies atrial activity in the typical AF band, yielding improved extraction quality at comparable complexity.

  • Clinical context: Atrial fibrillation replaces organized atrial wavefront propagation with wandering wavelets, impairing atrial function and increasing blood-clot and stroke risk.The disorder’s clinical significance motivates signal-based analysis of atrial activity.
  • Clinical context: AA extraction from ECGs requires suppressing ventricular activity, artifacts, and noise before analyzing the atrial source.PCA and ICA can separate statistically independent phenomena and reconstruct AA across leads.
  • Results: RobustICA obtains a more accurate AA estimate than FastICA in lead V1, as indicated by a higher spectral concentration value.For the illustrated patient, RobustICA finds AA in the third component, whereas FastICA finds it in the ninth.
  • Results: RobustICA achieves improved AA extraction quality with virtually identical dominant-frequency estimates at comparable complexity to the alternative two-stage technique.Stopped at AA extraction, it requires 62 ± 41 iterations or 241.3 ± 159.9 × 10^6 flops on average; its per-iteration cost is about an order of magnitude higher.
  • Source characteristics: The extracted frequency-domain sources are strongly super-Gaussian, with average kurtosis 231 compared with 731 for AA sources and circularity ratio 0.85±0.02.These measurements characterize the noncircular complex source setting used to demonstrate RobustICA’s biomedical applicability.

VI. CONCLUSIONS

RobustICA combines the kurtosis contrast with algebraic optimal step-size selection to provide deflationary source extraction without prewhitening. The method is especially effective for short data records and supports real or complex sources, including noncircular signals.

  • VI. CONCLUSIONS: RobustICA obtains the global contrast maximizer along each search direction algebraically at every filter-update iteration.The method uses optimal step-size selection on the kurtosis contrast.
  • VI. CONCLUSIONS: RobustICA processes real- and complex-valued, possibly noncircular sources without requiring prewhitening.This avoids performance limitations associated with whitening-based preprocessing and improves tolerance to residual source correlations in short records.
  • VI. CONCLUSIONS: RobustICA provides increased robustness to initialization and saddle points, particularly in small observation windows.The optimal step-size approach is linked to the method’s robustness in short-data settings.
  • VI. CONCLUSIONS: RobustICA reaches a given source-extraction quality with lower computational cost than kurtosis-based FastICA and some recent variants.Computational complexity is used as the convergence-speed measure, with benefits reported especially for short data records.
  • VI. CONCLUSIONS: RobustICA successfully extracts atrial activity from atrial-fibrillation ECG recordings containing noncircular complex strongly super-Gaussian sources.The paper presents this biomedical application as an illustration of the method’s practical usefulness.
  • VI. CONCLUSIONS: Further work includes extensions to convolutive mixtures and more robust cumulant estimates for handling outliers.The MIMO convolutive case requires appropriate deflation procedures, while improved cumulant estimates are proposed as an avenue for increasing outlier tolerance.

APPENDIX

The appendix derives RobustICA’s algebraic line-search step and documents experimental comparisons of extraction quality, computational cost, and biomedical application results.

  • Algebraic step-size derivation: K(w + µg) is expressed as a rational function of the step size µ along the search direction.The construction uses y+ = y + µg and polynomial quantities P(µ), P1(µ), and P2(µ).
  • Algebraic step-size derivation: The derivative of K(w + µg) with respect to µ yields a polynomial whose real roots are step-size candidates.Candidate roots are related to the polynomial defined by the preceding algebraic equations.
  • Algebraic step-size derivation: RobustICA evaluates the candidate roots in the contrast expression and selects the one giving the optimum absolute contrast value.The same selection procedure can use εK(w + µg) when the alternative procedure is employed.
  • Experimental comparisons: The experiments compare FastICA and RobustICA using extraction quality, computational complexity, mixture size, sample size, block length, and noise conditions.The appendix includes figures and tables covering real-valued mixtures, fixed-complexity comparisons, and algorithmic complexity per iteration.
  • Biomedical application: The atrial-activity experiment reports spectral concentration, dominant spectral-peak position, iterations, complexity, and estimated-source position over 35 ECG recordings.The ECG figures show the lead signal and AA estimates from FastICA-SOBI and RobustICA, with relative amplitudes on the vertical axes.
Loading 1002.3684v1…