To understand the idea of sparse signal recovery described in Sparsity and Incoherence in Compressive Sampling, I decided to build a toy problem. Suppose the sparse signal that we want to reconstruct $x^0$ is $n=1000$ dimensional and only $S=9$ of its entries are nonzero. For simplicity, I pick the transform matrix $U$ to be a DFT matrix and I randomly sample $m$ values from $Ux^0$ (transform coefficients) to use them as our measurements $y$. In other words, $$y = U_{\Omega} x^0.$$

Based on the theorem given in the paper, signal recovery is possible with constrained $\ell_1$ norm minimization if the number of measurements $m$ satisfies the following condition: $$m \geq C \mu^2(U) S \log n$$ for a positive constant $C$. In my toy problem, I know that $\mu(U)=1$, $S=9$ and $n=1000$, but I do not know the constant $C$! I looked at the paper over and over again and I think I am missing something. Could you please explain to me how to determine the value of $C$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.