Complete algebraic reconstruction of piecewise-smooth functions from Fourier data

Batenkov, Dmitry

doi:10.1090/S0025-5718-2015-02948-2

Complete algebraic reconstruction of piecewise-smooth functions from Fourier data

Author: Dmitry Batenkov
Journal: Math. Comp. 84 (2015), 2329-2350
MSC (2010): Primary 65T40; Secondary 65D15
DOI: https://doi.org/10.1090/S0025-5718-2015-02948-2
Published electronically: February 19, 2015
MathSciNet review: 3356028
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we provide a reconstruction algorithm for piecewise-smooth functions with a priori known smoothness and a number of discontinuities, from their Fourier coefficients, possessing the maximal possible asymptotic rate of convergence—including the positions of the discontinuities and the pointwise values of the function. This algorithm is a modification of our earlier method, which is in turn based on the algebraic method of K. Eckhoff proposed in the 1990s. The key ingredient of the new algorithm is to use a different set of Eckhoff’s equations for reconstructing the location of each discontinuity. Instead of consecutive Fourier samples, we propose to use a “decimated” set which is evenly spread throughout the spectrum.

References

Ben Adcock, Anders C. Hansen, and Alexei Shadrin, A stability barrier for reconstructions from Fourier samples, SIAM J. Numer. Anal. 52 (2014), no. 1, 125–139. MR 3151387, DOI https://doi.org/10.1137/130908221

J. R. Auton, Investigation of Procedures for Automatic Resonance Extraction from Noisy Transient Electromagnetics Data. Volume III, Translation of Prony’s Original Paper and Bibliography of Prony’s Method. Technical report, Effects Technology Inc., Santa Barbara, CA, 1981.

Nana S. Banerjee and James F. Geer, Exponentially accurate approximations to periodic Lipschitz functions based on Fourier series partial sums, J. Sci. Comput. 13 (1998), no. 4, 419–460. MR 1676752, DOI https://doi.org/10.1023/A%3A1023289301743

A. Barkhudaryan, R. Barkhudaryan, and A. Poghosyan, Asymptotic behavior of Eckhoff’s method for Fourier series convergence acceleration, Anal. Theory Appl. 23 (2007), no. 3, 228–242. MR 2350105, DOI https://doi.org/10.1007/s10496-007-0228-0

Riccardo March and Piero Barone, Reconstruction of a piecewise constant function from noisy Fourier coefficients by Padé method, SIAM J. Appl. Math. 60 (2000), no. 4, 1137–1156. MR 1760030, DOI https://doi.org/10.1137/S0036139998333841

D. Batenkov, Decimated generalized Prony systems, preprint, 2013.

D. Batenkov, V. Golubyatnikov, and Y. Yomdin, Reconstruction of planar domains from partial integral measurements, Complex analysis and dynamical systems V, Contemp. Math., vol. 591, Amer. Math. Soc., Providence, RI, 2013, pp. 51–66. MR 3155677, DOI https://doi.org/10.1090/conm/591/11826

D. Batenkov and Y. Yomdin, Geometry and singularities of the Prony mapping, Journal of Singularities 10 (2014), 1–25, Proceedings of 12th International Workshop on Real and Complex Singularities.

Dmitry Batenkov and Yosef Yomdin, Algebraic Fourier reconstruction of piecewise smooth functions, Math. Comp. 81 (2012), no. 277, 277–318. MR 2833496, DOI https://doi.org/10.1090/S0025-5718-2011-02539-1

Dmitry Batenkov and Yosef Yomdin, On the accuracy of solving confluent Prony systems, SIAM J. Appl. Math. 73 (2013), no. 1, 134–154. MR 3033143, DOI https://doi.org/10.1137/110836584

R. Bauer, Band filters for determining shock locations, PhD thesis, Department of Applied Mathematics, Brown University, Providence, RI, 1995.

Bernhard Beckermann, Ana C. Matos, and Franck Wielonsky, Reduction of the Gibbs phenomenon for smooth functions with jumps by the $\epsilon $-algorithm, J. Comput. Appl. Math. 219 (2008), no. 2, 329–349. MR 2441229, DOI https://doi.org/10.1016/j.cam.2007.11.011

John P. Boyd, Acceleration of algebraically-converging Fourier series when the coefficients have series in powers in $1/n$, J. Comput. Phys. 228 (2009), no. 5, 1404–1411. MR 2494223, DOI https://doi.org/10.1016/j.jcp.2008.10.039

C. Brezinski, Extrapolation algorithms for filtering series of functions, and treating the Gibbs phenomenon, Numer. Algorithms 36 (2004), no. 4, 309–329. MR 2108182, DOI https://doi.org/10.1007/s11075-004-2843-6

Emmanuel J. Candès and Carlos Fernandez-Granda, Towards a mathematical theory of super-resolution, Comm. Pure Appl. Math. 67 (2014), no. 6, 906–956. MR 3193963, DOI https://doi.org/10.1002/cpa.21455

Tobin A. Driscoll and Bengt Fornberg, A Padé-based algorithm for overcoming the Gibbs phenomenon, Numer. Algorithms 26 (2001), no. 1, 77–92. MR 1827318, DOI https://doi.org/10.1023/A%3A1016648530648

Knut S. Eckhoff, Accurate and efficient reconstruction of discontinuous functions from truncated series expansions, Math. Comp. 61 (1993), no. 204, 745–763. MR 1195430, DOI https://doi.org/10.1090/S0025-5718-1993-1195430-1

Knut S. Eckhoff, Accurate reconstructions of functions of finite regularity from truncated Fourier series expansions, Math. Comp. 64 (1995), no. 210, 671–690. MR 1265014, DOI https://doi.org/10.1090/S0025-5718-1995-1265014-7

Knut S. Eckhoff, On a high order numerical method for functions with singularities, Math. Comp. 67 (1998), no. 223, 1063–1087. MR 1459387, DOI https://doi.org/10.1090/S0025-5718-98-00949-1

Saber Elaydi, An introduction to difference equations, 3rd ed., Undergraduate Texts in Mathematics, Springer, New York, 2005. MR 2128146

Shlomo Engelberg and Eitan Tadmor, Recovery of edges from spectral data with noise—a new perspective, SIAM J. Numer. Anal. 46 (2008), no. 5, 2620–2635. MR 2421050, DOI https://doi.org/10.1137/070689899

Anne Gelb and Eitan Tadmor, Detection of edges in spectral data, Appl. Comput. Harmon. Anal. 7 (1999), no. 1, 101–135. MR 1699594, DOI https://doi.org/10.1006/acha.1999.0262

David Gottlieb and Chi-Wang Shu, On the Gibbs phenomenon and its resolution, SIAM Rev. 39 (1997), no. 4, 644–668. MR 1491051, DOI https://doi.org/10.1137/S0036144596301390

David Gottlieb and Steven A. Orszag, Numerical analysis of spectral methods: theory and applications, Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1977. CBMS-NSF Regional Conference Series in Applied Mathematics, No. 26. MR 0520152

Christian Guilpin, Jacques Gacougnolle, and Yvan Simon, The $\epsilon $-algorithm allows to detect Dirac delta functions, Appl. Numer. Math. 48 (2004), no. 1, 27–40. MR 2027820, DOI https://doi.org/10.1016/S0168-9274%2803%2900104-1

Tomasz Hrycak and Karlheinz Gröchenig, Pseudospectral Fourier reconstruction with the modified inverse polynomial reconstruction method, J. Comput. Phys. 229 (2010), no. 3, 933–946. MR 2566372, DOI https://doi.org/10.1016/j.jcp.2009.10.026

L. V. Kantorovich and V. I. Krylov, Approximate methods of higher analysis, Interscience Publishers, Inc., New York; P. Noordhoff Ltd., Groningen, 1958. Translated from the 3rd Russian edition by C. D. Benster. MR 0106537

George Kvernadze, Approximating the jump discontinuities of a function by its Fourier-Jacobi coefficients, Math. Comp. 73 (2004), no. 246, 731–751. MR 2031403, DOI https://doi.org/10.1090/S0025-5718-03-01594-1

George Kvernadze, Approximation of the discontinuities of a function by its classical orthogonal polynomial Fourier coefficients, Math. Comp. 79 (2010), no. 272, 2265–2285. MR 2684364, DOI https://doi.org/10.1090/S0025-5718-10-02366-5

H. N. Mhaskar and J. Prestin, Polynomial frames for the detection of singularities, Wavelet analysis and multiresolution methods (Urbana-Champaign, IL, 1999) Lecture Notes in Pure and Appl. Math., vol. 212, Dekker, New York, 2000, pp. 273–298. MR 1777997

Arnak Poghosyan, Asymptotic behavior of the Eckhoff method for convergence acceleration of trigonometric interpolation, Anal. Theory Appl. 26 (2010), no. 3, 236–260. MR 2728116, DOI https://doi.org/10.1007/s10496-010-0236-3

Arnak Poghosyan, On an auto-correction phenomenon of the Krylov-Gottlieb-Eckhoff method, IMA J. Numer. Anal. 31 (2011), no. 2, 512–527. MR 2813182, DOI https://doi.org/10.1093/imanum/drp043

R. Prony, Essai experimental et analytique, J. Ecole Polytech. (Paris), no. 2, 24–76, 1795.

B. D. Rao and K. S. Arun, Model based processing of signals: A state space approach, Proceedings of the IEEE 80 (1992), no. 2, 283–309.

Bernie D. Shizgal and Jae-Hun Jung, Towards the resolution of the Gibbs phenomena, J. Comput. Appl. Math. 161 (2003), no. 1, 41–65. MR 2018574, DOI https://doi.org/10.1016/S0377-0427%2803%2900500-4

Alex Solomonoff, Reconstruction of a discontinuous function from a few Fourier coefficients using Bayesian estimation, J. Sci. Comput. 10 (1995), no. 1, 29–80. MR 1337448, DOI https://doi.org/10.1007/BF02087960

Eitan Tadmor, Filters, mollifiers and the computation of the Gibbs phenomenon, Acta Numer. 16 (2007), 305–378. MR 2417931, DOI https://doi.org/10.1017/S0962492906320016

Musheng Wei, Ana Gabriela Martínez, and Alvaro R. De Pierro, Detection of edges from spectral data: new results, Appl. Comput. Harmon. Anal. 22 (2007), no. 3, 386–393. MR 2311863, DOI https://doi.org/10.1016/j.acha.2006.10.002

Y. Yomdin, Singularities in algebraic data acquisition, Real and complex singularities, London Math. Soc. Lecture Note Ser., vol. 380, Cambridge Univ. Press, Cambridge, 2010, pp. 378–396. MR 2759050

A. Zygmund, Trigonometric series: Vols. I, II, Cambridge University Press, London-New York, 1968. Second edition, reprinted with corrections and some additions. MR 0236587