# DiffRed: Dimensionality Reduction guided by stable rank

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 55 references that are in the map.
- First posted on arXiv 9 Mar 2024.

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

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [Automated Hate Speech Detection and the Problem of Offensive Language](https://mlsanity.com/paper/1703.04009/) (2017)
- [Learning-Based Low-Rank Approximations](https://mlsanity.com/paper/1910.13984/) (2019)
- [Optimal approximate matrix product in terms of stable rank](https://mlsanity.com/paper/1507.02268/) (2015)
- [Fast Randomized PCA for Sparse Data](https://mlsanity.com/paper/1810.06825/) (2018)
- [The Fast Johnson-Lindenstrauss Transform is Even Faster](https://mlsanity.com/paper/2204.01800/) (2022)

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

- [Subspace-Boosted Model Merging](https://mlsanity.com/paper/2506.16506/) (2025)
- ["Normalized Stress" is Not Normalized: How to Interpret Stress Correctly](https://mlsanity.com/paper/2408.07724/) (2024)
- [How Scale Breaks "Normalized Stress" and KL Divergence: Rethinking Quality Metrics](https://mlsanity.com/paper/2510.08660/) (2025)

## Abstract (arXiv)

In this work, we propose a novel dimensionality reduction technique, DiffRed, which first projects the data matrix, A, along first k1 principal components and the residual matrix A* (left after subtracting its k1-rank approximation) along k2 Gaussian random vectors. We evaluate M1, the distortion of mean-squared pair-wise distance, and Stress, the normalized value of RMS of distortion of the pairwise distances. We rigorously prove that DiffRed achieves a general upper bound of Oleft(√frac1-pk2right) on Stress and Oleft(frac(1-p)√k2*ρ(A*)right) on M1 where p is the fraction of variance explained by the first k1 principal components and ρ(A*) is the stable rank of A*. These bounds are tighter than the currently known results for Random maps. Our extensive experiments on a variety of real-world datasets demonstrate that DiffRed achieves near zero M1 and much lower values of Stress as compared to the well-known dimensionality reduction techniques. In particular, DiffRed can map a 6 million dimensional dataset to 10 dimensions with 54% lower Stress than PCA.