Wavelet regression and additive models for irregularly spaced data

Asad Haris, Ali Shojaie, Noah SimonNeurIPS 2018

Wavelets are a mathematical "Swiss Army knife" for signal processing and regression because they can capture both sharp spikes and smooth curves simultaneously, offering excellent time and frequency localization. However, traditional Discrete Wavelet Transforms (DWT) suffer from a notorious constraint: they typically require data to be perfectly equispaced on a grid, and the sample size ($n$) must be a power of two (e.g., 256, 512, 1024).

In the real world, data is messy. Observations are irregularly spaced, and sample sizes are arbitrary. Previous attempts to fix this usually involved interpolating the raw data onto a grid first. Unfortunately, this often fails in high-dimensional settings due to the "curse of dimensionality" or requires estimating the density of the predictors, adding another layer of error.

To address this, researchers have introduced waveMesh, a new framework that brings the power of wavelet regression to real-world, irregularly spaced data. By cleverly reversing how interpolation is used, waveMesh handles high-dimensional, sparse additive models while maintaining theoretical "gold standard" convergence speeds.

The waveMesh Approach: Grid-to-Data

The core innovation of waveMesh is a reversal of the standard interpolation approach. Instead of forcing the observed data onto a regular grid, the authors keep the data exactly where it is. They map the fitted values from a latent regular grid back to the observed data points.

  1. The Interpolation Matrix ($R$): The authors define a linear map that takes a function evaluated on a regular grid and interpolates it to the actual observed locations $x_i$.
  2. The Optimization Problem: Regression is framed as a penalized least-squares problem, conceptually similar to the Lasso. The goal is to find wavelet coefficients ($d$) that minimize the difference between the observed $y$ and the interpolated wavelet reconstruction ($RW^\top d$), plus an $\ell_1$ penalty to encourage sparsity.
  3. Proximal Gradient Descent: To solve this efficiently, the team developed an algorithm that leverages the speed of the traditional DWT ($O(n)$ operations) and the sparsity of the interpolation matrix.
  4. Sparse Additive Models: The framework naturally extends to multivariate data. For a large number of predictors ($p$), waveMesh uses a combination of penalties to perform both functional smoothing and variable selection (identifying which predictors are actually relevant).

By interpolating from the grid to the data, waveMesh completely avoids the need to estimate the density of the covariates, making the method significantly more robust in higher dimensions.

Experimental Validation

The authors evaluated waveMesh using both simulations and classic real-world benchmarks, including:

  • Simulated Univariate Functions: Standard test functions like "Bumps," "Doppler," and "Heavy Sine" to test the capture of discontinuities and oscillations.
  • Motorcycle Accident Dataset: A classic 1985 dataset of head acceleration over time, known for irregular spacing and varying noise levels.
  • Boston Housing Data: Used to test the multivariate additive model, predicting home values based on various environmental and social predictors.

Key Results

In head-to-head simulations against existing methods like "Adaptive Lifting" and "Isometric Wavelets," waveMesh achieved the lowest Mean Squared Error (MSE) in almost every univariate scenario.

MSE comparison of waveMesh against competing methods on univariate functions.

Beyond univariate tests, waveMesh demonstrated multivariate superiority. On the Boston Housing data and multivariate simulations, the waveMesh additive model significantly outperformed the established AMlet method. For example, in one simulation with $n=64$, waveMesh achieved an MSE of ~10.76 compared to AMlet's ~100.48.

Furthermore, waveMesh exhibited high visual fidelity. On the motorcycle dataset, it produced a smooth, physically plausible curve, whereas competing wavelet methods often yielded "wiggly" or highly variable estimates.

Theoretical Optimality and Flexibility

Crucially, the authors proved that waveMesh achieves adaptive minimax convergence rates. In practical terms, this means the method learns the underlying function nearly as fast as theoretically possible, even without knowing ahead of time how "smooth" the function is.

Interestingly, the grid size ($K$) does not have to match the sample size ($n$). Using a smaller $K$ can actually act as a form of regularization, improving performance on very smooth functions while saving on computational costs.

Limitations and Future Directions

While highly effective, waveMesh does have limitations. The proof for optimal rates in sparse additive models relies on a "compatibility condition"—a technical assumption about how predictors correlate that isn't always guaranteed to hold in practice. Additionally, unlike the standard DWT which is a single-pass algorithm, waveMesh requires iterative optimization. While fast, it remains more computationally demanding than "grid-only" methods.

Future extensions of the framework could adapt it to other loss functions (such as logistic regression for classification tasks) and different types of penalties, broadening the scope of wavelets for messy, real-world data.

Reference: Haris, A., Simon, N., & Shojaie, A. (2018). Wavelet regression and additive models for irregularly spaced data. 32nd Conference on Neural Information Processing Systems (NeurIPS 2018).

Summary updated

BibTeX
@inproceedings{haris2018wavelet,
  author = {Asad Haris and Ali Shojaie and Noah Simon},
  title = {{Wavelet regression and additive models for irregularly spaced data}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
}
Figure