# Polynomial Time and Sample Complexity for Non-Gaussian Component Analysis: Spectral Methods

arXiv: https://arxiv.org/abs/1704.01041 · HTML: https://mlsanity.com/paper/1704.01041/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Apr 2017.

## Built on by (most cited first, 9 of 9)

- [Lattice-Based Methods Surpass Sum-of-Squares in Clustering](https://mlsanity.com/paper/2112.03898/) (2021)
- [Optimal Spectral Recovery of a Planted Vector in a Subspace](https://mlsanity.com/paper/2105.15081/) (2021)
- [Non-Gaussian Component Analysis via Lattice Basis Reduction](https://mlsanity.com/paper/2112.09104/) (2021)
- [SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions](https://mlsanity.com/paper/2403.04744/) (2024)
- [Sum-of-squares lower bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2410.21426/) (2024)
- [Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models](https://mlsanity.com/paper/2206.04589/) (2022)
- [Learning from higher-order statistics, efficiently: hypothesis tests, random features, and neural networks](https://mlsanity.com/paper/2312.14922/) (2023)
- [Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time](https://mlsanity.com/paper/2311.01435/) (2023)
- [Beyond Second-Order Information: Paid Logistic Regression with Noisy Features](https://mlsanity.com/paper/2610.12919/) (2026)

## Abstract (arXiv)

The problem of Non-Gaussian Component Analysis (NGCA) is about finding a maximal low-dimensional subspace E in ℝn so that data points projected onto E follow a non-gaussian distribution. Although this is an appropriate model for some real world data analysis problems, there has been little progress on this problem over the last decade. In this paper, we attempt to address this state of affairs in two ways. First, we give a new characterization of standard gaussian distributions in high-dimensions, which lead to effective tests for non-gaussianness. Second, we propose a simple algorithm, Reweighted PCA, as a method for solving the NGCA problem. We prove that for a general unknown non-gaussian distribution, this algorithm recovers at least one direction in E, with sample and time complexity depending polynomially on the dimension of the ambient space. We conjecture that the algorithm actually recovers the entire E.