  We present a polynomial-time algorithm for robustly learning an unknown
affine transformation of the standard hypercube from samples, an important and
well-studied setting for independent component analysis (ICA). Specifically,
given an $\epsilon$-corrupted sample from a distribution $D$ obtained by
applying an unknown affine transformation $x \rightarrow Ax+s$ to the uniform
distribution on a $d$-dimensional hypercube $[-1,1]^d$, our algorithm
constructs $\hat{A}, \hat{s}$ such that the total variation distance of the
distribution $\hat{D}$ from $D$ is $O(\epsilon)$ using poly$(d)$ time and
samples. Total variation distance is the information-theoretically strongest
possible notion of distance in our setting and our recovery guarantees in this
distance are optimal up to the absolute constant factor multiplying $\epsilon$.
In particular, if the columns of $A$ are normalized to be unit length, our
total variation distance guarantee implies a bound on the sum of the $\ell_2$
distances between the column vectors of $A$ and $A'$, $\sum_{i =1}^d
\|a_i-\hat{a}_i\|_2 = O(\epsilon)$. In contrast, the strongest known prior
results only yield a $\epsilon^{O(1)}$ (relative) bound on the distance between
individual $a_i$'s and their estimates and translate into an $O(d\epsilon)$
bound on the total variation distance. Our key innovation is a new approach to
ICA (even to outlier-free ICA) that circumvents the difficulties in the
classical method of moments and instead relies on a new geometric certificate
of correctness of an affine transformation. Our algorithm is based on a new
method that iteratively improves an estimate of the unknown affine
transformation whenever the requirements of the certificate are not met.
