2023/10/28 by Foucart, Simon · 1 citation
#FOS: Mathematics #Functional Analysis (math.FA) #Numerical Analysis (math.NA)
paper · doi:10.48550/arxiv.2310.18565
This note is concerned with deterministic constructions of m × N matrices satisfying a restricted isometry property from ℓ2 to ℓ1 on s-sparse vectors. Similarly to the standard (ℓ2 to ℓ2) restricted isometry property, such constructions can be found in the regime m \asymp s2, 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 s4. 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 ℓ2n(ℂ) to ℓ4cn2(ℂ) is presented. Finally, the extension of the problem from sparse vectors to low-rank matrices is raised as an open question.