An Improved Lower Bound for Sparse Reconstruction from Subsampled Hadamard Matrices
summary
Claim: subsampled Hadamard matrices require about k log k log n rows to satisfy the restricted isometry property for k‑sparse recovery. Proof uses indicator vectors supported on subspaces of dimension log k, shows each such vector maps to zero with probability ≈ e^{−q/k}, and applies inclusion–exclusion / second‑moment arguments to force q ≥ Θ(k log n log k). Result separates known upper bounds (k log^2 k log n etc.) from the new lower bound.
AI-written summary · about