Binary Independent Component Analysis: Theory, Bounds And Algorithms | ||

Amichai Painsky, Tel Aviv UniversitySaharon Rosset, Tel Aviv University Meir Feder, Tel Aviv University |

**Abstract:**

Independent Component Analysis (ICA) is a statistical method for transforming an observable multi-dimensional random vector into components that are as statistically independent as possible from each other. The binary ICA (BICA) is a special case of ICA in which both the observations and the independent components are over a binary alphabet. The BICA problem has received a significant amount of attention in the past decade, mostly in the form of algorithmic approaches and heuristic solutions. However, BICA still suffers from a substantial lack of theoretical bounds and efficiency guarantees. In this work we address these concerns, as we introduce novel lower bounds and theoretical properties for the BICA problem, both under linear and non-linear transformations. In addition, we present simple algorithms which apply our methodology and achieve favorable merits, both in terms of their accuracy, and their practically optimal computational complexity.