On the Theorem of Uniform Recovery of Random Sampling Matrices
Provides incremental theoretical improvements for sparse recovery guarantees in compressive sensing.
The paper improves theoretical guarantees for compressive sensing by deriving tighter constants for uniform recovery of random sampling matrices and a better bound on restricted isometry constants (δ_{2s} < 4/√41) for ℓ1-minimization.
We consider two theorems from the theory of compressive sensing. Mainly a theorem concerning uniform recovery of random sampling matrices, where the number of samples needed in order to recover an $s$-sparse signal from linear measurements (with high probability) is known to be $m\gtrsim s(\ln s)^3\ln N$. We present new and improved constants together with what we consider to be a more explicit proof. A proof that also allows for a slightly larger class of $m\times N$-matrices, by considering what we call \emph{low entropy}. We also present an improved condition on the so-called restricted isometry constants, $δ_s$, ensuring sparse recovery via $\ell^1$-minimization. We show that $δ_{2s}<4/\sqrt{41}$ is sufficient and that this can be improved further to almost allow for a sufficient condition of the type $δ_{2s}<2/3$.