A key result in compressive sensing states that, with high probability on the random draw of an $\ m × N$ Gaussian or Bernoulli matrix $\ A$, all $\ s$-sparse vectors $\ x$ can be reconstructed from $\ y = Ax$ using a variety of algorithms provided
$\ m ≥ Cs\ln(N/s)$,
where $\ C > 0$ is a universal constant (independent of $\ s, m,$ and $\ N$). This bound is in fact optimal.
In practical terms, how does one interpret/find $\ C$?
The constant C is usually left unspecified as it can be very hard to calculate. It is independent of the signal dimension, and results in Compressed Sensing are generally only concerned with big-O results, so it falls out when we say something like $m = \mathcal{O}(s \ln{(N/s)})$. The important part in this statement is the strong dependence on the sparsity level, and that the signal dimension $N$ only logarithmically affects the number of measurements.
To give an example of where such a constant would come from: Let $V_d$ be the volume of the unit $\ell_2$ ball in $\mathbb{R}^d$. Some simple cases are that $V_2 = \pi r^2$ and $V_3 = \frac{4}{3} \pi r^3$. Note that both of these results are of the form $V_d = C r^d$, and this pattern generalizes for finite $d$. In CS, it is $r^d$ that we are interested in, as it captures the dependence on the signal dimension.
So $C$ will vary depending on the algorithm as different inequalities may be used in the proofs. I don't know of any publications that specifically calculate C.
C depends , among other things, on the reconstruction algorithm.
