I am looking for references discussing the formal requirements for the dimension $m$ of the "measurement" mixing matrix in compressive sensing (as in ${\bf y} = M {\bf x}$ where ${\bf y} \in \mathbb{R}^ m$ and $ M \in \mathbb{R}^{ m \times n}$ with $m < n$. Here ${\bf x} \in \mathbb{R}^ n$ is the original sparse signal vector to be recovered from $\bf y$). Question: What is the "smallest" dimension $m$ to allow full recovery of $\bf x$, as related to the simple "sparsity measure" (i.e. 90% of entries are zero) of $\bf x$? Any references would be greatly helpful.
2
-
1$\begingroup$ The bound depends on what you mean by "full recovery". The restriction of $x\mapsto Mx$ to the set of $k$-sparse vectors is injective only if $m\geq 2k$, in which case one can theoretically recover $x$ from $Mx$, but the algorithm might be slow. Meanwhile, a computationally efficient algorithm like $\ell_1$ minimization requires $m=\Omega(k\log(n/k))$. Foucart and Rauhut's book is the go-to reference for these things. $\endgroup$– Dustin G. MixonCommented Nov 19, 2022 at 23:10
-
$\begingroup$ Thank you @Dustin, I will take a look at Foucart and Rauhut $\endgroup$– Zebra FishCommented Nov 20, 2022 at 0:56
Add a comment
|