# Recovering Imbalanced Clusters via Gradient-Based Projection Pursuit

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 41 references that are in the map.
- First posted on arXiv 4 Feb 2025.

## Builds on (most cited first, 12 of 12)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [A note on the sample complexity of the Er-SpUD algorithm by Spielman, Wang and Wright for exact recovery of sparsely used dictionaries](https://mlsanity.com/paper/1601.02049/) (2016)
- [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)
- [Finding a sparse vector in a subspace: Linear sparsity using alternating directions](https://mlsanity.com/paper/1412.4659/) (2014)
- [Subgradient Descent Learns Orthogonal Dictionaries](https://mlsanity.com/paper/1810.10702/) (2018)
- [Clustering a Mixture of Gaussians with Unknown Covariance](https://mlsanity.com/paper/2110.01602/) (2021)
- [Sum-of-squares lower bounds for planted clique](https://mlsanity.com/paper/1503.06447/) (2015)
- [Statistical-Computational Trade-offs in Tensor PCA and Related Problems via Communication Complexity](https://mlsanity.com/paper/2204.07526/) (2022)
- [Sum-of-squares lower bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2410.21426/) (2024)
- [Multivariate outlier detection based on a robust Mahalanobis distance with shrinkage estimators](https://mlsanity.com/paper/1904.02596/) (2019)

## Abstract (arXiv)

Projection Pursuit is a classic exploratory technique for finding interesting projections of a dataset. We propose a method for recovering projections containing either Imbalanced Clusters or a Bernoulli-Rademacher distribution using a gradient-based technique to optimize the projection index. As sample complexity is a major limiting factor in Projection Pursuit, we analyze our algorithm's sample complexity within a Planted Vector setting where we can observe that Imbalanced Clusters can be recovered more easily than balanced ones. Additionally, we give a generalized result that works for a variety of data distributions and projection indices. We compare these results to computational lower bounds in the Low-Degree-Polynomial Framework. Finally, we experimentally evaluate our method's applicability to real-world data using FashionMNIST and the Human Activity Recognition Dataset, where our algorithm outperforms others when only a few samples are available.