Timezone: »

 
Poster
Sparse Recovery with Brownian Sensing
Alexandra Carpentier · Odalric-Ambrym Maillard · Remi Munos

Tue Dec 13 08:45 AM -- 02:59 PM (PST) @
in Poster Session »

We consider the problem of recovering the parameter alpha in R^K of a sparse function f, i.e. the number of non-zero entries of alpha 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 randomisation 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 a of the parameter such that ||\alpha - a||2 = O(||eta||2\sqrt{N}), where eta 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.

[ PDF] 

Author Information

Alexandra Carpentier (StatsLab Cambridge)
Odalric-Ambrym Maillard (INRIA)
Remi Munos (Google DeepMind)

More from the Same Authors