Comment: The relevant topic to your question is Gelfand widths. These are discussed in seminar notes of Foucart. Small width implies successful $\ell_1$-recovery of $s$-sparse vectors for $$s\sim \left(\frac{1}{2 d^m(B^{N}_{1},\ell_p^N)} \right)^{\frac{p}{p-1}}.$$
Josiah Park
- 3.2k
- 13
- 28