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.
- 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
Retrieve articles in Mathematics of Computation with MSC (2010): 65T40, 65D15
Retrieve articles in all journals with MSC (2010): 65T40, 65D15
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
Keywords:
Fourier inversion,
nonlinear approximation,
piecewise-smooth functions,
Eckhoff’s conjecture,
Eckhoff’s method,
Gibbs phenomenon
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.
Article copyright:
© Copyright 2015
American Mathematical Society