Generalized Independent Component Analysis over Finite Alphabets

Independent component analysis (ICA) is a statistical method for transforming an observable multidimensional random vector into components that are as statistically independent as possible. Usually the ICA framework assumes a model according to which the observations are generated (such as a linear transformation with additive noise). ICA over finite fields is a special case where both the observations and the independent components are over finite alphabet. In this work we consider a generalization of this framework where the observation vector is decomposed to its independent (as much as possible) components with no prior assumption on the way it was generated. This generalization is also known as Barlow's minimal redundancy representation problem [Barlow, '89] or factorial coding and is considered an open problem. We propose several theorems and show that this hard problem can be accurately solved by a branch and bound search tree algorithm, or tightly approximated with a series of linear problems. Moreover, we show that there exists a simple transformation (namely, order permutation) which provides a greedy yet very effective approximation of the optimal solution. We further show that while not every random vector can be efficiently decomposed into independent components, the vast majority of vectors do decompose very well (that is, with a small constant cost), as the dimension increases. The minimal redundancy representation (factorial coding) has many applications, e.g., in neural networks and deep learning. In this work we show that this formulation further applies to large alphabet lossless source coding.

Joint work with Amichai Painsky and Saharon Rosset.