Fourier PCA (or Blum beats glum)
September 11, 2013
Suppose you see points in n-space that are projections of uniform random points from a parallelepiped in a higher dimensional space. Can you recover the parallelepiped? This problem, known as Independent Component Analysis, comes up in several contexts. In linear algebraic terms, you see vectors x that satisfy x= As for an unknown n x m matrix A; the coordinates of the signal s are independent random variables and the goal is to recover A. We will present, in constant time, a polytime algorithm for this problem, assuming only that the distribution of x is not Gaussian (a necessary condition for a well-defined solution). The main new tool is a Fourier variant of Principal Component Analysis (PCA); this amounts to PCA after reweighting the distribution with a random Fourier weighting. During the talk, we will practice the modern pronunciation of Fourier and Hummus as much as possible.

This is joint work with Navin Goyal and Ying Xiao.