PhD Dissertation: Generalized Independent Components Analysis Over Finite Alphabets

  • 2018-09-13 16:22:19
  • Amichai Painsky
  • 3


Independent component analysis (ICA) is a statistical method for transformingan observable multi-dimensional random vector into components that are asstatistically independent as possible from each other. Usually the ICAframework assumes a model according to which the observations are generated(such as a linear transformation with additive noise). ICA over finite fieldsis a special case of ICA in which both the observations and the independentcomponents are over a finite alphabet. In this thesis we consider a formulationof the finite-field case in which an observation vector is decomposed to itsindependent components (as much as possible) with no prior assumption on theway it was generated. This generalization is also known as Barlow's minimalredundancy representation and is considered an open problem. We propose severaltheorems and show that this hard problem can be accurately solved with a branchand bound search tree algorithm, or tightly approximated with a series oflinear problems. Moreover, we show that there exists a simple transformation(namely, order permutation) which provides a greedy yet very effectiveapproximation of the optimal solution. We further show that while not everyrandom vector can be efficiently decomposed into independent components, thevast majority of vectors do decompose very well (that is, within a smallconstant cost), as the dimension increases. In addition, we show that we maypractically achieve this favorable constant cost with a complexity that isasymptotically linear in the alphabet size. Our contribution provides the firstefficient set of solutions to Barlow's problem with theoretical andcomputational guarantees. Finally, we demonstrate our suggested framework inmultiple source coding applications.


Introduction (beta)



Conclusion (beta)