{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T07:49:41Z","timestamp":1776844181537,"version":"3.51.2"},"reference-count":46,"publisher":"American Mathematical Society (AMS)","issue":"277","license":[{"start":{"date-parts":[[2012,8,30]],"date-time":"2012-08-30T00:00:00Z","timestamp":1346284800000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

Accurate reconstruction of piecewise smooth functions from a finite number of Fourier coefficients is an important problem in various applications. This problem exhibits an inherent inaccuracy, in particular, the Gibbs phenomenon, and it has been intensively investigated during the last few decades. Several nonlinear reconstruction methods have been proposed in the literature, and it is by now well-established that the \u201cclassical\u201d convergence order can be completely restored up to the discontinuities. Still, the maximal accuracy of determining the positions of these discontinuities remains an open question.<\/p>\n

\n In this paper we prove that the locations of the jumps (and subsequently the pointwise values of the function) can be reconstructed with at least \u201chalf the classical accuracy\u201d. In particular, we develop a constructive approximation procedure which, given the first\n \n \n \n k<\/mml:mi>\n k<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n Fourier coefficients of a piecewise\n \n \n \n \n C<\/mml:mi>\n \n 2<\/mml:mn>\n d<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n C^{2d+1}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n function, recovers the locations of the jumps with accuracy\n \n \n \n \n \n \u223c\n \n <\/mml:mo>\n \n k<\/mml:mi>\n \n \n \u2212\n \n <\/mml:mo>\n \n (<\/mml:mo>\n d<\/mml:mi>\n +<\/mml:mo>\n 2<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n \\sim k^{-\\left (d+2\\right )}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , and the values of the function between the jumps with accuracy\n \n \n \n \n \n \u223c\n \n <\/mml:mo>\n \n k<\/mml:mi>\n \n \n \u2212\n \n <\/mml:mo>\n \n (<\/mml:mo>\n d<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n \\sim k^{-\\left (d+1\\right )}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n (similar estimates are obtained for the associated jump magnitudes). A key ingredient of the algorithm is to start with the case of a single discontinuity, where a modified version of one of the existing algebraic methods (due to K.\u00a0Eckhoff) may be applied. It turns out that the additional orders of smoothness produce highly correlated error terms in the Fourier coefficients, which eventually cancel out in the corresponding algebraic equations. To handle more than one jump, we apply a localization procedure via a convolution in the Fourier domain, which eventually preserves the accuracy estimates obtained for the single jump. We provide some numerical results which support the theoretical predictions.\n <\/p>","DOI":"10.1090\/s0025-5718-2011-02539-1","type":"journal-article","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T15:07:34Z","timestamp":1314716854000},"page":"277-318","source":"Crossref","is-referenced-by-count":33,"title":["Algebraic Fourier reconstruction of piecewise smooth functions"],"prefix":"10.1090","volume":"81","author":[{"given":"Dmitry","family":"Batenkov","sequence":"first","affiliation":[]},{"given":"Yosef","family":"Yomdin","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2011,8,30]]},"reference":[{"key":"1","series-title":"National Bureau of Standards Applied Mathematics Series, No. 55","volume-title":"Handbook of mathematical functions with formulas, graphs, and mathematical tables","author":"Abramowitz, Milton","year":"1964"},{"issue":"1","key":"2","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1137\/S0036142903426245","article-title":"Interpolation and approximation of piecewise smooth functions","volume":"43","author":"Arandiga, Francesc","year":"2005","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"issue":"4","key":"3","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1023\/A:1023289301743","article-title":"Exponentially accurate approximations to periodic Lipschitz functions based on Fourier series partial sums","volume":"13","author":"Banerjee, Nana S.","year":"1998","journal-title":"J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0885-7474","issn-type":"print"},{"issue":"3","key":"4","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/s10496-007-0228-0","article-title":"Asymptotic behavior of Eckhoff\u2019s method for Fourier series convergence acceleration","volume":"23","author":"Barkhudaryan, A.","year":"2007","journal-title":"Anal. Theory Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/1672-4070","issn-type":"print"},{"issue":"4","key":"5","doi-asserted-by":"publisher","first-page":"1137","DOI":"10.1137\/S0036139998333841","article-title":"Reconstruction of a piecewise constant function from noisy Fourier coefficients by Pad\u00e9 method","volume":"60","author":"March, Riccardo","year":"2000","journal-title":"SIAM J. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1399","issn-type":"print"},{"issue":"10","key":"6","doi-asserted-by":"publisher","first-page":"105001","DOI":"10.1088\/0266-5611\/25\/10\/105001","article-title":"Moment inversion problem for piecewise \ud835\udc37-finite functions","volume":"25","author":"Batenkov, Dmitry","year":"2009","journal-title":"Inverse Problems","ISSN":"https:\/\/id.crossref.org\/issn\/0266-5611","issn-type":"print"},{"key":"7","unstructured":"D. Batenkov, N. Sarig, and Y. Yomdin. An \u201calgebraic\u201d reconstruction of piecewise-smooth functions from integral measurements. Proc. of Sampling Theory and Applications (SAMPTA), 2009."},{"key":"8","unstructured":"R. Bauer. Band filters for determining shock locations. PhD thesis, Department of Applied Mathematics, Brown University, Providence, RI, 1995."},{"issue":"2","key":"9","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/j.cam.2007.11.011","article-title":"Reduction of the Gibbs phenomenon for smooth functions with jumps by the \ud835\udf00-algorithm","volume":"219","author":"Beckermann, Bernhard","year":"2008","journal-title":"J. Comput. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0377-0427","issn-type":"print"},{"issue":"5","key":"10","doi-asserted-by":"publisher","first-page":"1404","DOI":"10.1016\/j.jcp.2008.10.039","article-title":"Acceleration of algebraically-converging Fourier series when the coefficients have series in powers in 1\/\ud835\udc5b","volume":"228","author":"Boyd, John P.","year":"2009","journal-title":"J. Comput. Phys.","ISSN":"https:\/\/id.crossref.org\/issn\/0021-9991","issn-type":"print"},{"issue":"4","key":"11","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/s11075-004-2843-6","article-title":"Extrapolation algorithms for filtering series of functions, and treating the Gibbs phenomenon","volume":"36","author":"Brezinski, C.","year":"2004","journal-title":"Numer. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/1017-1398","issn-type":"print"},{"issue":"5","key":"12","doi-asserted-by":"publisher","first-page":"1741","DOI":"10.1109\/TSP.2006.890907","article-title":"Sampling moments and reconstructing signals of finite rate of innovation: Shannon meets Strang-Fix","volume":"55","author":"Dragotti, Pier Luigi","year":"2007","journal-title":"IEEE Trans. Signal Process.","ISSN":"https:\/\/id.crossref.org\/issn\/1053-587X","issn-type":"print"},{"issue":"1","key":"13","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1023\/A:1016648530648","article-title":"A Pad\u00e9-based algorithm for overcoming the Gibbs phenomenon","volume":"26","author":"Driscoll, Tobin A.","year":"2001","journal-title":"Numer. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/1017-1398","issn-type":"print"},{"issue":"204","key":"14","doi-asserted-by":"publisher","first-page":"745","DOI":"10.2307\/2153251","article-title":"Accurate and efficient reconstruction of discontinuous functions from truncated series expansions","volume":"61","author":"Eckhoff, Knut S.","year":"1993","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"210","key":"15","doi-asserted-by":"publisher","first-page":"671","DOI":"10.2307\/2153445","article-title":"Accurate reconstructions of functions of finite regularity from truncated Fourier series expansions","volume":"64","author":"Eckhoff, Knut S.","year":"1995","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"223","key":"16","doi-asserted-by":"publisher","first-page":"1063","DOI":"10.1090\/S0025-5718-98-00949-1","article-title":"On a high order numerical method for functions with singularities","volume":"67","author":"Eckhoff, Knut S.","year":"1998","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"17","series-title":"Undergraduate Texts in Mathematics","isbn-type":"print","volume-title":"An introduction to difference equations","author":"Elaydi, Saber","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/0387230599","edition":"3"},{"issue":"5","key":"18","doi-asserted-by":"publisher","first-page":"2620","DOI":"10.1137\/070689899","article-title":"Recovery of edges from spectral data with noise\u2014a new perspective","volume":"46","author":"Engelberg, Shlomo","year":"2008","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"issue":"2","key":"19","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/s12220-008-9016-0","article-title":"Linear versus non-linear acquisition of step-functions","volume":"18","author":"Ettinger, B.","year":"2008","journal-title":"J. Geom. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/1050-6926","issn-type":"print"},{"key":"20","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1137\/0712035","article-title":"A note on fill for sparse matrices","volume":"12","author":"George, Alan","year":"1975","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"issue":"2-4","key":"21","first-page":"326","article-title":"Segmentation of images from Fourier spectral data","volume":"5","author":"Gelb, Anne","year":"2009","journal-title":"Commun. Comput. Phys.","ISSN":"https:\/\/id.crossref.org\/issn\/1815-2406","issn-type":"print"},{"issue":"1","key":"22","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1006\/acha.1999.0262","article-title":"Detection of edges in spectral data","volume":"7","author":"Gelb, Anne","year":"1999","journal-title":"Appl. Comput. Harmon. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/1063-5203","issn-type":"print"},{"issue":"4","key":"23","doi-asserted-by":"publisher","first-page":"1222","DOI":"10.1137\/S1064827597328315","article-title":"A stable numerical method for inverting shape from moments","volume":"21","author":"Golub, Gene H.","year":"1999","journal-title":"SIAM J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"issue":"4","key":"24","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1137\/S0036144596301390","article-title":"On the Gibbs phenomenon and its resolution","volume":"39","author":"Gottlieb, David","year":"1997","journal-title":"SIAM Rev.","ISSN":"https:\/\/id.crossref.org\/issn\/1095-7200","issn-type":"print"},{"issue":"1","key":"25","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/S0168-9274(03)00104-1","article-title":"The \ud835\udf00-algorithm allows to detect Dirac delta functions","volume":"48","author":"Guilpin, Christian","year":"2004","journal-title":"Appl. Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0168-9274","issn-type":"print"},{"issue":"4","key":"26","doi-asserted-by":"publisher","first-page":"1053","DOI":"10.1088\/0266-5611\/16\/4\/312","article-title":"Reconstructing planar domains from their moments","volume":"16","author":"Gustafsson, Bj\u00f6rn","year":"2000","journal-title":"Inverse Problems","ISSN":"https:\/\/id.crossref.org\/issn\/0266-5611","issn-type":"print"},{"issue":"3","key":"27","doi-asserted-by":"publisher","first-page":"933","DOI":"10.1016\/j.jcp.2009.10.026","article-title":"Pseudospectral Fourier reconstruction with the modified inverse polynomial reconstruction method","volume":"229","author":"Hrycak, Tomasz","year":"2010","journal-title":"J. Comput. Phys.","ISSN":"https:\/\/id.crossref.org\/issn\/0021-9991","issn-type":"print"},{"key":"28","volume-title":"{\\cyr Priblizhennye metody vysshego analiza}","author":"Kantorovi\u010d, L. V.","year":"1962"},{"issue":"246","key":"29","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1090\/S0025-5718-03-01594-1","article-title":"Approximating the jump discontinuities of a function by its Fourier-Jacobi coefficients","volume":"73","author":"Kvernadze, George","year":"2004","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"272","key":"30","doi-asserted-by":"publisher","first-page":"2265","DOI":"10.1090\/S0025-5718-10-02366-5","article-title":"Approximation of the discontinuities of a function by its classical orthogonal polynomial Fourier coefficients","volume":"79","author":"Kvernadze, George","year":"2010","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"4","key":"31","doi-asserted-by":"publisher","first-page":"1159","DOI":"10.1093\/imanum\/drn087","article-title":"Approximating piecewise-smooth functions","volume":"30","author":"Lipman, Yaron","year":"2010","journal-title":"IMA J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0272-4979","issn-type":"print"},{"issue":"1","key":"32","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1023\/B:RAMA.0000027196.19661.b7","article-title":"The Sylvester-Ramanujan system of equations and the complex power moment problem","volume":"8","author":"Lyubich, Yuri I.","year":"2004","journal-title":"Ramanujan J.","ISSN":"https:\/\/id.crossref.org\/issn\/1382-4090","issn-type":"print"},{"key":"33","isbn-type":"print","first-page":"273","article-title":"Polynomial frames for the detection of singularities","author":"Mhaskar, H. N.","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/0824704177"},{"key":"34","unstructured":"I.P. Natanson. Constructive Function Theory (in Russian). Gostekhizdat, 1949."},{"issue":"2","key":"35","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s11784-009-0121-x","article-title":"The power of adaptive algorithms for functions with singularities","volume":"6","author":"Plaskota, Leszek","year":"2009","journal-title":"J. Fixed Point Theory Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/1661-7738","issn-type":"print"},{"key":"36","unstructured":"R. Prony. Essai experimental et analytique. J. Ec. Polytech.(Paris), 2:24\u201376, 1795."},{"issue":"4","key":"37","first-page":"97","article-title":"Signal acquisition from measurements via non-linear models","volume":"29","author":"Sarig, N.","year":"2007","journal-title":"C. R. Math. Acad. Sci. Soc. R. Can.","ISSN":"https:\/\/id.crossref.org\/issn\/0706-1994","issn-type":"print"},{"issue":"1","key":"38","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0377-0427(03)00500-4","article-title":"Towards the resolution of the Gibbs phenomena","volume":"161","author":"Shizgal, Bernie D.","year":"2003","journal-title":"J. Comput. Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0377-0427","issn-type":"print"},{"issue":"1","key":"39","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/BF02087960","article-title":"Reconstruction of a discontinuous function from a few Fourier coefficients using Bayesian estimation","volume":"10","author":"Solomonoff, Alex","year":"1995","journal-title":"J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0885-7474","issn-type":"print"},{"key":"40","series-title":"American Mathematical Society Colloquium Publications, Vol. XXIII","volume-title":"Orthogonal polynomials","author":"Szeg\u0151, G\u00e1bor","year":"1975","edition":"4"},{"key":"41","isbn-type":"print","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1017\/S0962492906320016","article-title":"Filters, mollifiers and the computation of the Gibbs phenomenon","volume":"16","author":"Tadmor, Eitan","year":"2007","ISBN":"https:\/\/id.crossref.org\/isbn\/9780521877435","journal-title":"Acta Numer.","ISSN":"https:\/\/id.crossref.org\/issn\/0962-4929","issn-type":"print"},{"issue":"6","key":"42","doi-asserted-by":"publisher","first-page":"1417","DOI":"10.1109\/TSP.2002.1003065","article-title":"Sampling signals with finite rate of innovation","volume":"50","author":"Vetterli, Martin","year":"2002","journal-title":"IEEE Trans. Signal Process.","ISSN":"https:\/\/id.crossref.org\/issn\/1053-587X","issn-type":"print"},{"key":"43","unstructured":"J. Vindas. Local Behavior of Distributions and Applications. PhD thesis, 2009."},{"issue":"3","key":"44","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1016\/j.acha.2006.10.002","article-title":"Detection of edges from spectral data: new results","volume":"22","author":"Wei, Musheng","year":"2007","journal-title":"Appl. Comput. Harmon. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/1063-5203","issn-type":"print"},{"key":"45","isbn-type":"print","volume-title":"Rounding errors in algebraic processes","author":"Wilkinson, J. H.","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0486679993"},{"key":"46","volume-title":"Trigonometric series: Vols. I, II","author":"Zygmund, A.","year":"1968"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2012-81-277\/S0025-5718-2011-02539-1\/S0025-5718-2011-02539-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2012-81-277\/S0025-5718-2011-02539-1\/S0025-5718-2011-02539-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T17:02:38Z","timestamp":1776790958000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2012-81-277\/S0025-5718-2011-02539-1\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,8,30]]},"references-count":46,"journal-issue":{"issue":"277","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["S0025-5718-2011-02539-1"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-2011-02539-1","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2011,8,30]]}}}