Generalized Independent Component Analysis over Finite Alphabets

Tuesday, March 22, 2016 - 4:00pm

Event Calendar Category

LIDS Seminar Series

Speaker Name

Meir Feder

Affiliation

Tel-Aviv University

Building and Room Number

32-155

Abstract

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.

Biography

Professor Meir Federreceived the Sc.D. degree from the Massachusetts Institute of Technology (MIT) and Woods Hole Oceanographic Institution (WHOI) in 1987. In 1990 he joined the school of electrical engineering, Tel-Aviv University (TAU), where he is now a Professor and the holder of the Information Theory chair. From 2010-2013 he was the head of the EE school at TAU.

While serving in the Israeli defense Forces, he was awarded the 1978 “creative mind” award. He received several paper awards including the 1993 best paper award of the Information Theory Society. He was the recipient of the 1994 prize of Tel-Aviv University for excellent young scientists, the 1994 award of the Electronic Industry in Israel (awarded by the president of Israel), and the 1995 research prize in applied electronics awarded by Ben-Gurion University. He is a Fellow of the IEEE for his contribution to universal data prediction and universal compression.

In parallel to his academic career he is closely involved with the high-tech industry. In 1998 he co-founded Peach Networks, acquired in 2000 by Microsoft. He then co-founded Bandwiz, to provide massive content delivery systems using rateless codes. He was on the founding team of Final Inc., a high frequency trading firm. In 2004 he co-founded Amimon, a provider of wireless high-definition A/V connectivity solutions for the consumer, professional and medical markets.

Reception information

Reception to follow.