Union bound over supports for the restricted isometry property

ProofAdvanced⏱ 1 hourHigh-Dim Statisticsripunion boundsparsitysample complexity

Theory: Sparse Recovery, Compressed Sensing and the Lasso →

Problem

Show that a Gaussian matrix $X\in\R^{n\times p}$ satisfies the $(s,\delta)$ -RIP with probability at least $1-2e^{-c\delta^2n}$ provided $n \gtrsim \delta^{-2}s\log(p/s)$ , by combining a per-support covariance bound with a union bound over the $\binom ps$ supports. Perform the exponent count explicitly.

Write a complete argument. Every inequality you use should be one you could state precisely.

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems

Problem	Field	Type	Difficulty	Time
When is the union bound tight?	Probability	Proof	Foundation	15 min
Generalisation for a finite class	Learning Theory	Proof	Beginner	30 min
Two different curses of dimensionality	Classical ML	Numerical	Beginner	15 min
Derive the soft-thresholding operator	High-Dim Statistics	Proof	Intermediate	30 min
Sample complexity of covariance estimation	High-Dim Statistics	Numerical	Intermediate	30 min