  In this paper, we investigate the optimal statistical performance and the
impact of computational constraints for independent component analysis (ICA).
Our goal is twofold. On the one hand, we characterize the precise role of
dimensionality on sample complexity and statistical accuracy, and how
computational consideration may affect them. In particular, we show that the
optimal sample complexity is linear in dimensionality, and interestingly, the
commonly used sample kurtosis-based approaches are necessarily suboptimal.
However, the optimal sample complexity becomes quadratic, up to a logarithmic
factor, in the dimension if we restrict ourselves to estimates that can be
computed with low-degree polynomial algorithms. On the other hand, we develop
computationally tractable estimates that attain both the optimal sample
complexity and minimax optimal rates of convergence. We study the asymptotic
properties of the proposed estimates and establish their asymptotic normality
that can be readily used for statistical inferences. Our method is fairly easy
to implement and numerical experiments are presented to further demonstrate its
practical merits.
