The road to deterministic matrices with the restricted isometry property

Understand

The restricted isometry property (RIP) is a well-known matrix condition that provides state-of-the-art reconstruction guarantees for compressed sensing.

• While random matrices are known to satisfy this property with high probability, deterministic constructions have found less success.
• In this paper, we consider various techniques for demonstrating RIP deterministically, some popular and some novel, and we evaluate their performance.
• In evaluating some techniques, we apply random matrix theory and inadvertently find a simple alternative proof that certain random matrices are RIP.