Recipes for stable linear embeddings from Hilbert spaces to R^m

Gilles Puy, Michael Davies, Remi Gribonval

Research output: Contribution to journalArticlepeer-review


We consider the problem of constructing a linear map from a Hilbert space H (possibly infinite dimensional) to Rm that satisfies a restricted isometry property (RIP) on an arbitrary signal model, i.e., a subset of H. We present a generic framework that handles a large class of low-dimensional subsets but also unstructured and structured linear maps. We provide a simple recipe to prove that a random linear map satisfies a general RIP with high probability. We also describe a generic technique to construct linear maps that satisfy the RIP. Finally, we detail how to use our results in several examples, which allow us to recover and extend many known compressive sampling results.
Original languageEnglish
Pages (from-to)2171 - 2187
JournalIEEE Transactions on Information Theory
Issue number4
Early online date6 Feb 2017
Publication statusPublished - Apr 2017


  • compressed sensing
  • restricted isometry property
  • box-counting dimension


Dive into the research topics of 'Recipes for stable linear embeddings from Hilbert spaces to R^m'. Together they form a unique fingerprint.

Cite this