Abstract
This paper concerns with iterative schemes for the perfect reconstruction of functions belonging to multiresolution spaces on bounded manifolds from nonuniform sampling. The schemes have optimal complexity in the sense that the computational cost to achieve a certain fixed accuracy is proportional to the computed quantity. Since the iterations converge uniformly, one can produce corresponding iterative integration schemes that allow to recover the integral of functions belonging to multiresolution spaces from nonuniform sampling. We present also an error analysis and, in particular, we estimate the $L^2$-error which one produces in recovering smooth functions in $H^s$, but not necessarily in any multiresolution space, and their integrals from nonuniform sampling. Several uni- and bi-variate numerical examples are illustrated and discussed. We also show that one can construct a rather large variety of multiresolution spaces on manifolds from certain refinable bases on the real line formed by so-called GP-functions. This class of functions that contains in particular B-splines has remarkable properties in terms of producing well-conditioned bases. The resulting multiresolution analyses are well-suited for the application of the iterative recovering of functions from nonuniform sampling.
Introduction: The Challenge of Nonuniform Sampling
In many practical scenarios, from digital image restoration to astronomical observations, data is rarely collected at perfectly regular intervals. This phenomenon, known as nonuniform sampling, poses a significant challenge for traditional signal processing techniques like the Shannon-Nyquist theorem, which typically assume infinite, regularly sampled domains.
Most real-world problems occur on bounded domains—finite intervals, 2D images, or manifold surfaces. Reconstructing a continuous signal from scattered, finite data points requires a framework that is both mathematically rigorous and computationally efficient. Existing methods often suffer from numerical instability or high computational overhead. This paper addresses these issues by introducing an iterative reconstruction scheme with optimal complexity.
Methodology: Multiresolution Analysis and GP-Functions
The proposed framework leverages Multiresolution Analysis (MRA), which represents functions across a series of nested spaces of increasing detail. A key technical innovation is the use of GP-functions (generalized refinable functions) to construct these spaces. While B-splines are commonly used, they can become ill-conditioned in certain settings. GP-functions provide a more flexible and numerically stable alternative, ensuring that the resulting bases are well-suited for computer implementation.
The Iterative Reconstruction Framework
The core of the approach consists of two primary algorithms:
- RESTORE: An iterative scheme that uses a "quasi-interpolation" operator to project sampled data into the MRA space. Starting from an initial guess, the algorithm repeatedly applies corrections to converge toward the true function.
- INTEGRATE: An extension that allows for the precise calculation of a function's total integral directly from nonuniform samples, bypassing the need for a full continuous reconstruction first.
Key Insights and Results
The authors demonstrate that their iterative schemes achieve optimal complexity, meaning the computational cost scales linearly with the amount of data. By avoiding the inversion of large, dense matrices—a common bottleneck in other methods—the algorithm remains fast even for high-resolution data.
Numerical experiments validate the theory:
- Perfect Reconstruction: Functions within the multiresolution space are recovered exactly given a sufficiently dense sampling set.
- Error Bounds: For smooth functions outside the MRA space, the authors provide rigorous $L^2$ error estimates, showing predictable error reduction as resolution increases.
- Stability: Tuning the parameters of GP-functions significantly improves numerical stability compared to standard spline-based approaches.
In 2D surface reconstruction tests, the algorithm successfully recovered complex "bumpy" surfaces from random sampling points with high fidelity. Similarly, 1D integration tests showed the error dropping from $10^{-1}$ to $10^{-6}$ over successive iterations.
Conclusion and Future Directions
This research provides a robust bridge between abstract sampling theory and practical application. The iterative nature of the RESTORE and INTEGRATE algorithms makes them highly suitable for large-scale data processing on bounded domains.
A current limitation is the requirement for "$\Delta$-dense" sampling; large gaps in data can slow convergence. Future work may explore the use of frames—redundant mathematical bases—to better handle complex geometries and noisy boundaries, further enhancing the algorithm's versatility in real-world environments.
Summary updated