Signal estimation and denoising using VC-theory

Signal denoising is closely related to function estimation from noisy samples. The same problem is also addressed in statistics (non-linear regression) and neural network learning. Vapnik-Chervonenkis (VC) theory has recently emerged as a general theory for estimation of dependencies from finite samples. This theory emphasizes model complexity control according to Structural Risk Minimization (SRM) inductive principle, which considers a nested set of models of increasing complexity (called a structure), and then selects an optimal model complexity providing minimum error for future samples. This paper applies the framework of VC-theory to signal estimation/denoising. There are three factors important for accurate signal estimation from finite samples: (1) the type of (orthogonal) basis functions used (i.e. Fourier basis, wavelets etc.). (2) The choice of a structure, i.e. ordering of the basis functions according to their 'importance' for accurate signal estimation. This corresponds to the choice of a 'structure' under SRM formulation. (3) Selecting an optimal number of terms (basis functions) from the ordered sequence of basis functions (2), aka model selection or complexity control (in statistics). We propose a methodology for specifying appropriate orderings (2) and an analytic expression for model selection (3) for signal processing applications. We also present empirical comparisons between the proposed methodology and current state-of-the-art wavelet thresholding methods for univariate signals. These comparisons suggest that the prudent choice of a structure (2) and the use of VC-based model selection (3) are critical for accurate signal estimation with finite samples.