# Overcomplete Independent Component Analysis via SDP

arXiv: https://arxiv.org/abs/1901.08334 · HTML: https://mlsanity.com/paper/1901.08334/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jan 2019.

## Built on by (most cited first, 9 of 9)

- [Stop Probing, Start Coding: Why Linear Probes and Sparse Autoencoders Fail at Compositional Generalisation](https://mlsanity.com/paper/2603.28744/) (2026)
- [Near-optimal fitting of ellipsoids to random points](https://mlsanity.com/paper/2208.09493/) (2022)
- [Distributional Equivalence in Linear Non-Gaussian Latent-Variable Cyclic Causal Models: Characterization and Learning](https://mlsanity.com/paper/2603.04780/) (2026)
- [ICA Lens: Interpreting Language Models Without Training Another Dictionary](https://mlsanity.com/paper/2606.11722/) (2026)
- [A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points](https://mlsanity.com/paper/2212.11221/) (2022)
- [Second-order Approximation of Minimum Discrimination Information in Independent Component Analysis](https://mlsanity.com/paper/2111.15060/) (2021)
- [Fitting an ellipsoid to a quadratic number of random points](https://mlsanity.com/paper/2307.01181/) (2023)
- [The sharp SAT/UNSAT phase transition in random ellipsoid fitting](https://mlsanity.com/paper/2608.10184/) (2026)
- [Boosting Independent Component Analysis](https://mlsanity.com/paper/2112.06920/) (2021)

## Abstract (arXiv)

We present a novel algorithm for overcomplete independent components analysis (ICA), where the number of latent sources k exceeds the dimension p of observed variables. Previous algorithms either suffer from high computational complexity or make strong assumptions about the form of the mixing matrix. Our algorithm does not make any sparsity assumption yet enjoys favorable computational and theoretical properties. Our algorithm consists of two main steps: (a) estimation of the Hessians of the cumulant generating function (as opposed to the fourth and higher order cumulants used by most algorithms) and (b) a novel semi-definite programming (SDP) relaxation for recovering a mixing component. We show that this relaxation can be efficiently solved with a projected accelerated gradient descent method, which makes the whole algorithm computationally practical. Moreover, we conjecture that the proposed program recovers a mixing component at the rate k < p^2/4 and prove that a mixing component can be recovered with high probability when k < (2 - epsilon) p log p when the original components are sampled uniformly at random on the hyper sphere. Experiments are provided on synthetic data and the CIFAR-10 dataset of real images.