Alexandra Carpentier, Odalric-Ambrym Maillard, Rémi Munos.
In Proceedings of the 24th conference on advances in Neural Information Processing Systems, NIPS ’11, 2011.
[Download]
Abstract: |
We consider the problem of recovering the parameter α ∈ R^K 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 such that ||α − â||_2 = O( ||η||_2/ sqrt(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. |
You can dowload the paper from the NIPS webiste (here) or from the HAL online open depository* (here).
Bibtex: |
@incollection{CarpentierMM11, title = {Sparse Recovery with Brownian Sensing}, author = {Alexandra Carpentier and Odalric-ambrym Maillard and R\'{e}mi Munos}, booktitle = {Advances in Neural Information Processing Systems 24}, editor = {J. Shawe-Taylor and R.S. Zemel and P.L. Bartlett and F. Pereira and K.Q. Weinberger}, pages = {1782–1790}, year = {2011}, publisher = {Curran Associates, Inc.} } |