# Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 38 references that are in the map.
- First posted on arXiv 23 Feb 2023.

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

- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Efficient Algorithms for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [List-Decodable Linear Regression](https://mlsanity.com/paper/1905.05679/) (2019)
- [Robust Linear Regression: Optimal Rates in Polynomial Time](https://mlsanity.com/paper/2007.01394/) (2020)
- [List Decodable Learning via Sum of Squares](https://mlsanity.com/paper/1905.04660/) (2019)
- [Settling the Robust Learnability of Mixtures of Gaussians](https://mlsanity.com/paper/2011.03622/) (2020)
- [Faster Algorithms for High-Dimensional Robust Covariance Estimation](https://mlsanity.com/paper/1906.04661/) (2019)
- [Outlier-robust moment-estimation via sum-of-squares](https://mlsanity.com/paper/1711.11581/) (2017)
- [Better Agnostic Clustering Via Relaxed Tensor Norms](https://mlsanity.com/paper/1711.07465/) (2017)
- [Smoothed Analysis of Tensor Decompositions](https://mlsanity.com/paper/1311.3651/) (2013)
- [Fourier PCA and Robust Tensor Decomposition](https://mlsanity.com/paper/1306.5825/) (2013)
- [List-Decodable Covariance Estimation](https://mlsanity.com/paper/2206.10942/) (2022)
- [List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time](https://mlsanity.com/paper/2002.05139/) (2020)

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

- [Distribution Learnability and Robustness](https://mlsanity.com/paper/2406.17814/) (2024)
- [Smoothed Analysis of Learning from Positive Samples](https://mlsanity.com/paper/2504.10428/) (2025)
- [Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time](https://mlsanity.com/paper/2311.01435/) (2023)
- [On the Learnability of Distribution Classes with Adaptive Adversaries](https://mlsanity.com/paper/2509.05137/) (2025)

## Abstract (arXiv)

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 ε-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 hatA, hats such that the total variation distance of the distribution hatD from D is O(ε) 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 ε. 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 ℓ2 distances between the column vectors of A and A', sumi =1d |ai-hatai|2 = O(ε). In contrast, the strongest known prior results only yield a εO(1) (relative) bound on the distance between individual ai's and their estimates and translate into an O(dε) 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.