Linearly Embedding Sparse Vectors from ${\mathrm{\ell }}_2$ to ${\mathrm{\ell }}_1$ via Deterministic Dimension-Reducing Maps

This note is concerned with deterministic constructions of $m\times N$ matrices satisfying a restricted isometry property from ${\mathrm{\ell }}_2$ to ${\mathrm{\ell }}_1$ on $s$-sparse vectors. Similarly to the standard (${\mathrm{\ell }}_2$ to ${\mathrm{\ell }}_2$) restricted isometry property, such constructions can be found in the regime $m\asymp s^2$, at least in theory. With effectiveness of implementation in mind, two simple constructions are presented in the less pleasing but still relevant regime $m\asymp s^4$. The first one, executing a Las Vegas strategy, is quasideterministic and applies in the real setting. The second one, exploiting Golomb rulers, is explicit and applies to the complex setting. As a stepping stone, an explicit isometric embedding from ${\mathrm{\ell }}_2^n(\mathbb{C})$ to ${\mathrm{\ell }}_4^{c{n}^2}(\mathbb{C})$ is presented. Finally, the extension of the problem from sparse vectors to low-rank matrices is raised as an open question.