Approximation

The problem of fitting a curve, surface or function to scattered, possibly noisy, data arises in many applications in science and engineering.(see e.g. Applications of Wavelets.) Approximation from observed data is often needed. This has been widely studied in the literature when the data is exact and the underlying function is smooth. However, the observed data is often contaminated with noise and the underlying function may be non-smooth (e.g. contains singularities). To properly handle noisy data, any effective approximation scheme must contain a noise removal component. This project presents a theoretical analysis of such noise removal schemes through the lens of approximation.

We first provided an error analysis of fitting a  smooth curve, surface or function to scattered and noisy data in [4] which, roughly speaking, states that the error between the exact (probably unknown) data function and the obtained fitting function is small whenever the scattered samples have a high sampling density and a low noise level. We then gave a computational formulation using splines and wavelet frames constructed from splines.

To well approximate a non-smooth curve, surface, or function, one needs to have a sparse approximation in, for example, the wavelet domain. Sparsity-based noise removal schemes have been proven effective empirically.  For a given sample size, approximation from uniform grid data and scattered data were investigated in [1, 2]. The error of the approximation scheme, the bias of the denoising model, and the noise level of data was analyzed, respectively. In addition, when the amount of data is large enough, a new approximation scheme was proposed to grant sufficient reduction on the noise level and ensure asymptotic convergence. Moreover, a link to wavelet frame-based image restoration models was established and the convergence of these models was analyzed. One of the most important examples of our model studied in [3] is image recovery from randomly sampled pixels, which occurs when part of the pixel is randomly missing due to, e.g., the unreliable communication channel or the corruption by salt-and-pepper noise. While many such algorithms have been developed recently, there are very few papers available on their error estimations. Paper [3] analyzes the error of a frame-based data recovery approach from random samples. In particular, we estimated the error between the underlying original data and the approximate solution that interpolates (or approximates with an error bound depending on the noise level) the given data that has a sparse approximation in the canonical frame domain.

    1. Bin Dong, Zuowei Shen, Jianbin Yang, Approximation from Noisy Data, SIAM Journal on Numerical Analysis, 59(5), (2021), 2722-2745. PDF
    2. Jianbin Yang, Dominik Stahl, Zuowei Shen, An analysis of wavelet frame based scattered data reconstruction, Applied and Computational Harmonic Analysis, 42(3), (2017), 480-507. PDF
    3. Jianfeng Cai, Zuowei Shen, Guibo Ye, Approximation of frame based missing data recovery, Applied and Computational Harmonic Analysis, 31(2), (2011), 185-204 PDF
    4. M. J. Johnson, Zuowei Shen, Yuhong Xu, Scattered data reconstruction by regularization in B-spline and associated wavelet spaces, Journal of Approximation Theory, 159 (2009), 197-223. PDF