📊 statistics

Wavelet Tree Ensembles for Triangulable Manifolds

This paper introduces unbalanced Haar wavelet tree ensembles for regression on triangulable manifolds, a method that constructs geodesic-adapted orthonormal wavelet systems to outperform classical tree ensembles and non-adaptive wavelets in tasks like climate anomaly modeling while providing Bayesian uncertainty quantification.

Original authors: Hengrui Luo, Akira Horiguchi, Li Ma

Published 2026-01-29

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Hengrui Luo, Akira Horiguchi, Li Ma

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to draw a detailed map of a strange, curvy island (like a sphere or a bumpy planet) based on a limited number of weather stations scattered across it. Your goal is to guess the temperature everywhere else on the island, even in places where you have no data.

This paper introduces a new, smarter way to draw that map. It combines two old ideas—Wavelets (which are like zoom lenses for spotting sharp changes) and Decision Trees (which are like a game of "20 Questions" to sort data)—into a powerful new tool called Wavelet Tree Ensembles.

Here is how it works, broken down into simple concepts:

1. The Problem with Old Maps

Traditional methods for drawing maps on curved surfaces often force the data into a rigid grid, like a checkerboard laid over a basketball.

The Issue: If you have a sharp temperature change right along a coastline, a rigid grid might cut right through the middle of the coast, blurring the line. It's like trying to fit a square peg in a round hole.
The Result: The map looks "fuzzy" in the important spots and misses the sharp details.

2. The New Tool: "Unbalanced" Trees

The authors created a new type of tree that doesn't care about rigid grids. Instead, it looks at the actual shape of the island and the data points.

The Analogy: Imagine you are cutting a pizza. A standard method always cuts the pizza exactly in half, then halves those halves again, no matter where the toppings are.
The Innovation: This new method is "unbalanced." If there is a huge pepperoni cluster on one side, it makes a tiny slice there to capture the detail, while leaving the plain cheese side as one big slice. It cuts the island exactly where the data changes the most.
The "Wavelet" Part: Every time it makes a cut, it creates a mathematical "wave" that measures the difference between the two new pieces. This ensures that when you add all the pieces back together, you get a perfect reconstruction of the data without losing information.

3. The Ensemble: The "Committee of Experts"

One single tree (or one expert) might make a mistake. To fix this, the paper uses an Ensemble approach.

The Analogy: Imagine you ask 100 different cartographers to draw the map.
- Random Forests (Old Way): Each cartographer draws a deep, complex map. They might overthink it and get confused by the noise (like wind or measurement errors).
- This New Way (Boosting/BART): The authors use a "committee" of many simple experts.
  - Boosting: The first expert draws a rough map. The second expert only looks at the mistakes the first one made and fixes them. The third expert fixes the second one's mistakes, and so on.
  - Bayesian (Uncertainty): They also have a version that doesn't just give one map, but gives a "confidence interval." It says, "I'm 95% sure the temperature here is between X and Y." This is like a weather forecaster saying, "It will rain, but I'm not 100% certain."

4. Why It's Better (The "Magic" of the Sphere)

The paper tested this on a sphere (like the Earth) and found it beats the old methods.

Adaptability: Because the cuts are based on the actual data and the shape of the triangles on the sphere, the map gets very detailed exactly where the temperature changes fast (like near the poles or oceans) and stays simple where the weather is calm.
Diversity: To make the "committee" work, they rotate the island slightly for each expert. This forces them to look at the data from different angles, ensuring they don't all make the same mistake.
Results: In their tests, this method produced much clearer, more accurate maps of temperature anomalies (like climate change hotspots) than traditional tree methods or standard wavelets. It also worked well for cleaning up noisy images.

Summary

The paper presents a new mathematical framework that allows computers to learn patterns on curved surfaces (like the Earth) much more efficiently. Instead of forcing data into a rigid box, it builds a flexible, "unbalanced" tree structure that adapts to the shape of the data. By combining many of these smart, simple trees, it creates highly accurate predictions and can even tell you how confident it is in those predictions.

Key Takeaway: It's a smarter, more flexible way to draw maps of complex, curved worlds, using a team of experts that specialize in finding the sharp edges and hidden details that other methods miss.

Technical Summary: Wavelet Tree Ensembles for Triangulable Manifolds

Problem Statement
The paper addresses the challenge of nonparametric regression on triangulable manifolds, such as spheres or general curved surfaces. Existing wavelet regression literature typically relies on wavelet bases defined along single recursive partition trees on fixed, regular Euclidean grids (e.g., dyadic intervals). These standard approaches struggle on manifolds due to the lack of natural coordinate axes and the distortion caused by global coordinate systems. Conversely, tree-based ensemble methods (e.g., Random Forests, Boosting) have been generalized to non-Euclidean domains but often lack the sparse, multiscale representation capabilities of wavelets, potentially leading to high variance or overfitting, particularly in low signal-to-noise regimes. The authors posit that a unified framework combining orthogonal wavelet representations with data-driven recursive partitions and modern ensemble techniques is needed to improve estimation and inference on these complex domains.

Methodology
The authors propose Unbalanced Haar (UH) Wavelet Tree Ensembles, a framework that extends classical UH wavelet trees from regular grids to generic triangulable manifolds. The methodology consists of three main components:

Unbalanced Haar (UH) Construction on Manifolds:
- Instead of fixed midpoints, the method employs data-driven recursive partitions of geodesic triangles.
- A triangle is split by connecting a point $\xi$ on an edge to the opposite vertex via a geodesic arc. The split location is chosen to maximize the empirical UH wavelet coefficient, allowing for "unbalanced" splits that adapt to local data variation and geometry.
- The resulting wavelet functions form an orthonormal system in $L^2(\mu_n)$ , where $\mu_n$ is the empirical measure on the sample points. This ensures exact reconstruction at sampled locations and orthogonality regardless of the underlying manifold geometry.
- Splitting rules include "balance" (mid-edge bisection), "adapt" (choosing the edge with the largest coefficient), and "adapt_vertex" (choosing both the edge and the cut point based on data).
Ensemble Learning Strategies:
- Optimization-based Boosting: The authors develop a forward stagewise boosting algorithm where weak learners are UH trees fitted to residuals. To ensure diversity among trees on manifolds, they employ random rigid motions (e.g., rotations in $SO(3)$ for spheres) or intrinsic reparameterizations before fitting each tree. Regularization is achieved through early stopping, learning rates, and soft-thresholding of wavelet coefficients at reconstruction.
- Bayesian Backfitting (RUHWT): A probabilistic formulation is introduced where a prior is placed over split dimensions and locations. This induces a posterior distribution over tree structures, allowing for uncertainty quantification. The authors utilize a Gibbs sampler with Metropolis-within-Gibbs steps to update tree structures and coefficients, analogous to Bayesian Additive Regression Trees (BART).
Theoretical Analysis:
- The paper derives oracle bounds comparing the proposed UH estimators to standard "leafwise" estimators (like CART). The analysis demonstrates that the stochastic error term for UH estimators scales with the number of active (non-zero) coefficients, whereas leafwise estimators scale with the total number of leaves. This suggests UH ensembles are particularly advantageous for signals that are sparse in the wavelet dictionary.

Key Contributions

Generalization to Manifolds: The work extends UH wavelet trees from 2D/3D grids to triangulable manifolds, preserving orthogonality and exact reconstruction properties via geodesic triangulations and empirical measures.
Data-Driven Adaptivity: Unlike balanced Haar bases on fixed grids, the proposed method allows splits at arbitrary locations along triangle edges, adapting to local signal variations and sampling densities.
Ensemble Integration: The paper introduces the first framework to combine orthogonal wavelets, geometry-aware recursive partitions, and ensemble techniques (both boosting and Bayesian) for regression on manifolds.
Uncertainty Quantification: A Bayesian variant (RUHWT) is provided, offering posterior uncertainty quantification for function estimates on manifolds.

Results
The authors evaluate the method on synthetic and real-world datasets:

Image Denoising (Euclidean Grid): On a noisy astronaut image, UH ensembles substantially outperform Balanced Haar (BH) ensembles. The results indicate that boosting is ineffective if weak learners are constrained to split at midpoints; the ability to split away from midpoints (unbalanced) is crucial for performance gains.
Synthetic Sphere Regression: On simulated data on a unit sphere, the Random-Rotation Boosting approach using UH trees achieves the lowest Mean Squared Error (MSE) compared to Fréchet Forests, Random Rotation Random Forests, and state-of-the-art deep Gaussian Process models. The method effectively smooths artificial boundaries found in non-rotated predictions.
Real-World Application (GISS): Applied to global surface temperature anomaly data (GISS), the UH ensemble on a triangulated sphere outperforms competing tree-based methods. The predictions show improved accuracy, particularly in capturing complex spatial variations, with the lowest test MSE observed for the Random-Rotation Boosted ensemble.

Significance and Claims
The paper claims to present the first unified regression method that integrates orthogonal wavelets, geometry-aware recursive partitions, and modern ensemble techniques for triangulable manifolds. The authors emphasize that their construction preserves three key properties: (i) orthogonality and exact reconstruction, (ii) recursive, data-driven partitions adapted to manifold geometry, and (iii) compatibility with both optimization-based and Bayesian ensemble building.

Theoretical results suggest that UH ensembles offer a sparsity-adaptive representation where risk is controlled by the number of significant coefficients rather than the total tree size, providing a theoretical advantage over traditional leafwise estimators. Empirically, the method demonstrates substantial improvements over classical tree ensembles and non-adaptive mesh-based wavelets, particularly in scenarios with low signal-to-noise ratios and complex geometries. The authors position this work as a practical and theoretically grounded tool for multiscale regression on complex domains, bridging the gap between classical wavelet theory and modern tree-based machine learning.