Stable reconstructions in Hilbert spaces and the resolution of the Gibbs phenomenon. (English) Zbl 1245.94058
Authors’ abstract: “We introduce a simple and efficient method to reconstruct an element of a Hilbert space in terms of an arbitrary finite collection of linearly independent reconstruction vectors, given a finite number of its samples with respect to any Riesz basis. As we establish, provided the dimension of the reconstruction space is chosen suitably in relation to the number of samples, this procedure can be implemented in a completely numerically stable manner. Moreover, the accuracy of the resulting approximation is determined solely by the choice of reconstruction basis, meaning that reconstruction vectors can be readily tailored to the particular problem at hand.
An important example of this approach is the accurate recovery of a piecewise analytic function from its first few Fourier coefficients. Whilst the standard Fourier projection suffers from the Gibbs phenomenon, by reconstructing in a piecewise polynomial basis we obtain an approximation with root-exponential accuracy in terms of the number of Fourier samples and exponential accuracy in terms of the degree of the reconstruction. Numerical examples illustrate the advantage of this approach over other existing methods.”
An important example of this approach is the accurate recovery of a piecewise analytic function from its first few Fourier coefficients. Whilst the standard Fourier projection suffers from the Gibbs phenomenon, by reconstructing in a piecewise polynomial basis we obtain an approximation with root-exponential accuracy in terms of the number of Fourier samples and exponential accuracy in terms of the degree of the reconstruction. Numerical examples illustrate the advantage of this approach over other existing methods.”
Reviewer: Toivo Leiger (Tartu)
MSC:
| 94A20 | Sampling theory in information and communication theory |
| 46C05 | Hilbert and pre-Hilbert spaces: geometry and topology (including spaces with semidefinite inner product) |
| 42C15 | General harmonic expansions, frames |
References:
| [1] | Abramowitz, M.; Stegun, I. A., Handbook of Mathematical Functions (1974), Dover |
| [2] | B. Adcock, Modified Fourier expansions: theory, construction and applications, PhD thesis, University of Cambridge, 2010.; B. Adcock, Modified Fourier expansions: theory, construction and applications, PhD thesis, University of Cambridge, 2010. · Zbl 1193.65235 |
| [3] | Adcock, B., Multivariate modified Fourier series and application to boundary value problems, Numer. Math., 115, 4, 511-552 (2010) · Zbl 1193.65235 |
| [4] | B. Adcock, A.C. Hansen, A generalized sampling theorem for stable reconstructions in arbitrary bases, Technical report NA2010/07, DAMTP, University of Cambridge, 2010.; B. Adcock, A.C. Hansen, A generalized sampling theorem for stable reconstructions in arbitrary bases, Technical report NA2010/07, DAMTP, University of Cambridge, 2010. · Zbl 1259.94035 |
| [5] | B. Adcock, A.C. Hansen, Generalized sampling and infinite-dimensional compressed sensing, Technical report NA2011/02, DAMTP, University of Cambridge, 2011.; B. Adcock, A.C. Hansen, Generalized sampling and infinite-dimensional compressed sensing, Technical report NA2011/02, DAMTP, University of Cambridge, 2011. · Zbl 1379.94026 |
| [6] | B. Adcock, A.C. Hansen, Sharp bounds, optimality and a geometric interpretation for generalised sampling in Hilbert spaces, Technical report NA2011/10, DAMTP, University of Cambridge, 2011.; B. Adcock, A.C. Hansen, Sharp bounds, optimality and a geometric interpretation for generalised sampling in Hilbert spaces, Technical report NA2011/10, DAMTP, University of Cambridge, 2011. |
| [7] | Adcock, B.; Huybrechs, D., Multivariate modified Fourier expansions, (Rønquist, E.; etal., Proceedings of the International Conference on Spectral and High Order Methods (2011)) · Zbl 1216.65150 |
| [8] | Archibald, R.; Chen, K.; Gelb, A.; Renault, R., Improving tissue segmentation of human brain MRI through preprocessing by the Gegenbauer reconstruction method, NeuroImage, 20, 1, 489-502 (2003) |
| [9] | Archibald, R.; Gelb, A., A method to reduce the Gibbs ringing artifact in MRI scans while keeping tissue boundary integrity, IEEE Trans. Med. Imaging, 21, 4, 305-319 (2002) |
| [10] | Bateman, H., Higher Transcendental Functions, vol. 2 (1953), McGraw-Hill: McGraw-Hill New York · Zbl 0051.30303 |
| [11] | Böttcher, A.; Dörfler, P., Weighted Markov-type inequalities, norms of Volterra operators, and zeros of Bessel functions, Math. Nachr., 283, 1, 40-57 (2010) · Zbl 1186.41004 |
| [12] | Boyd, J. P., Chebyshev and Fourier Spectral Methods (1989), Springer-Verlag · Zbl 0681.65079 |
| [13] | Boyd, J. P., A comparison of numerical algorithms for Fourier extension of the first, second, and third kinds, J. Comput. Phys., 178, 118-160 (2002) · Zbl 0999.65132 |
| [14] | Boyd, J. P., Trouble with Gegenbauer reconstruction for defeating Gibbs phenomenon: Runge phenomenon in the diagonal limit of Gegenbauer polynomial approximations, J. Comput. Phys., 204, 1, 253-264 (2005) · Zbl 1071.65189 |
| [15] | Boyd, J. P., Acceleration of algebraically-converging Fourier series when the coefficients have series in powers of \(1 / n\), J. Comput. Phys., 228, 1404-1411 (2009) · Zbl 1159.65112 |
| [16] | Boyd, J. P.; Ong, J. R., Exponentially-convergent strategies for defeating the Runge phenomenon for the approximation of non-periodic functions. I. Single-interval schemes, Commun. Comput. Phys., 5, 2-4, 484-497 (2009) · Zbl 1364.65025 |
| [17] | Boyd, J. P.; Xu, F., Divergence (Runge phenomenon) for least-squares polynomial approximation on an equispaced grid and mock-Chebyshev subset interpolation, Appl. Math. Comput., 210, 1, 158-168 (2009) · Zbl 1171.41004 |
| [18] | Brezinski, C., Extrapolation algorithms for filtering series of functions, and treating the Gibbs phenomenon, Numer. Algorithms, 36, 309-329 (2004) · Zbl 1071.42003 |
| [19] | Candès, E. J., An introduction to compressive sensing, IEEE Signal Process. Mag., 25, 2, 21-30 (2008) |
| [20] | Canuto, C.; Hussaini, M. Y.; Quarteroni, A.; Zang, T. A., Spectral Methods: Fundamentals in Single Domains (2006), Springer · Zbl 1093.76002 |
| [21] | Christensen, O., An Introduction to Frames and Riesz Bases (2003), Birkhäuser · Zbl 1017.42022 |
| [22] | V. Dominguez, I.G. Graham, V.P. Smyshlyaev, Stability and error estimates for Filon-Clenshaw-Curtis rules for highly-oscillatory integrals, IMA J. Numer. Anal., doi:10.1093/imanum/drq036; V. Dominguez, I.G. Graham, V.P. Smyshlyaev, Stability and error estimates for Filon-Clenshaw-Curtis rules for highly-oscillatory integrals, IMA J. Numer. Anal., doi:10.1093/imanum/drq036 · Zbl 1231.65060 |
| [23] | Donoho, D. L., Compressed sensing, IEEE Trans. Inform. Theory, 52, 4, 1289-1306 (2006) · Zbl 1288.94016 |
| [24] | Driscoll, T. A.; Fornberg, B., A Padé-based algorithm for overcoming the Gibbs phenomenon, Numer. Algorithms, 26, 77-92 (2001) · Zbl 0973.65133 |
| [25] | Dutt, A.; Rokhlin, V., Fast Fourier transforms for nonequispaced data, SIAM J. Sci. Comput., 14, 6, 1368-1393 (1993) · Zbl 0791.65108 |
| [26] | Dutt, A.; Rokhlin, V., Fast Fourier transforms for nonequispaced data, II, Appl. Comput. Harmon. Anal., 2, 85-100 (1995) · Zbl 0822.65130 |
| [27] | Eckhoff, K. S., On a high order numerical method for functions with singularities, Math. Comp., 67, 223, 1063-1087 (1998) · Zbl 0895.65067 |
| [28] | Eldar, Y. C., Sampling without input constraints: Consistent reconstruction in arbitrary spaces, (Zayed, A. I.; Benedetto, J. J., Sampling, Wavelets and Tomography (2004), Birkhäuser: Birkhäuser Boston, MA), 33-60 · Zbl 1062.94536 |
| [29] | Eldar, Y. C.; Werther, T., General framework for consistent sampling in Hilbert spaces, Int. J. Wavelets Multiresolut. Inf. Process., 3, 3, 347 (2005) · Zbl 1075.42010 |
| [30] | Gelb, A., The resolution of the Gibbs phenomenon for spherical harmonics, Math. Comp., 66, 218, 699-717 (1997) · Zbl 0863.42004 |
| [31] | Gelb, A., Reconstruction of piecewise smooth functions from non-uniform grid point data, J. Sci. Comput., 30, 3, 409-440 (2007) · Zbl 1113.65014 |
| [32] | Gelb, A.; Gottlieb, S., The resolution of the Gibbs phenomenon for Fourier spectral methods, (Jerri, A., Advances in the Gibbs Phenomenon (2007), Sampling Publishing: Sampling Publishing Potsdam, New York) · Zbl 0911.65145 |
| [33] | A. Gelb, T. Hines, Detection of edges from nonuniform Fourier data, J. Fourier Anal. Appl., doi:10.1007/s00041-011-9172-7; A. Gelb, T. Hines, Detection of edges from nonuniform Fourier data, J. Fourier Anal. Appl., doi:10.1007/s00041-011-9172-7 · Zbl 1236.42026 |
| [34] | Gelb, A.; Tadmor, E., Detection of edges in spectral data, Appl. Comput. Harmon. Anal., 7, 1, 101 (1999) · Zbl 0952.42001 |
| [35] | Gelb, A.; Tanner, J., Robust reprojection methods for the resolution of the Gibbs phenomenon, Appl. Comput. Harmon. Anal., 20, 3-25 (2006) · Zbl 1088.42001 |
| [36] | Gilbarg, D.; Trudinger, N. S., Elliptic Partial Differential Equations of Second Order (2001), Springer-Verlag · Zbl 1042.35002 |
| [37] | Golub, G. H.; Van Loan, C. F., Matrix Computations (1989), John Hopkins University Press: John Hopkins University Press Baltimore · Zbl 0733.65016 |
| [38] | Gottlieb, D.; Hesthaven, J. S., Spectral methods for hyperbolic problems, J. Comput. Appl. Math., 128, 1-2, 83-131 (2001) · Zbl 0974.65093 |
| [39] | Gottlieb, D.; Shu, C.-W., On the Gibbs phenomenon IV: Recovering exponential accuracy in a subinterval from a Gegenbauer partial sum of a piecewise analytic function, Math. Comp., 64, 211, 1081-1095 (1995) · Zbl 0852.42018 |
| [40] | Gottlieb, D.; Shu, C.-W., On the Gibbs phenomenon III: Recovering exponential accuracy in a sub-interval from a spectral partial sum of a piecewise analytic function, SIAM J. Numer. Anal., 33, 1, 280-290 (1996) · Zbl 0852.42017 |
| [41] | Gottlieb, D.; Shu, C.-W., On the Gibbsʼ phenomenon and its resolution, SIAM Rev., 39, 4, 644-668 (1997) · Zbl 0885.42003 |
| [42] | Gottlieb, D.; Shu, C.-W.; Solomonoff, A.; Vandeven, H., On the Gibbs phenomenon I: Recovering exponential accuracy from the Fourier partial sum of a nonperiodic analytic function, J. Comput. Appl. Math., 43, 1-2, 91-98 (1992) · Zbl 0781.42022 |
| [43] | Gröchenig, K.; Rzeszotnik, Z.; Strohmer, T., Quantitative estimates for the finite section method and Banach algebras of matrices, Integral Equations Operator Theory, 67, 2, 183-202 (2011) · Zbl 1197.65053 |
| [44] | Hansen, A. C., On the solvability complexity index, the \(n\)-pseudospectrum and approximations of spectra of operators, J. Amer. Math. Soc., 24, 1, 81-124 (2011) · Zbl 1210.47013 |
| [45] | Heinemeyer, E.; Lindner, M.; Potthast, R., Convergence and numerics of a multisection method for scattering by three-dimensional rough surfaces, SIAM J. Numer. Anal., 46, 4, 1780-1798 (2008) · Zbl 1173.65070 |
| [46] | Hesthaven, J. S.; Gottlieb, S.; Gottlieb, D., Spectral Methods for Time-Dependent Problems (2007), Cambridge University Press · Zbl 1111.65093 |
| [47] | Hrycak, T.; Gröchenig, K., Pseudospectral Fourier reconstruction with the modified inverse polynomial reconstruction method, J. Comput. Phys., 229, 3, 933-946 (2010) · Zbl 1184.65123 |
| [48] | Huybrechs, D., On the Fourier extension of non-periodic functions, SIAM J. Numer. Anal., 47, 6, 4326-4355 (2010) · Zbl 1209.65153 |
| [49] | Iserles, A.; Nørsett, S. P., From high oscillation to rapid approximation I: Modified Fourier expansions, IMA J. Numer. Anal., 28, 862-887 (2008) · Zbl 1221.65348 |
| [50] | (Jerri, A. J., The Gibbs Phenomenon in Fourier Analysis, Splines, and Wavelet Approximations (1998), Kluwer Academic: Kluwer Academic Dordrecht) · Zbl 0918.42001 |
| [51] | (Jerri, A. J., Advances in the Gibbs Phenomenon (2007), Sampling Publishing: Sampling Publishing Potsdam, New York) |
| [52] | Jung, J.-H.; Shizgal, B. D., Towards the resolution of the Gibbs phenomena, J. Comput. Appl. Math., 161, 1, 41-65 (2003) · Zbl 1033.65122 |
| [53] | Jung, J.-H.; Shizgal, B. D., Generalization of the inverse polynomial reconstruction method in the resolution of the Gibbs phenomenon, J. Comput. Appl. Math., 172, 1, 131-151 (2004) · Zbl 1053.65102 |
| [54] | Jung, J. H.; Gottlieb, S.; Kim, S. O.; Bresten, C. L.; Higgs, D., Recovery of high order accuracy in radial basis function approximations of discontinuous problems, J. Sci. Comput., 45, 359-381 (2010) · Zbl 1203.41011 |
| [55] | Kamm, J. R.; Williams, T. O.; Brock, J. S.; Li, S., Application of Gegenbauer polynomial expansions to mitigate Gibbs phenomenon in Fourier-Bessel series solutions of a dynamic sphere problem, Int. J. Numer. Methods Biomed. Eng., 26, 1276-1292 (2010) · Zbl 1274.74179 |
| [56] | Körner, T. W., Fourier Analysis (1988), Cambridge University Press · Zbl 0649.42001 |
| [57] | Platte, R.; Trefethen, L. N.; Kuijlaars, A., Impossibility of fast stable approximation of analytic functions from equispaced samples, SIAM Rev., 53, 308-318 (2011) · Zbl 1247.41001 |
| [58] | Rivlin, T. J.; Kalashnikov, V., Chebyshev Polynomials: From Approximation Theory to Algebra and Number Theory (1990), Wiley: Wiley New York · Zbl 0734.41029 |
| [59] | Schmidt, E., Die asymptotische Bestimmung des Maximums des Integrals über das Quadrat der Ableitung eines normierten Polynoms, dessen Grad ins Unendliche wächst, Sitzungsber. Preuss. Akad. Wiss., 287 (1932) · JFM 58.1100.04 |
| [60] | Schmidt, E., Über die nebst ihren Ableitungen orthogonalen Polynomensysteme und das zugehörige Extremum, Math. Ann., 119, 165-204 (1944) · Zbl 0028.39402 |
| [61] | Tadmor, E., Filters, mollifiers and the computation of the Gibbsʼ phenomenon, Acta Numer., 16, 305-378 (2007) · Zbl 1125.65122 |
| [62] | Tadmor, E.; Tanner, J., Adaptive mollifiers for high resolution recovery of piecewise smooth data from its spectral information, Found. Comput. Math., 2, 2, 155-189 (2002) · Zbl 1056.42002 |
| [63] | Unser, M., Sampling—50 years after Shannon, Proc. IEEE, 88, 4, 569-587 (2000) · Zbl 1404.94028 |
| [64] | Viswanathan, A.; Gelb, A.; Cochran, D.; Renaut, R., On reconstructions from non-uniform spectral data, J. Sci. Comput., 45, 1-3, 487-513 (2010) · Zbl 1203.65290 |
| [65] | L. Wang, Y. Wang, Reconstruction from irregular Fourier samples and Gaussian spectral mollifiers, preprint, 2011.; L. Wang, Y. Wang, Reconstruction from irregular Fourier samples and Gaussian spectral mollifiers, preprint, 2011. · Zbl 1232.42026 |
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.
