Lemma 5 should also require the condition $(\sqrt{n+1}\,\beta)^{1/c}>nB$. Since $\beta$ is typically exponential in $n$, in practice this isn't a problem for the intended application. However, this bound will not be satisfied if $n=1$ or if for example one tries to reconstruct a vector consisting of identical entries; in that case the problem reduces to the scalar case and there's no getting around the $M\in\Omega(\beta^2)$ uniqueness requirement.