Sparse Recovery with Brownian Sensing

A. Carpentier 1 O. A. Maillard 1 R. Munos 1
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
Abstract : We consider the problem of recovering the parameter α of a sparse function f (i.e. the number of non-zero entries of α is small compared to the number K of features) given noisy evaluations of f at a set of well-chosen sampling points. We introduce an additional randomization process, called Brownian sensing, based on the computation of stochastic integrals, which produces a Gaussian sensing matrix, for which good recovery properties are proven, independently on the number of sampling points N, even when the features are arbitrarily non-orthogonal. Under the assumption that f is Hölder continuous with exponent at least 1/2 we provide an estimate of the parameter with quadratic error O(||η || / N ), where η is the observation noise. The method uses a set of sampling points uniformly distributed along a one-dimensional curve selected according to the features. We report numerical experiments illustrating our method.
Type de document :
Communication dans un congrès
Advances in Neural Information Processing Systems, 2011, Granada, Spain. 2011
Liste complète des métadonnées
Contributeur : Philippe Preux <>
Soumis le : vendredi 7 février 2014 - 08:23:58
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13


  • HAL Id : hal-00943122, version 1



A. Carpentier, O. A. Maillard, R. Munos. Sparse Recovery with Brownian Sensing. Advances in Neural Information Processing Systems, 2011, Granada, Spain. 2011. 〈hal-00943122〉



Consultations de la notice