Linear embeddings of low-dimensional subsets of a Hilbert space to $\mathbb{R}^m$

Gilles Puy (1) , Mike E. Davies (2) , Rémi Gribonval (1)

1 PANAMA - Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio
2 Institute for Digital Communication Joint Research Institute for Signal & Image Processing School of Engineering and Electronics - University of Edinburgh

We consider the problem of embedding a low-dimensional set, M, from an infinite-dimensional Hilbert space to a finite-dimensional space. Defining appropriate random linear projections, we construct a linear map which has the restricted isometry property on the secant set of M, with high probability for a number of projections essentially proportional to the intrinsic dimension of M.

Mots clés: Box-counting dimension; Compressed Sensing; Restricted Isometry Property

Domaines: Traitement du signal et de l'image [eess.SP]

Gilles Puy, Mike E. Davies, Rémi Gribonval. Linear embeddings of low-dimensional subsets of a Hilbert space to $\mathbb{R}^m$. SPARS15 - Signal Processing with Adaptive Sparse Structured Representations, Jul 2015, Cambridge, United Kingdom. ⟨hal-01157992⟩