# Universality laws for randomized dimension reduction, with applications

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Nov 2015.

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

- [Universality of empirical risk minimization](https://mlsanity.com/paper/2202.08832/) (2022)
- [Label-Imbalanced and Group-Sensitive Classification under Overparameterization](https://mlsanity.com/paper/2103.01550/) (2021)
- [Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting](https://mlsanity.com/paper/2106.09276/) (2021)
- [Precise Asymptotic Analysis of Deep Random Feature Models](https://mlsanity.com/paper/2302.06210/) (2023)
- [On the Inherent Regularization Effects of Noise Injection During Training](https://mlsanity.com/paper/2102.07379/) (2021)
- [Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression](https://mlsanity.com/paper/2112.04470/) (2021)
- [Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems](https://mlsanity.com/paper/2405.05818/) (2024)
- [Universality of max-margin classifiers](https://mlsanity.com/paper/2310.00176/) (2023)
- [Beyond Independent Measurements: General Compressed Sensing with GNN Application](https://mlsanity.com/paper/2111.00327/) (2021)
- [Random Features Model with General Convex Regularization: A Fine Grained Analysis with Precise Asymptotic Learning Curves](https://mlsanity.com/paper/2204.02678/) (2022)
- [Sample Efficient Subspace-based Representations for Nonlinear Meta-Learning](https://mlsanity.com/paper/2102.07206/) (2021)
- [Lasso Universality Under Linearly Dependent Covariates in the Sparse Regime](https://mlsanity.com/paper/2608.08390/) (2026)
- [Optimal Implicit Bias in Linear Regression](https://mlsanity.com/paper/2506.17187/) (2025)
- [RAPTOR: Ridge-Adaptive Logistic Probes](https://mlsanity.com/paper/2602.00158/) (2026)
- [Characterization of Gaussian Universality Breakdown in High-Dimensional Empirical Risk Minimization](https://mlsanity.com/paper/2604.03146/) (2026)
- [The sharp SAT/UNSAT phase transition in random ellipsoid fitting](https://mlsanity.com/paper/2608.10184/) (2026)
- [Phase Transitions in Recovery of Structured Signals from Corrupted Measurements](https://mlsanity.com/paper/2101.00599/) (2021)
- [Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees](https://mlsanity.com/paper/2311.01806/) (2023)
- [One-Bit Quantization for Random Features Models](https://mlsanity.com/paper/2510.16250/) (2025)
- [Asymptotic Behavior of Multi--Task Learning: Implicit Regularization and Double Descent Effects](https://mlsanity.com/paper/2603.05060/) (2026)
- [Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tails](https://mlsanity.com/paper/2609.03504/) (2026)

## Abstract (arXiv)

Dimension reduction is the process of embedding high-dimensional data into a lower dimensional space to facilitate its analysis. In the Euclidean setting, one fundamental technique for dimension reduction is to apply a random linear map to the data. This dimension reduction procedure succeeds when it preserves certain geometric features of the set. The question is how large the embedding dimension must be to ensure that randomized dimension reduction succeeds with high probability. This paper studies a natural family of randomized dimension reduction maps and a large class of data sets. It proves that there is a phase transition in the success probability of the dimension reduction map as the embedding dimension increases. For a given data set, the location of the phase transition is the same for all maps in this family. Furthermore, each map has the same stability properties, as quantified through the restricted minimum singular value. These results can be viewed as new universality laws in high-dimensional stochastic geometry. Universality laws for randomized dimension reduction have many applications in applied mathematics, signal processing, and statistics. They yield design principles for numerical linear algebra algorithms, for compressed sensing measurement ensembles, and for random linear codes. Furthermore, these results have implications for the performance of statistical estimation methods under a large class of random experimental designs.