Understanding Independent Component Analysis and Particle Filters

Posted on Dec 7, 2025 in Mathematics and Computer Science

Independent Component Analysis (ICA)

ICA is a statistical technique used to separate a multivariate signal into independent, non-Gaussian components. It assumes the observed data are linear mixtures of independent source signals.

Mathematically, X = A S

where X is the observed mixed signals, A is the unknown mixing matrix, and S is the statistically independent source signals.

The aim is to estimate A and S such that S = W X, where W is the separating matrix.

Steps in ICA

  1. Centering: Subtract mean to make data zero-centered.
  2. Whitening: Transform data to make components uncorrelated with unit variance.
  3. Rotation: Find W to make transformed variables statistically independent.

Example: If multiple microphones record a mix of voices, ICA separates each speaker’s voice — known as the ‘cocktail party problem.’

Applications of ICA

  • Dimensionality reduction
  • Noise removal
  • Feature extraction

Particle Filter (Sequential Monte Carlo Method)

Particle Filters estimate the state of a dynamic system when it is non-linear and non-Gaussian. The method represents the state using a set of random samples (particles) with associated weights.

Steps in Particle Filtering

  1. Initialization: Generate random particles for possible states with equal weights.
  2. Prediction: Predict the next state using a motion model and noise.
  3. Update: Update each particle’s weight based on the likelihood of the observation.
  4. Resampling: Discard low-weight particles and replicate high-weight ones.
  5. Estimation: Estimated state = weighted average of particles.

Formula: x̂_t = Σ (w_t^(i) * x_t^(i))

Example: Tracking an object’s position using noisy GPS data—each particle predicts possible locations, and weights are updated as new data arrives.

Advantages of Particle Filters

  • Handles non-linear systems
  • Robust to noise

Applications of Particle Filters

  • Robot localization
  • Visual tracking
  • Navigation systems

Nearest Neighbor Methods (k-NN)

The Nearest Neighbor (NN) methods are non-parametric, instance-based algorithms used for classification and regression. They classify data points based on the closest training examples in the feature space.

Formula: d(x, y) = √Σ(x_i – y_i)²

Working Principle of k-NN

  1. Compute distance between new sample and all training points.
  2. Select k nearest neighbors.
  3. Classification: Choose the majority class among neighbors.
  4. Regression: Take the average of neighbors’ values.

Example: To classify a fruit as ‘Apple’ or ‘Orange’ using color and weight, the algorithm computes distances to known fruits, selects k=3 nearest, and assigns the class that appears most frequently.

Advantages and Disadvantages of k-NN

  • Advantages: Simple, non-parametric, adaptable.
  • Disadvantages: High computation, storage needs, sensitive to noise and scaling issues.

Additional Concepts

  • Entropy in Decision Tree: Measures uncertainty or impurity in a dataset.
  • Ensemble Learning: Combines multiple models to improve accuracy and robustness.
  • Bagging: Trains multiple models on random data subsets and averages predictions.
  • Gaussian Mixture Model: Represents data as a combination of multiple Gaussian distributions.
  • PCA: Principal Component Analysis; reduces dimensionality by capturing maximum variance.
  • Evolutionary Operators: Crossover and mutation.
  • Genetic Algorithm: Optimization inspired by natural selection using selection, crossover, mutation.
  • Bayesian vs Markov Random Field: Bayesian Networks are directed; Markov Random Fields are undirected.
  • Forward Algorithm in HMM: Computes probability of an observation sequence given model parameters.
  • Policy in RL: Defines agent’s strategy for choosing actions in given states.

Markov Chain Monte Carlo (MCMC) Methods

MCMC methods are a class of algorithms used to sample from complex probability distributions when direct sampling is difficult or impossible. They combine Markov Chains and Monte Carlo Simulation to approximate posterior distributions of parameters in probabilistic models.

Key Concepts

  • Markov Chain: A sequence of random variables X₁, X₂, …, Xₙ where the probability of moving to the next state depends only on the current state:

P(X_{t+1} | X₁, X₂, …, X_t) = P(X_{t+1} | X_t)

Monte Carlo Simulation: Uses random sampling to approximate integrals or expectations.

Purpose of MCMC

Used in probabilistic models (especially Bayesian ones) to estimate the posterior distribution P(θ|D) when direct computation is intractable.

Popular Algorithms

  1. Metropolis-Hastings Algorithm:
    • Proposes a new sample x′ from a proposal distribution q(x′|x).
    • Accepts it with probability α = min(1, [P(x′)q(x|x′)] / [P(x)q(x′|x)]).
    • Ensures generated samples follow the target distribution P(x).
  2. Gibbs Sampling:
    • Special case of Metropolis-Hastings.
    • Samples each variable from its conditional distribution while keeping others fixed.
    • Commonly used in Bayesian Networks and Hidden Markov Models.

Role in Inference

MCMC methods approximate posterior distributions and perform inference by generating samples that represent the target distribution. They enable estimation of marginal probabilities, Bayesian parameter estimation, model prediction, and learning in graphical models.

Formula for marginal probability:

P(A) = ∫ P(A, B) dB