Approximation from noisy data. (English) Zbl 1512.94016
Summary: In most applications, functions are often given by sampled data. Approximation of functions from observed data is often needed. This has been widely studied in the literature when data is exact and the underlying function is smooth. However, the observed data is often contaminated with noise and the underlying function may be nonsmooth (e.g., contains singularities). To properly handle noisy data, any effective approximation scheme must contain a noise removal component. To well approximate nonsmooth functions, one needs to have a sparse approximation in, for example, the wavelet domain. Sparsity-based noise removal schemes have been proven effective empirically. This paper presents theoretical analysis of such noise removal schemes through the lens of function approximation. For a given sample size, approximation from uniform grid data and scattered data is investigated. The error of the approximation scheme, the bias of the denoising model, and the noise level of data are analyzed, respectively. In addition, when the amount of data is large enough, a new approximation scheme is proposed to grant sufficient reduction on the noise level and ensure asymptotic convergence.
MSC:
| 94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |
| 94A20 | Sampling theory in information and communication theory |
| 42C40 | Nontrigonometric harmonic analysis involving wavelets and other special systems |
| 42C15 | General harmonic expansions, frames |
| 46E35 | Sobolev spaces and other spaces of “smooth” functions, embedding theorems, trace theorems |
| 65D05 | Numerical interpolation |
| 65D10 | Numerical smoothing, curve fitting |
| 65D15 | Algorithms for approximation of functions |
| 41A30 | Approximation by other special function classes |
References:
| [1] | R. A. Adams and J. J. Fournier, Sobolev Spaces, Academic Press, 2003. · Zbl 1098.46001 |
| [2] | R. Arcangéli, M. C. L. de Silanes, and J. J. Torrens, An extension of a bound for functions in Sobolev spaces, with applications to \((m, s)\)-spline interpolation and smoothing, Numer. Math., 107 (2007), pp. 181-211. · Zbl 1221.41012 |
| [3] | A. Ben-Tal and E. Hochman, More bounds on the expectation of a convex function of a random variable, J. Appl. Probab., 9 (1972), pp. 803-812. · Zbl 0246.60011 |
| [4] | L. Borup, R. Gribonval, and M. Nielsen, Bi-framelet systems with few vanishing moments characterize Besov spaces, Appl. Comput. Harmon. Anal., 17 (2004), pp. 3-28. · Zbl 1042.42028 |
| [5] | J.-F. Cai, B. Dong, S. Osher, and Z. Shen, Image restoration: Total variation, wavelet frames, and beyond, J. Amer. Math. Soc., 25 (2012), pp. 1033-1089. · Zbl 1277.35019 |
| [6] | J.-F. Cai, S. Osher, and Z. Shen, Split Bregman methods and frame based image restoration, Multiscale Model. Simul., 8 (2009), pp. 337-369, https://doi.org/10.1137/090753504. · Zbl 1189.94014 |
| [7] | A. Chambolle, R. A. De Vore, N.-Y. Lee, and B. J. Lucier, Nonlinear wavelet image processing: Variational problems, compression, and noise removal through wavelet shrinkage, IEEE Trans. Image Process., 7 (1998), pp. 319-335. · Zbl 0993.94507 |
| [8] | Z. Chen, R. Tuo, and W. Zhang, Stochastic convergence of a nonconforming finite element method for the thin plate spline smoother for observational data, SIAM J. Numer. Anal., 56 (2018), pp. 635-659, https://doi.org/10.1137/16M109630X. · Zbl 1397.65254 |
| [9] | Z. Chen, R. Tuo, and W. Zhang, A balanced oversampling finite element method for elliptic problems with observational boundary data, J. Comput. Math., 38 (2020), pp. 355-374. · Zbl 1463.65364 |
| [10] | W. Dahmen, Multiscale and wavelet methods for operator equations, in Multiscale Problems and Methods in Numerical Simulations, Springer, 2003, pp. 31-96. · Zbl 1036.65095 |
| [11] | I. Daubechies, B. Han, A. Ron, and Z. Shen, Framelets: MRA-based constructions of wavelet frames, Appl. Comput. Harmon. Anal., 14 (2003), pp. 1-46. · Zbl 1035.42031 |
| [12] | C. de Boor, R. A. Devore, and A. Ron, Approximation from shift-invariant subspaces of \(L_2(\mathbb R^d)\), Trans. Amer. Math. Soc., 341 (1994), pp. 787-806. · Zbl 0790.41012 |
| [13] | B. Dong, Q. Jiang, and Z. Shen, Image restoration: Wavelet frame shrinkage, nonlinear evolution PDEs, and beyond, Multiscale Model. Simul., 15 (2017), pp. 606-660, https://doi.org/10.1137/15M1037457. · Zbl 1378.35159 |
| [14] | B. Dong and Z. Shen, MRA Based Wavelet Frames and Applications, IAS Lecture Notes Series, Summer Program on the Mathematics of Image Processing, Park City Mathematics Institute, 2010. |
| [15] | B. Dong, Z. Shen, and P. Xie, Image restoration: A general wavelet frame based model and its asymptotic analysis, SIAM J. Math. Anal., 49 (2017), pp. 421-445, https://doi.org/10.1137/16M1064969. · Zbl 1366.42035 |
| [16] | W. Gao, X. Sun, Z. Wu, and X. Zhou, Multivariate Monte Carlo approximation based on scattered data, SIAM J. Sci. Comput., 42 (2020), pp. A2262-A2280, https://doi.org/10.1137/19M1249138. · Zbl 1489.65020 |
| [17] | I. Goodfellow, Y. Bengio, and A. Courville, Deep Learning, MIT Press, Cambridge, MA, 2016. · Zbl 1373.68009 |
| [18] | B. Han and Z. Shen, Dual wavelet frames and Riesz bases in Sobolev spaces, Constr. Approx., 29 (2009), pp. 369-406. · Zbl 1161.42018 |
| [19] | W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc., 58 (1963), pp. 13-30. · Zbl 0127.10602 |
| [20] | H. Ji, Z. Shen, and Y. Xu, Wavelet frame based scene reconstruction from range data, J. Comput. Phys., 229 (2010), pp. 2093-2108. · Zbl 1185.65029 |
| [21] | R.-Q. Jia, Approximation with scaled shift-invariant spaces by means of quasi-projection operators, J. Approx. Theory, 131 (2004), pp. 30-46. · Zbl 1064.41013 |
| [22] | R.-Q. Jia and C. A. Micchelli, Using the refinement equations for the construction of pre-wavelets II: Powers of two, in Curves and Surfaces, Elsevier, 1991, pp. 209-246. · Zbl 0777.41013 |
| [23] | M. J. Johnson, Scattered date interpolation from principal shift-invariant spaces, J. Approx. Theory, 113 (2001), pp. 172-188. · Zbl 0991.41005 |
| [24] | M. J. Johnson, Z. Shen, and Y. Xu, Scattered data reconstruction by regularization in B-spline and associated wavelet spaces, J. Approx. Theory, 159 (2009), pp. 197-223. · Zbl 1181.41013 |
| [25] | S. Mallat, A Wavelet Tour of Signal Processing: The Sparse Way, Academic Press, 2008. · Zbl 1170.94003 |
| [26] | D. B. Mumford and J. Shah, Optimal approximations by piecewise smooth functions and associated variational problems, Comm. Pure Appl. Math., 42 (1989), pp. 577-685. · Zbl 0691.49036 |
| [27] | A. Ron and Z. Shen, Affine systems in \(L_2(\mathbb R^d)\): The analysis of the analysis operator, J. Funct. Anal., 148 (1997), pp. 408-447. · Zbl 0891.42018 |
| [28] | L. I. Rudin, S. Osher, and E. Fatemi, Nonlinear total variation based noise removal algorithms, Phys. D, 60 (1992), pp. 259-268. · Zbl 0780.49028 |
| [29] | Z. Shen, Wavelet frames and image restorations, in Proceedings of the International Congress of Mathematicians 2010, World Scientific, 2010, pp. 2834-2863. · Zbl 1228.42036 |
| [30] | G. Strang and G. Fix, A Fourier analysis of the finite element variational method, in Constructive Aspects of Functional Analysis, Springer, 1973, pp. 793-840. · Zbl 0278.65116 |
| [31] | G. Wahba, Spline Models for Observational Data, SIAM, 1990, https://doi.org/10.1137/1.9781611970128. · Zbl 0813.62001 |
| [32] | H. Wendland, Scattered Data Approximation, Cambridge University Press, 2005. · Zbl 1075.65021 |
| [33] | Y. Xu and Q. Ye, Generalized Mercer kernels and reproducing kernel Banach spaces, Mem. Amer. Math. Soc., 258 (1243) (2019). · Zbl 1455.68009 |
| [34] | J. Yang, Random sampling and reconstruction in multiply generated shift-invariant spaces, Anal. Appl., 17 (2019), pp. 323-347. · Zbl 1417.42045 |
| [35] | J. Yang, D. Stahl, and Z. Shen, An analysis of wavelet frame based scattered data reconstruction, Appl. Comput. Harmon. Anal., 42 (2017), pp. 480-507. · Zbl 1412.94261 |
| [36] | J. Yang, G. Zhu, D. Tong, L. Lu, and Z. Shen, B-spline tight frame based force matching method, J. Comput. Phys., 362 (2018), pp. 208-219. · Zbl 1422.65094 |
| [37] | Q. Zhang, L. Wang, and W. Sun, Signal denoising with average sampling, Digital Signal Process., 22 (2012), pp. 226-232. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
