{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T00:56:08Z","timestamp":1775696168657,"version":"3.50.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,7,9]],"date-time":"2025-07-09T00:00:00Z","timestamp":1752019200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,7,9]],"date-time":"2025-07-09T00:00:00Z","timestamp":1752019200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004721","name":"The University of Tokyo","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004721","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Numer. Math."],"published-print":{"date-parts":[[2025,8]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Approximating a univariate function on the interval <jats:inline-formula>\n              <jats:tex-math>$$[-1,1]$$<\/jats:tex-math>\n            <\/jats:inline-formula> with a polynomial is among the most classical problems in numerical analysis. When the function evaluations come with noise, a least-squares fit is known to reduce the effect of noise as more samples are taken. The generic algorithm for the least-squares problem requires <jats:inline-formula>\n              <jats:tex-math>$$O(Nn^2)$$<\/jats:tex-math>\n            <\/jats:inline-formula> operations, where <jats:inline-formula>\n              <jats:tex-math>$$N+1$$<\/jats:tex-math>\n            <\/jats:inline-formula> is the number of sample points and <jats:italic>n<\/jats:italic> is the degree of the polynomial approximant. This algorithm is unstable when <jats:italic>n<\/jats:italic> is large, for example <jats:inline-formula>\n              <jats:tex-math>$$n\\gg \\sqrt{N}$$<\/jats:tex-math>\n            <\/jats:inline-formula> for equispaced sample points. In this study, we blend numerical analysis and statistics to introduce a stable and fast <jats:inline-formula>\n              <jats:tex-math>$$O(N\\log N)$$<\/jats:tex-math>\n            <\/jats:inline-formula> algorithm called NoisyChebtrunc based on Chebyshev interpolation. It has the same error reduction effect as least-squares and the convergence is spectral until the error reaches <jats:inline-formula>\n              <jats:tex-math>$$O(\\sigma \\sqrt{{n}\/{N}})$$<\/jats:tex-math>\n            <\/jats:inline-formula>, where <jats:inline-formula>\n              <jats:tex-math>$$\\sigma$$<\/jats:tex-math>\n            <\/jats:inline-formula> is the noise level, after which the error continues to decrease at the Monte-Carlo <jats:inline-formula>\n              <jats:tex-math>$$O(1\/\\sqrt{N})$$<\/jats:tex-math>\n            <\/jats:inline-formula> rate. To determine the polynomial degree, NoisyChebtrunc employs a statistical criterion, namely Mallows\u2019 <jats:inline-formula>\n              <jats:tex-math>$$C_p$$<\/jats:tex-math>\n            <\/jats:inline-formula>. We analyze NoisyChebtrunc in terms of the variance and concentration in the infinity norm to the underlying noiseless function. These results show that with high probability the infinity-norm error is bounded by a small constant times <jats:inline-formula>\n              <jats:tex-math>$$\\sigma \\sqrt{{n}\/{N}}$$<\/jats:tex-math>\n            <\/jats:inline-formula>, when the noise is independent and follows a subgaussian or subexponential distribution. We illustrate the performance of NoisyChebtrunc with numerical experiments.<\/jats:p>","DOI":"10.1007\/s00211-025-01485-4","type":"journal-article","created":{"date-parts":[[2025,7,10]],"date-time":"2025-07-10T09:25:18Z","timestamp":1752139518000},"page":"1285-1311","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Polynomial approximation of noisy functions"],"prefix":"10.1007","volume":"157","author":[{"given":"Takeru","family":"Matsuda","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuji","family":"Nakatsukasa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,7,9]]},"reference":[{"key":"1485_CR1","unstructured":"Adcock, B.: Optimal sampling for least-squares approximation. arXiv preprint arXiv:2409.02342 (2024)"},{"issue":"3","key":"1485_CR2","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1137\/17M1114697","volume":"61","author":"B Adcock","year":"2019","unstructured":"Adcock, B., Huybrechs, D.: Frames and numerical approximation. SIAM Rev. 61(3), 443\u2013473 (2019)","journal-title":"SIAM Rev."},{"key":"1485_CR3","doi-asserted-by":"crossref","unstructured":"Adcock, B., Huybrechs, D.: Approximating smooth, multivariate functions on irregular domains. In: Forum of Mathematics, Sigma, Cambridge University Press,\u00a0vol. 8, p. 26 (2020)","DOI":"10.1017\/fms.2020.23"},{"key":"1485_CR4","doi-asserted-by":"crossref","unstructured":"Akaike, H.: Information theory and an extension of the maximum likelihood principle. In: Selected Papers of Hirotugu Akaike, pp. 199\u2013213. Springer, New York (1998)","DOI":"10.1007\/978-1-4612-1694-0_15"},{"issue":"4","key":"1485_CR5","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/2998442","volume":"43","author":"JL Aurentz","year":"2017","unstructured":"Aurentz, J.L., Trefethen, L.N.: Chopping a Chebyshev series. ACM Trans. Math. Soft. 43(4), 33 (2017)","journal-title":"ACM Trans. Math. Soft."},{"issue":"2","key":"1485_CR6","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/j.jeconom.2015.02.014","volume":"186","author":"A Belloni","year":"2015","unstructured":"Belloni, A., Chernozhukov, V., Chetverikov, D., Kato, K.: Some new asymptotic theory for least squares series: Pointwise and uniform results. Journal of Econometrics 186(2), 345\u2013366 (2015)","journal-title":"Journal of Econometrics"},{"key":"1485_CR7","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1017\/S0962492904000182","volume":"13","author":"H-J Bungartz","year":"2004","unstructured":"Bungartz, H.-J., Griebel, M.: Sparse grids. Acta Numer. 13, 147\u2013269 (2004)","journal-title":"Acta Numer."},{"key":"1485_CR8","volume-title":"Pattern Recognition and Machine Learning","author":"CM Bishop","year":"2006","unstructured":"Bishop, C.M., Nasrabadi, N.M.: Pattern Recognition and Machine Learning. Springer, New York (2006)"},{"issue":"5","key":"1485_CR9","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1007\/s10208-013-9142-3","volume":"13","author":"A Cohen","year":"2013","unstructured":"Cohen, A., Davenport, M.A., Leviatan, D.: On the stability and accuracy of least squares approximations. Found. Comput. Math. 13(5), 819\u2013834 (2013)","journal-title":"Found. Comput. Math."},{"key":"1485_CR10","doi-asserted-by":"publisher","first-page":"181","DOI":"10.5802\/smai-jcm.24","volume":"3","author":"A Cohen","year":"2017","unstructured":"Cohen, A., Migliorati, G.: Optimal weighted least-squares methods. SMAI-J. Comput. Math. 3, 181\u2013203 (2017)","journal-title":"SMAI-J. Comput. Math."},{"key":"1485_CR11","volume-title":"Numerical Methods in Scientific Computing","author":"G Dahlquist","year":"2008","unstructured":"Dahlquist, G., Bj\u00f6rck, \u00c5.: Numerical Methods in Scientific Computing, vol. I. SIAM, Philadelphia (2008)"},{"key":"1485_CR12","volume-title":"Chebfun Guide","author":"TA Driscoll","year":"2014","unstructured":"Driscoll, T.A., Hale, N., Trefethen, L.N.: Chebfun Guide. Pafnuty Publications, Oxford (2014)"},{"key":"1485_CR13","doi-asserted-by":"publisher","DOI":"10.1002\/9781118625590","volume-title":"Applied Regression Analysis","author":"NR Draper","year":"1998","unstructured":"Draper, N.R., Smith, H.: Applied Regression Analysis. John Wiley & Sons, New York (1998)"},{"issue":"1","key":"1485_CR14","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1080\/00207728908910103","volume":"20","author":"S Fioretti","year":"1989","unstructured":"Fioretti, S., Jetto, L.: Accurate derivative estimation from noisy data: a state-space approach. Int. J. Syst. Sci 20(1), 33\u201353 (1989)","journal-title":"Int. J. Syst. Sci"},{"key":"1485_CR15","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1016\/j.jmva.2013.09.006","volume":"123","author":"Y Fujikoshi","year":"2014","unstructured":"Fujikoshi, Y., Sakurai, T., Yanagihara, H.: Consistency of high-dimensional aic-type and cp-type criteria in multivariate linear regression. J. Multivar. Anal. 123, 184\u2013200 (2014)","journal-title":"J. Multivar. Anal."},{"key":"1485_CR16","doi-asserted-by":"publisher","DOI":"10.1201\/b18401","volume-title":"Statistical Learning with Sparsity","author":"T Hastie","year":"2015","unstructured":"Hastie, T., Tibshirani, R., Wainwright, M.: Statistical Learning with Sparsity. CRC Press, New York (2015)"},{"key":"1485_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-7138-7","volume-title":"An Introduction to Statistical Learning","author":"G James","year":"2013","unstructured":"James, G., Witten, D., Hastie, T., Tibshirani, R.: An Introduction to Statistical Learning. Springer, New York (2013)"},{"key":"1485_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-71887-3","volume-title":"Information Criteria and Statistical Modeling","author":"S Konishi","year":"2008","unstructured":"Konishi, S., Kitagawa, G.: Information Criteria and Statistical Modeling. Springer, New York (2008)"},{"issue":"4","key":"1485_CR19","first-page":"661","volume":"15","author":"CL Mallows","year":"1973","unstructured":"Mallows, C.L.: Some comments on Cp. Technometrics 15(4), 661\u2013675 (1973)","journal-title":"Technometrics"},{"issue":"3","key":"1485_CR20","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s100970100031","volume":"3","author":"P Massart","year":"2001","unstructured":"Massart, P., Birg\u00e9, L.: Gaussian model selection. J. Eur. Math. Soc. 3(3), 203\u2013268 (2001)","journal-title":"J. Eur. Math. Soc."},{"key":"1485_CR21","volume-title":"Chebyshev Polynomials","author":"JC Mason","year":"2010","unstructured":"Mason, J.C., Handscomb, D.C.: Chebyshev Polynomials. CRC Press, Boca Raton (2010)"},{"key":"1485_CR22","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.jmva.2015.08.009","volume":"142","author":"G Migliorati","year":"2015","unstructured":"Migliorati, G., Nobile, F., Tempone, R.: Convergence estimates in probability and in expectation for discrete least squares with noisy evaluations at random points. J. Multivar. Anal. 142, 167\u2013182 (2015)","journal-title":"J. Multivar. Anal."},{"key":"1485_CR23","unstructured":"Nakatsukasa, Y.: Approximate and integrate: Variance reduction in Monte Carlo integration via function approximation. arXiv:1806.05492 (2018)"},{"issue":"1","key":"1485_CR24","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0021-9045(86)90016-X","volume":"48","author":"P Nevai","year":"1986","unstructured":"Nevai, P.: G\u00e9za Freud, orthogonal polynomials and Christoffel functions. A case study. J. Approx. Theory 48(1), 3\u2013167 (1986)","journal-title":"A case study. J. Approx. Theory"},{"issue":"3","key":"1485_CR25","doi-asserted-by":"publisher","first-page":"1494","DOI":"10.1137\/16M1106122","volume":"40","author":"Y Nakatsukasa","year":"2018","unstructured":"Nakatsukasa, Y., S\u00e8te, O., Trefethen, L.N.: The AAA algorithm for rational approximation. SIAM J. Sci. Comp. 40(3), 1494\u20131522 (2018)","journal-title":"SIAM J. Sci. Comp."},{"key":"1485_CR26","first-page":"1298","volume":"12","author":"S Portnoy","year":"1984","unstructured":"Portnoy, S.: Asymptotic behavior of m-estimators of p regression parameters when $$p^2\/n$$ is large. i. consistency. Ann. Stat. 12, 1298\u20131309 (1984)","journal-title":"i. consistency. Ann. Stat."},{"issue":"1","key":"1485_CR27","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/355984.355989","volume":"8","author":"CC Paige","year":"1982","unstructured":"Paige, C.C., Saunders, M.A.: LSQR: An algorithm for sparse linear equations and sparse least squares. ACM Trans. Math. Soft. 8(1), 43\u201371 (1982)","journal-title":"ACM Trans. Math. Soft."},{"issue":"4","key":"1485_CR28","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/0021-9045(83)90042-4","volume":"37","author":"DL Ragozin","year":"1983","unstructured":"Ragozin, D.L.: Error bounds for derivative estimates based on spline smoothing of exact or noisy data. J. Approx. Theory 37(4), 335\u2013355 (1983)","journal-title":"J. Approx. Theory"},{"issue":"4","key":"1485_CR29","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1109\/MSP.2011.941097","volume":"28","author":"RW Schafer","year":"2011","unstructured":"Schafer, R.W.: What is a Savitzky-Golay filter? [lecture notes]. IEEE Signal processing magazine 28(4), 111\u2013117 (2011)","journal-title":"IEEE Signal processing magazine"},{"issue":"3","key":"1485_CR30","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/s10444-024-10140-9","volume":"50","author":"C Str\u00f6ssner","year":"2024","unstructured":"Str\u00f6ssner, C., Sun, B., Kressner, D.: Approximation in the extended functional tensor train format. Adv. in Comput. Math. 50(3), 54 (2024)","journal-title":"Adv. in Comput. Math."},{"issue":"1","key":"1485_CR31","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/S0036144598336745","volume":"41","author":"G Strang","year":"1999","unstructured":"Strang, G.: The discrete cosine transform. SIAM Rev. 41(1), 135\u2013147 (1999)","journal-title":"SIAM Rev."},{"key":"1485_CR32","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719598","volume-title":"Spectral Methods in MATLAB","author":"LN Trefethen","year":"2000","unstructured":"Trefethen, L.N.: Spectral Methods in MATLAB. SIAM, Philadelphia (2000)"},{"key":"1485_CR33","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975949","volume-title":"Approximation Theory and Approximation Practice","author":"LN Trefethen","year":"2019","unstructured":"Trefethen, L.N.: Approximation Theory and Approximation Practice, Extended SIAM, Philadelphia (2019)","edition":"Extended"},{"key":"1485_CR34","doi-asserted-by":"publisher","DOI":"10.1007\/b13794","volume-title":"Introduction to Nonparametric Estimation","author":"AB Tsybakov","year":"2009","unstructured":"Tsybakov, A.B.: Introduction to Nonparametric Estimation. Springer, New York (2009)"},{"issue":"6","key":"1485_CR35","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1137\/130908002","volume":"35","author":"A Townsend","year":"2013","unstructured":"Townsend, A., Trefethen, L.N.: An extension of Chebfun to two dimensions. SIAM J. Sci. Comp. 35(6), 495\u2013518 (2013)","journal-title":"SIAM J. Sci. Comp."},{"key":"1485_CR36","doi-asserted-by":"publisher","DOI":"10.1017\/9781108231596","volume-title":"High-dimensional Probability: An Introduction with Applications in Data Science","author":"R Vershynin","year":"2018","unstructured":"Vershynin, R.: High-dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, Cambridge (2018)"},{"key":"1485_CR37","doi-asserted-by":"publisher","DOI":"10.1017\/9781108627771","volume-title":"High-Dimensional Statistics: A Non-Asymptotic Viewpoint","author":"MJ Wainwright","year":"2019","unstructured":"Wainwright, M.J.: High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, Cambridge (2019)"},{"key":"1485_CR38","volume-title":"All of Nonparametric Statistics","author":"L Wasserman","year":"2006","unstructured":"Wasserman, L.: All of Nonparametric Statistics. Springer, New York (2006)"},{"key":"1485_CR39","volume-title":"All of Statistics: a Concise Course in Statistical Inference","author":"L Wasserman","year":"2013","unstructured":"Wasserman, L.: All of Statistics: a Concise Course in Statistical Inference. Springer, New York (2013)"},{"issue":"3","key":"1485_CR40","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1137\/21M1420277","volume":"44","author":"H Wilber","year":"2022","unstructured":"Wilber, H., Damle, A., Townsend, A.: Data-driven algorithms for signal processing with trigonometric rational functions. SIAM J. Sci. Comp. 44(3), 185\u2013209 (2022)","journal-title":"SIAM J. Sci. Comp."},{"key":"1485_CR41","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1214\/aos\/1176344610","volume":"7","author":"VJ Yohai","year":"1979","unstructured":"Yohai, V.J., Maronna, R.A.: Asymptotic behavior of m-estimators for the linear model.\u00a0Ann. Stat. 7, 258\u2013268 (1979)","journal-title":"Ann. Stat."},{"issue":"5","key":"1485_CR42","doi-asserted-by":"publisher","first-page":"1226","DOI":"10.1016\/j.jmva.2009.09.017","volume":"101","author":"H Yanagihara","year":"2010","unstructured":"Yanagihara, H., Satoh, K.: An unbiased Cp\u00a0criterion for multivariate ridge regression. Journal of Multivariate Analysis 101(5), 1226\u20131238 (2010)","journal-title":"Journal of Multivariate Analysis"},{"key":"1485_CR43","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1214\/15-EJS1022","volume":"9","author":"H Yanagihara","year":"2015","unstructured":"Yanagihara, H., Wakaki, H., Fujikoshi, Y.: A consistency property of the aic for multivariate linear models when the dimension and the sample size are large. Electron. J. Stat. 9, 869\u2013897 (2015)","journal-title":"Electron. J. Stat."},{"key":"1485_CR44","unstructured":"Zhuk, S.: Weighted pseudoinverse of compact operators and differentiation of signals with random noise. In: 23rd International Symposium on Mathematical Theory of Networks and Systems Hong Kong University of Science and Technology, Hong Kong, pp. 85\u201392 (2018)"},{"key":"1485_CR45","unstructured":"Zhu, W., Nakatsukasa, Y.: Convergence and near-optimal sampling for multivariate function approximations in irregular domains via vandermonde with arnoldi. arXiv preprint arXiv:2301.12241 (2023)"}],"container-title":["Numerische Mathematik"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00211-025-01485-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00211-025-01485-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00211-025-01485-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T16:30:45Z","timestamp":1758299445000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00211-025-01485-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,9]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["1485"],"URL":"https:\/\/doi.org\/10.1007\/s00211-025-01485-4","relation":{},"ISSN":["0029-599X","0945-3245"],"issn-type":[{"value":"0029-599X","type":"print"},{"value":"0945-3245","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,9]]},"assertion":[{"value":"19 November 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 April 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 June 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 July 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}