  Independent component analysis (ICA) is the problem of efficiently recovering
a matrix $A \in \mathbb{R}^{n\times n}$ from i.i.d. observations of $X=AS$
where $S \in \mathbb{R}^n$ is a random vector with mutually independent
coordinates. This problem has been intensively studied, but all existing
efficient algorithms with provable guarantees require that the coordinates
$S_i$ have finite fourth moments. We consider the heavy-tailed ICA problem
where we do not make this assumption, about the second moment. This problem
also has received considerable attention in the applied literature. In the
present work, we first give a provably efficient algorithm that works under the
assumption that for constant $\gamma > 0$, each $S_i$ has finite
$(1+\gamma)$-moment, thus substantially weakening the moment requirement
condition for the ICA problem to be solvable. We then give an algorithm that
works under the assumption that matrix $A$ has orthogonal columns but requires
no moment assumptions. Our techniques draw ideas from convex geometry and
exploit standard properties of the multivariate spherical Gaussian distribution
in a novel way.
