Skip to Main content Skip to Navigation
Reports

Linear embeddings of low-dimensional subsets of a Hilbert space to 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
Inria Rennes – Bretagne Atlantique , IRISA-D5 - SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE
Abstract : We consider the problem of embedding a low-dimensional set, M, from an infinite-dimensional Hilbert space, H, to a finite-dimensional space. Defining appropriate random linear projections, we propose two constructions of linear maps that have the restricted isometry property (RIP) on the secant set of M with high probability. The first one is optimal in the sense that it only needs a number of projections essentially proportional to the intrinsic dimension of M to satisfy the RIP. The second one, which is based on a variable density sampling technique, is computationally more efficient, while potentially requiring more measurements.
Complete list of metadata

https://hal.inria.fr/hal-01116153
Contributor : Gilles Puy <>
Submitted on : Thursday, February 12, 2015 - 4:19:26 PM
Last modification on : Wednesday, January 16, 2019 - 11:40:15 AM

Identifiers

  • HAL Id : hal-01116153, version 1

Citation

Gilles Puy, Mike E. Davies, Rémi Gribonval. Linear embeddings of low-dimensional subsets of a Hilbert space to R$^m$. [Technical Report] INRIA - IRISA - PANAMA; Institute for Digital Communications (IDCom) - University of Edinburgh. 2015. ⟨hal-01116153v1⟩

Share

Metrics

Record views

203