Function approximation and interpolation

On constructing an approximation of some arbitrary function, and measuring the badness thereof.

THIS IS CHAOS RIGHT NOW. I need to break out the sampling/interpolation problem for regular data, for one thing.

Choosing the best approximation

In what sense? Most compact? Most easy to code?

If we are not interpolating, how much smoothing do we do?

We can use cross-validation, especially so-called โ€œgeneralizedโ€ cross validation, to choose smoothing parameter this efficiently, in some sense.

Or you might have noisy data, in which case you now have a function approximation and inference problem, with error due to both approximation and sampling complexity. Compressive sensing can provide finite-sample guarantees for some of these settings.

To discuss: loss functions.

An interesting problem is how you align the curves that are your objects of study; That is a problem of warping.

Spline smoothing of observations

The classic.

Special superpowers: Easy to differentiate and integrate.

Special weakness: many free parameters, not so easy to do in high dimension.

See splines.

Polynomial bases

See polynomial bases.

Fourier bases


Radial basis function approximation

I# Radial basis function approximation I actually care about this mostly for densities, so see mixture models, for what information I do have.

Rational approximation

Padรฉโ€™s is the method Iโ€™ve heard of. Are there others? Easy to differentiate. OK to integrate if you cheat using a computational algebra package.


Anil, Cem, James Lucas, and Roger Grosse. 2018. โ€œSorting Out Lipschitz Function Approximation,โ€ November.
Barron, A. 1989. โ€œMinimum Complexity Estimation.โ€ In, 5_7โ€“7. IEEE.
Barron, Andrew R., Albert Cohen, Wolfgang Dahmen, and Ronald A. DeVore. 2008. โ€œApproximation and Learning by Greedy Algorithms.โ€ The Annals of Statistics 36 (1): 64โ€“94.
Barron, A.R. 1993. โ€œUniversal Approximation Bounds for Superpositions of a Sigmoidal Function.โ€ IEEE Transactions on Information Theory 39 (3): 930โ€“45.
Berinde, Radu, and Piotr Indyk. 2009. โ€œSequential Sparse Matching Pursuit.โ€ In 2009 47th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2009, 36โ€“43.
Berner, Julius, Philipp Grohs, Gitta Kutyniok, and Philipp Petersen. 2021. โ€œThe Modern Mathematics of Deep Learning.โ€
Beylkin, Gregory, and Lucas Monzรณn. 2010. โ€œApproximation by Exponential Sums Revisited.โ€ Applied and Computational Harmonic Analysis 28 (2): 131โ€“49.
Blumensath, Thomas, and Mike E. Davies. 2008. โ€œGradient Pursuit for Non-Linear Sparse Signal Modelling.โ€ In Signal Processing Conference, 2008 16th European, 1โ€“5. IEEE.
Bรถlcskei, Helmut, Philipp Grohs, Gitta Kutyniok, and Philipp Petersen. 2019. โ€œOptimal Approximation with Sparsely Connected Deep Neural Networks.โ€ SIAM Journal on Mathematics of Data Science 1 (1): 8โ€“45.
Boyd, John P. 2001. Chebyshev & Fourier Spectral Methods. Second Edition, Revised edition. Lecture Notes in Engineering. Berlin Heidelberg: Springer-Verlag.
Boyd, Nicholas, Trevor Hastie, Stephen Boyd, Benjamin Recht, and Michael Jordan. 2016. โ€œSaturating Splines and Feature Selection.โ€ arXiv:1609.06764 [Stat], September.
Carlson, R. E., and F. N. Fritsch. 1985. โ€œMonotone Piecewise Bicubic Interpolation.โ€ SIAM Journal on Numerical Analysis 22 (2): 386โ€“400.
Cheney, Elliott Ward, and William Allan Light. 2009. A Course in Approximation Theory. American Mathematical Soc.
Cybenko, G. 1989. โ€œApproximation by Superpositions of a Sigmoidal Function.โ€ Mathematics of Control, Signals and Systems 2: 303โ€“14.
Daniely, Amit. 2017. โ€œDepth Separation for Neural Networks.โ€ arXiv:1702.08489 [Cs, Stat], February.
Davies, Scott. n.d. โ€œMultidimensional Triangulation and Interpolation for Reinforcement Learning,โ€ 7.
Davis, Geoffrey M. 1998. โ€œA Wavelet-Based Analysis of Fractal Image Compression.โ€ IEEE Transactions on Image Processing 7 (2): 141โ€“54.
Davis, G., S. Mallat, and M. Avellaneda. 1997. โ€œAdaptive Greedy Approximations.โ€ Constructive Approximation 13 (1): 57โ€“98.
DeVore, Ronald, Boris Hanin, and Guergana Petrova. 2021. โ€œNeural Network Approximation.โ€ Acta Numerica 30 (May): 327โ€“444.
Dierckx, Paul. 1996. Curve and Surface Fitting Splines. Oxford: Clarendon Press.
Dougherty, Randall L., Alan S. Edelman, and James M. Hyman. 1989. โ€œNonnegativity-, Monotonicity-, or Convexity-Preserving Cubic and Quintic Hermite Interpolation.โ€ Mathematics of Computation 52 (186): 471โ€“94.
Ekanadham, C., D. Tranchina, and E. P. Simoncelli. 2011. โ€œRecovery of Sparse Translation-Invariant Signals With Continuous Basis Pursuit.โ€ IEEE Transactions on Signal Processing 59 (10): 4735โ€“44.
Elbrรคchter, Dennis, Dmytro Perekrestenko, Philipp Grohs, and Helmut Bรถlcskei. 2021. โ€œDeep Neural Network Approximation Theory.โ€ IEEE Transactions on Information Theory 67 (5): 2581โ€“2623.
Fomel, Sergey. 2000. โ€œInverse B-Spline Interpolation.โ€ Citeseer.
Fritsch, F., and R. Carlson. 1980. โ€œMonotone Piecewise Cubic Interpolation.โ€ SIAM Journal on Numerical Analysis 17 (2): 238โ€“46.
Goodwin, M M. 2001. โ€œMultiscale Overlap-Add Sinusoidal Modeling Using Matching Pursuit and Refinements.โ€ In IEEE Workshop on Applications of Signal Processing to Audio and Acoustics.
Goodwin, M M, and M Vetterli. 1999. โ€œMatching Pursuit and Atomic Signal Models Based on Recursive Filter Banks.โ€ IEEE Transactions on Signal Processing 47 (7): 1890โ€“1902.
Goodwin, Michael. 1997. โ€œMatching Pursuit with Damped Sinusoids.โ€ In 1997 IEEE International Conference on Acoustics, Speech, and Signal Processing, 3:2037โ€“40. Munich, Germany: IEEE.
Goodwin, M., and M. Vetterli. 1997. โ€œAtomic Decompositions of Audio Signals.โ€ In 1997 IEEE ASSP Workshop on Applications of Signal Processing to Audio and Acoustics, 1997.
Graps, A. 1995. โ€œAn Introduction to Wavelets.โ€ IEEE Computational Science Engineering 2 (2): 50โ€“61.
Grohs, Philipp, and Lukas Herrmann. 2022. โ€œDeep Neural Network Approximation for High-Dimensional Elliptic PDEs with Boundary Conditions.โ€ IMA Journal of Numerical Analysis 42 (3): 2055โ€“82.
Higham, D. J. 1992. โ€œMonotonic Piecewise Cubic Interpolation, with Applications to ODE Plotting.โ€ Journal of Computational and Applied Mathematics 39 (3): 287โ€“94.
Hornik, Kurt, Maxwell Stinchcombe, and Halbert White. 1989. โ€œMultilayer Feedforward Networks Are Universal Approximators.โ€ Neural Networks 2 (5): 359โ€“66.
Hou, H.S., and H. Andrews. 1978. โ€œCubic Splines for Image Interpolation and Digital Filtering.โ€ IEEE Transactions on Acoustics, Speech and Signal Processing 26 (6): 508โ€“17.
Huggins, P S, and S W Zucker. 2007. โ€œGreedy Basis Pursuit.โ€ IEEE Transactions on Signal Processing 55 (7): 3760โ€“72.
Knudson, Karin C, Jacob Yates, Alexander Huk, and Jonathan W Pillow. 2014. โ€œInferring Sparse Representations of Continuous Signals with Continuous Orthogonal Matching Pursuit.โ€ In Advances in Neural Information Processing Systems 27, edited by Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, 27:1215โ€“23. Curran Associates, Inc.
Koehler, Frederic, Viraj Mehta, and Andrej Risteski. 2020. โ€œRepresentational Aspects of Depth and Conditioning in Normalizing Flows.โ€ arXiv:2010.01155 [Cs, Stat], October.
Koppel, Alec, Garrett Warnell, Ethan Stump, and Alejandro Ribeiro. 2016. โ€œParsimonious Online Learning with Kernels via Sparse Projections in Function Space.โ€ arXiv:1612.04111 [Cs, Stat], December.
Kronland-Martinet, R., Ph. Guillemain, and S. Ystad. 1997. โ€œModelling of Natural Sounds by Timeโ€“Frequency and Wavelet Representations.โ€ Organised Sound 2 (03): 179โ€“91.
Lee, Holden, Rong Ge, Tengyu Ma, Andrej Risteski, and Sanjeev Arora. 2017. โ€œOn the Ability of Neural Nets to Express Distributions.โ€ In arXiv:1702.07028 [Cs].
Lee, Wee Sun, Peter L. Bartlett, and Robert C. Williamson. 1996. โ€œEfficient Agnostic Learning of Neural Networks with Bounded Fan-in.โ€ IEEE Transactions on Information Theory 42 (6): 2118โ€“32.
Lyche, Tom, and Knut Mรธrken. 2011. Spline Methods.
Opschoor, Joost A. A., Philipp C. Petersen, and Christoph Schwab. 2020. โ€œDeep ReLU Networks and High-Order Finite Element Methods.โ€ Analysis and Applications 18 (05): 715โ€“70.
Orr, Mark JL. 1996. โ€œIntroduction to Radial Basis Function Networks.โ€ Technical Report, Center for Cognitive Science, University of Edinburgh.
Pati, Y. C., R. Rezaiifar, and P. S. Krishnaprasad. 1993. โ€œOrthogonal Matching Pursuit: Recursive Function Approximation with Applications to Wavelet Decomposition.โ€ In Conference Record of The Twenty-Seventh Asilomar Conference on Signals, Systems and Computers, 40โ€“44 vol.1.
Pinkus, Allan. 1999. โ€œApproximation Theory of the MLP Model in Neural Networks.โ€ Acta Numerica 8 (January): 143โ€“95.
Poggio, T., and F. Girosi. 1990. โ€œNetworks for Approximation and Learning.โ€ Proceedings of the IEEE 78 (9): 1481โ€“97.
Poole, Ben, Subhaneil Lahiri, Maithreyi Raghu, Jascha Sohl-Dickstein, and Surya Ganguli. 2016. โ€œExponential Expressivity in Deep Neural Networks Through Transient Chaos.โ€ In Advances in Neural Information Processing Systems 29, edited by D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, 3360โ€“68. Curran Associates, Inc.
Ramsay, J. O. 1988. โ€œMonotone Regression Splines in Action.โ€ Statistical Science 3 (4): 425โ€“41.
Rioul, O., and M. Vetterli. 1991. โ€œWavelets and Signal Processing.โ€ IEEE Signal Processing Magazine 8 (4): 14โ€“38.
Rolnick, David, and Max Tegmark. 2017. โ€œThe Power of Deeper Networks for Expressing Natural Functions.โ€ arXiv:1705.05502 [Cs, Stat], May.
Rubinstein, Ron, A.M. Bruckstein, and Michael Elad. 2010. โ€œDictionaries for Sparse Representation Modeling.โ€ Proceedings of the IEEE 98 (6): 1045โ€“57.
Sachdeva, Sushant. 2013. โ€œFaster Algorithms via Approximation Theory.โ€ Foundations and Trendsยฎ in Theoretical Computer Science 9 (2): 125โ€“210.
Song, Le, Santosh Vempala, John Wilmes, and Bo Xie. 2017. โ€œOn the Complexity of Learning Neural Networks.โ€ arXiv:1707.04615 [Cs], July.
Telgarsky, Matus. 2016. โ€œBenefits of Depth in Neural Networks.โ€ In arXiv:1602.04485 [Cs, Stat].
โ€”โ€”โ€”. 2017. โ€œNeural Networks and Rational Functions.โ€ In PMLR, 3387โ€“93.
Torrence, Christopher, and Gilbert P Compo. 1998. โ€œA Practical Guide to Wavelet Analysis.โ€ Bulletin of the American Meteorological Society 79 (1): 61โ€“78.
Unser, M., A. Aldroubi, and M. Eden. 1993a. โ€œB-Spline Signal Processing. I. Theory.โ€ IEEE Transactions on Signal Processing 41 (2): 821โ€“33.
โ€”โ€”โ€”. 1993b. โ€œB-Spline Signal Processing. II. Efficiency Design and Applications.โ€ IEEE Transactions on Signal Processing 41 (2): 834โ€“48.
Unser, Michael, Akram Aldroubi, and Murray Eden. 1991. โ€œFast B-Spline Transforms for Continuous Image Representation and Interpolation.โ€ IEEE Transactions on Pattern Analysis and Machine Intelligence 13 (3): 277โ€“85.
Vetterli, Martin. 1999. โ€œWavelets: Approximation and Compressionโ€“a Review.โ€ In AeroSenseโ€™99, 3723:28โ€“31. International Society for Optics and Photonics.
Wang, Yu-Xiang, Alex Smola, and Ryan J. Tibshirani. 2014. โ€œThe Falling Factorial Basis and Its Statistical Applications.โ€ In Proceedings of the 31st International Conference on International Conference on Machine Learning - Volume 32, 730โ€“38. ICMLโ€™14. Beijing, China:
Weidmann, Claudio, and Martin Vetterli. 2012. โ€œRate Distortion Behavior of Sparse Sources.โ€ IEEE Transactions on Information Theory 58 (8): 4969โ€“92.
Weinert, H. L., and T. Kailath. 1974. โ€œMinimum Energy Control Using Spline Functions.โ€ In 1974 IEEE Conference on Decision and Control Including the 13th Symposium on Adaptive Processes, 169โ€“72.
Wiatowski, Thomas, and Helmut Bรถlcskei. 2015. โ€œA Mathematical Theory of Deep Convolutional Neural Networks for Feature Extraction.โ€ In Proceedings of IEEE International Symposium on Information Theory.
Wood, S. 1994. โ€œMonotonic Smoothing Splines Fitted by Cross Validation.โ€ SIAM Journal on Scientific Computing 15 (5): 1126โ€“33.
Yarotsky, Dmitry, and Anton Zhevnerchuk. 2020. โ€œThe Phase Diagram of Approximation Rates for Deep Neural Networks.โ€ In Proceedings of the 34th International Conference on Neural Information Processing Systems, 33:13005โ€“15. NIPSโ€™20. Red Hook, NY, USA: Curran Associates Inc.
Zeevi, Assaf J., and Ronny Meir. 1997. โ€œDensity Estimation Through Convex Combinations of Densities: Approximation and Estimation Bounds.โ€ Neural Networks: The Official Journal of the International Neural Network Society 10 (1): 99โ€“109.

No comments yet. Why not leave one?

GitHub-flavored Markdown & a sane subset of HTML is supported.