Editing Independent component analysis (section)

== Binary ICA ==

A special variant of ICA is binary ICA in which both signal sources and monitors are in binary form and observations from monitors are disjunctive mixtures of binary independent sources. The problem was shown to have applications in many domains including [[medical diagnosis]], [[multi-cluster assignment]], [[network tomography]] and [[internet resource management]].

Let <math>{x_1, x_2, \ldots, x_m}</math> be the set of binary variables from <math>m</math> monitors and <math>{y_1, y_2, \ldots, y_n}</math> be the set of binary variables from <math>n</math> sources. Source-monitor connections are represented by the (unknown) mixing matrix <math display="inline">\boldsymbol{G}</math>, where <math>g_{ij} = 1</math> indicates that signal from the ''i''-th source can be observed by the ''j''-th monitor. The system works as follows: at any time, if a source <math>i</math> is active (<math>y_i=1</math>) and it is connected to the monitor <math>j</math> (<math>g_{ij}=1</math>) then the monitor <math>j</math> will observe some activity (<math>x_j=1</math>). Formally we have:

:<math>
x_i = \bigvee_{j=1}^n (g_{ij}\wedge y_j), i = 1, 2, \ldots, m,
</math>

where <math>\wedge</math> is Boolean AND and <math>\vee</math> is Boolean OR. Noise is not explicitly modelled, rather, can be treated as independent sources.

The above problem can be heuristically solved<ref name="Hyvärinen">Johan Himbergand Aapo Hyvärinen, ''[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.8895 Independent Component Analysis For Binary Data: An Experimental Study]'', Proc. Int. Workshop on Independent Component Analysis and Blind Signal Separation (ICA2001), San Diego, California, 2001.</ref> by assuming variables are continuous and running [[FastICA]] on binary observation data to get the mixing matrix <math display="inline">\boldsymbol{G}</math> (real values), then apply [[round number]] techniques on <math display="inline">\boldsymbol{G}</math> to obtain the binary values. This approach has been shown to produce a highly inaccurate result.{{citation needed|date=October 2012}}

Another method is to use [[dynamic programming]]: recursively breaking the observation matrix <math display="inline">\boldsymbol{X}</math> into its sub-matrices and run the inference algorithm on these sub-matrices. The key observation which leads to this algorithm is the sub-matrix <math display="inline">\boldsymbol{X}^0</math> of <math display="inline">\boldsymbol{X}</math> where <math display="inline">x_{ij} = 0, \forall j</math> corresponds to the unbiased observation matrix of hidden components that do not have connection to the <math>i</math>-th monitor. Experimental results from<ref name="Huyna">Huy Nguyen and Rong Zheng, ''[https://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5753957 Binary Independent Component Analysis With or Mixtures]'', IEEE Transactions on Signal Processing, Vol. 59, Issue 7. (July 2011), pp. 3168&ndash;3181.</ref> show that this approach is accurate under moderate noise levels.

The Generalized Binary ICA framework<ref name="Generalized Binary ICA">{{cite book|last1=Painsky|first1=Amichai|last2=Rosset|first2=Saharon|last3=Feder|first3=Meir|title=2014 IEEE International Symposium on Information Theory |chapter=Generalized binary independent component analysis |pages=1326–1330|doi=10.1109/ISIT.2014.6875048|year=2014|isbn=978-1-4799-5186-4|s2cid=18579555}}</ref> introduces a broader problem formulation which does not necessitate any knowledge on the generative model. In other words, this method attempts to decompose a source into its independent components (as much as possible, and without losing any information) with no prior assumption on the way it was generated. Although this problem appears quite complex, it can be accurately solved with a [[branch and bound]] search tree algorithm or tightly upper bounded with a single multiplication of a matrix with a vector.