# Restricted Isometry Property under High Correlations

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Apr 2019.

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

- [Preconditioning for Scalable Gaussian Process Hyperparameter Optimization](https://mlsanity.com/paper/2107.00243/) (2021)
- [Attentive Walk-Aggregating Graph Neural Networks](https://mlsanity.com/paper/2110.02667/) (2021)
- [Non-Convex Compressed Sensing with Training Data](https://mlsanity.com/paper/2101.08310/) (2021)
- [Learning Trees of ℓ0-Minimization Problems](https://mlsanity.com/paper/2302.02548/) (2023)
- [Resilience of Rademacher chaos of low degree](https://mlsanity.com/paper/2402.10504/) (2024)

## Abstract (arXiv)

Matrices satisfying the Restricted Isometry Property (RIP) play an important role in the areas of compressed sensing and statistical learning. RIP matrices with optimal parameters are mainly obtained via probabilistic arguments, as explicit constructions seem hard. It is therefore interesting to ask whether a fixed matrix can be incorporated into a construction of restricted isometries. In this paper, we construct a new broad ensemble of random matrices with dependent entries that satisfy the restricted isometry property. Our construction starts with a fixed (deterministic) matrix X satisfying some simple stable rank condition, and we show that the matrix XR, where R is a random matrix drawn from various popular probabilistic models (including, subgaussian, sparse, low-randomness, satisfying convex concentration property), satisfies the RIP with high probability. These theorems have various applications in signal recovery, random matrix theory, dimensionality reduction, etc. Additionally, motivated by an application for understanding the effectiveness of word vector embeddings popular in natural language processing and machine learning applications, we investigate the RIP of the matrix XR(l) where R(l) is formed by taking all possible (disregarding order) l-way entrywise products of the columns of a random matrix R.