## Complete algebraic reconstruction of piecewise-smooth functions from Fourier data

HTML articles powered by AMS MathViewer

- by Dmitry Batenkov PDF
- Math. Comp.
**84**(2015), 2329-2350 Request permission

## 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 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 10.1023/A:1023289301743 - 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 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 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 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 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 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 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 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 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 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 10.1023/A:1016648530648 - 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 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 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 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 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 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 10.1137/S0036144596301390 - David Gottlieb and Steven A. Orszag,
*Numerical analysis of spectral methods: theory and applications*, CBMS-NSF Regional Conference Series in Applied Mathematics, No. 26, Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1977. 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 10.1016/S0168-9274(03)00104-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 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 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 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 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 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 10.1016/S0377-0427(03)00500-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 10.1007/BF02087960 - Eitan Tadmor,
*Filters, mollifiers and the computation of the Gibbs phenomenon*, Acta Numer.**16**(2007), 305–378. MR**2417931**, DOI 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 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**

## Additional Information

**Dmitry Batenkov**- Affiliation: Department of Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel
- Address at time of publication: Department of Computer Science, Technion – Israel Institute of Technology, Technion City, Haifa 32000, Israel
- MR Author ID: 881951
- ORCID: setImmediate$0.09410305223452953$7
- Email: batenkov@cs.technion.ac.il
- Received by editor(s): December 2, 2012
- Received by editor(s) in revised form: November 30, 2013
- Published electronically: February 19, 2015
- Additional Notes: This research has been supported by the Adams Fellowship Program of the Israel Academy of Sciences and Humanities.
- © Copyright 2015 American Mathematical Society
- Journal: Math. Comp.
**84**(2015), 2329-2350 - MSC (2010): Primary 65T40; Secondary 65D15
- DOI: https://doi.org/10.1090/S0025-5718-2015-02948-2
- MathSciNet review: 3356028