Linearly Embedding Sparse Vectors from \(\ell _2\) to \(\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 \(\ell _2\) to \(\ell _1\) on s-sparse vectors. Similarly to the standard ( \(\ell _2\) to \(\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 \(\ell _2^n(\mathbb {C})\) to \(\ell _4^{cn^2}(\mathbb {C})\) is presented. Finally, the extension of the problem from sparse vectors to low-rank matrices is raised as an open question.