Nonparametric Function Estimation using Overcomplete Dictionaries

Merlise A. Clyde and Robert L. Wolpert

Duke University Department of Statistical Science

May 2006

We consider the nonparametric regression problem of estimating an unknown function based on noisy data. One approach to this estimation problem is to represent the function in a series expansion using a linear combination of basis functions. Overcomplete dictionaries provide a larger, but redundant collection of generating elements than a basis, however, coefficients in the expansion are no longer unique. Despite the non-uniqueness, this has the potential to lead to sparser representations by using fewer non-zero coefficients. Compound Poisson random fields and their generalization to Levy random fields are ideally suited for construction of priors on functions using these overcomplete representations for the general nonparametric regression problem, and provide a natural limiting generalization of priors for the finite dimensional version of the regression problem. While expressions for posterior modes or posterior distributions of quantities of interest are not available in closed form, the prior construction using Levy random fields permits tractable posterior simulation via a reversible jump Markov chain Monte Carlo algorithm. Efficient computation is possible because updates based on adding/deleting or updating single dictionary elements bypass the need to invert large matrices. Furthermore, because dictionary elements are only computed as needed, memory requirements scale linearly with the sample size. In comparison with other methods, the Levy random field priors provide excellent performance in terms of both mean squared error and coverage for out-of-sample predictions.

Keywords: Gaussian Random Field; Infinitely Divisible; Kernel Regression; Levy random field; Nonparametric Regression; Relevance Vector Machine; Reversible Jump Markov chain Monte Carlo; Spatial-Temporal Models; Splines; Support Vector Machine; Wavelets

The manuscript is available in PostScript (2.6Mb) and PDF (562Kb) formats.

Cite as:

@InProceedings{Clyd:Wolp:2007,
      Author = "Merlise A. Clyde and Robert L. Wolpert",
       Title = "Estimation Using Overcomplete Dictionaries",
   BookTitle = "Bayesian Statistics 8",
      Editor = "Jos{\'e} M. Bernardo and M. J. Bayarri and
                James O. Berger and A. Phillip Dawid and David
                Heckerman and Adrian F. M. Smith and Mike West",
   Publisher = "Oxford University Press",
     Address = "Oxford, UK",
        ISBN = "978-0-19-921465-5",
       Pages = "91--114",
        Year = 2007,
}

This material is based upon work supported by the National Science Foundation under Grant Number DMS-0342172, DMS-0422400 and DMS-0406115. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.