Wavelet interpolation networks

Christophe P. Bernard, Stéphane Mallat, Jean-Jacques E. SlotineESANN 1998

Abstract

Real-time function approximation is a critical component in adaptive robotic control, where systems must learn unknown mappings from streaming, scattered data. This paper introduces Wavelet Interpolation Networks, a method that utilizes a hierarchical tryadic wavelet basis to adaptively allocate data points. By employing a "pachinko-like" allocation strategy, the algorithm constructs a sparse, high-precision model that focuses computational resources on complex regions or dense data areas.

Introduction

In fields such as adaptive robotic control, systems are frequently required to learn unknown functions—such as the mapping between motor torques and movements—on the fly. This task presents significant challenges: updates must occur in real-time, the problem is often ill-posed with limited data, and memory efficiency is paramount for long-term operation. Existing high-quality regularization techniques are often too computationally intensive for high-speed loops, while fast neural network updates may lack the necessary smoothness or global consistency.

Methodology

The proposed approach leverages Tryadic (3-band) Wavelets. Unlike standard binary wavelets, tryadic wavelets provide a cleaner hierarchical tree structure where each parent node branches into $3^n$ children, facilitating a more natural spatial decomposition.

Hierarchical Allocation: The "Pachinko" Method

The core innovation is the "Pachinko" allocation algorithm. As a new data point $(x, y)$ enters the system, it "falls" through the wavelet tree. At each level, the point gravitates toward the nearest node. If a node is already occupied, a competition occurs: the point closest to the node's center remains, while the other is pushed to a higher-resolution level.

Tryadic wavelet nodes and their corresponding tree structure.

This mechanism ensures an adaptive grid where high-resolution wavelets are deployed only where necessary—specifically in regions with high data density or sharp functional transitions.

The hierarchical allocation process ('Pachinko' method) for new data points.

Efficient Computation and Truncation

To maintain real-time performance, the system solves a linear system ($AC = Y$) for wavelet coefficients. Instead of full matrix inversion, a Sherman-Morrison-like formula allows for $O(\log^2 N)$ updates to the inverse matrix ($A^{-1}$). Furthermore, the model employs a truncation step, pruning coefficients that fall below a significance threshold. This "forgetting" mechanism effectively compresses the model by discarding non-informative data.

Experimental Evaluation

The method was evaluated using synthetic piecewise smooth functions in 1D and 2D:

  • 1D Experiment: A function with a singularity at $x=0.5$ was sampled with 200 random points. The system successfully maintained an accurate model using only 24 measures, discarding 88% of the data.
  • 2D Experiment: A sinusoidal function was sampled along a specific trajectory. The system retained only 27 out of 197 points.

In both cases, approximation errors remained remarkably low—less than $3 \cdot 10^{-3}$ near singularities and $3 \cdot 10^{-5}$ in smooth regions—demonstrating high precision despite significant data pruning.

Discussion and Conclusion

Wavelet Interpolation Networks offer a compelling balance between local adaptivity and global regularization. The "pachinko" allocation provides a robust way to implement adaptive resolution, ensuring computational resources are spent where the function is most complex. Because wavelets are localized in both space and frequency, updates remain computationally efficient.

Future work should address the "curse of dimensionality" inherent in the $3^n$ branching factor for high-dimensional inputs and investigate the system's robustness to high-variance sensor noise. Transitioning from software simulations to real-world robotic hardware remains the primary next step for validating this "pachinko" approach to learning.

Summary updated

BibTeX
@inproceedings{bernard1998wavelet,
  author = {Christophe P. Bernard and Stéphane Mallat and Jean-Jacques E. Slotine},
  title = {{Wavelet interpolation networks}},
  booktitle = {ESANN},
  year = {1998},
}
Figure