# Isometric sketching of any set via the Restricted Isometry Property

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2015.

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

- [Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications](https://mlsanity.com/paper/2311.05116/) (2023)
- [On Fast Johnson-Lindenstrauss Embeddings of Compact Submanifolds of ℝN with Boundary](https://mlsanity.com/paper/2110.04193/) (2021)
- [Gradient Descent Provably Solves Nonlinear Tomographic Reconstruction](https://mlsanity.com/paper/2310.03956/) (2023)
- [Leverage Score Sampling for Complete Mode Coverage in Generative Adversarial Networks](https://mlsanity.com/paper/2104.02373/) (2021)
- [Reconstruct Anything Model: a lightweight general model for computational imaging](https://mlsanity.com/paper/2503.08915/) (2025)
- [Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees](https://mlsanity.com/paper/2311.01806/) (2023)
- [Sparsifying Suprema of Gaussian Processes](https://mlsanity.com/paper/2411.14664/) (2024)

## Abstract (arXiv)

In this paper we show that for the purposes of dimensionality reduction certain class of structured random matrices behave similarly to random Gaussian matrices. This class includes several matrices for which matrix-vector multiply can be computed in log-linear time, providing efficient dimensionality reduction of general sets. In particular, we show that using such matrices any set from high dimensions can be embedded into lower dimensions with near optimal distortion. We obtain our results by connecting dimensionality reduction of any set to dimensionality reduction of sparse vectors via a chaining argument.