# Function approximation and interpolation

June 9, 2016 — June 9, 2016

convolution
functional analysis
Hilbert space
nonparametric
signal processing
sparser than thou

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.

## 1 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.

## 2 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.

## 3 Polynomial bases

See polynomial bases.

🏗️

## 5 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.

## 6 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.

## 7 References

Anil, Lucas, and Grosse. 2018.
Barron, A. 1989. In.
Barron, A.R. 1993. IEEE Transactions on Information Theory.
Barron, Andrew R., Cohen, Dahmen, et al. 2008. The Annals of Statistics.
Berinde, and Indyk. 2009. In 2009 47th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2009.
Berner, Grohs, Kutyniok, et al. 2021.
Beylkin, and Monzón. 2010. Applied and Computational Harmonic Analysis.
Blumensath, and Davies. 2008. “Gradient Pursuit for Non-Linear Sparse Signal Modelling.” In Signal Processing Conference, 2008 16th European.
Bölcskei, Grohs, Kutyniok, et al. 2019. SIAM Journal on Mathematics of Data Science.
Boyd, John P. 2001. Chebyshev & Fourier Spectral Methods. Lecture Notes in Engineering.
Boyd, Nicholas, Hastie, Boyd, et al. 2016. arXiv:1609.06764 [Stat].
Carlson, and Fritsch. 1985. SIAM Journal on Numerical Analysis.
Cheney, and Light. 2009. A Course in Approximation Theory.
Cybenko. 1989. Mathematics of Control, Signals and Systems.
Daniely. 2017. arXiv:1702.08489 [Cs, Stat].
Davies. n.d. “Multidimensional Triangulation and Interpolation for Reinforcement Learning.”
Davis, Geoffrey M. 1998. IEEE Transactions on Image Processing.
Davis, G., Mallat, and Avellaneda. 1997. Constructive Approximation.
DeVore, Hanin, and Petrova. 2021. Acta Numerica.
Dierckx. 1996. Curve and Surface Fitting Splines.
Dougherty, Edelman, and Hyman. 1989. Mathematics of Computation.
Ekanadham, Tranchina, and Simoncelli. 2011. IEEE Transactions on Signal Processing.
Elbrächter, Perekrestenko, Grohs, et al. 2021. IEEE Transactions on Information Theory.
Fomel. 2000.
Fritsch, and Carlson. 1980. SIAM Journal on Numerical Analysis.
Goodwin, Michael. 1997. In 1997 IEEE International Conference on Acoustics, Speech, and Signal Processing.
Goodwin, M M. 2001. In IEEE Workshop on Applications of Signal Processing to Audio and Acoustics.
Goodwin, M., and Vetterli. 1997. In 1997 IEEE ASSP Workshop on Applications of Signal Processing to Audio and Acoustics, 1997.
Goodwin, M M, and Vetterli. 1999. IEEE Transactions on Signal Processing.
Graps. 1995. IEEE Computational Science Engineering.
Grohs, and Herrmann. 2022. IMA Journal of Numerical Analysis.
Higham. 1992. Journal of Computational and Applied Mathematics.
Hornik, Stinchcombe, and White. 1989. Neural Networks.
Hou, and Andrews. 1978. IEEE Transactions on Acoustics, Speech and Signal Processing.
Huggins, and Zucker. 2007. IEEE Transactions on Signal Processing.
Knudson, Yates, Huk, et al. 2014. In Advances in Neural Information Processing Systems 27.
Koehler, Mehta, and Risteski. 2020. arXiv:2010.01155 [Cs, Stat].
Koppel, Warnell, Stump, et al. 2016. arXiv:1612.04111 [Cs, Stat].
Kronland-Martinet, Guillemain, and Ystad. 1997. Organised Sound.
Lee, Wee Sun, Bartlett, and Williamson. 1996. IEEE Transactions on Information Theory.
Lee, Holden, Ge, Ma, et al. 2017. In arXiv:1702.07028 [Cs].
Lyche, and Mørken. 2011. Spline Methods.
Opschoor, Petersen, and Schwab. 2020. Analysis and Applications.
Orr. 1996.
Pati, Rezaiifar, and Krishnaprasad. 1993. In Conference Record of The Twenty-Seventh Asilomar Conference on Signals, Systems and Computers.
Pinkus. 1999. Acta Numerica.
Poggio, and Girosi. 1990. Proceedings of the IEEE.
Poole, Lahiri, Raghu, et al. 2016. In Advances in Neural Information Processing Systems 29.
Ramsay. 1988. Statistical Science.
Rioul, and Vetterli. 1991. IEEE Signal Processing Magazine.
Rolnick, and Tegmark. 2017. arXiv:1705.05502 [Cs, Stat].
Rubinstein, Bruckstein, and Elad. 2010. Proceedings of the IEEE.
Sachdeva. 2013. Foundations and Trends® in Theoretical Computer Science.
Song, Vempala, Wilmes, et al. 2017. arXiv:1707.04615 [Cs].
Telgarsky. 2016. In arXiv:1602.04485 [Cs, Stat].
———. 2017. In PMLR.
Torrence, and Compo. 1998. Bulletin of the American Meteorological Society.
Unser, Michael, Aldroubi, and Eden. 1991. IEEE Transactions on Pattern Analysis and Machine Intelligence.
Unser, M., Aldroubi, and Eden. 1993a. IEEE Transactions on Signal Processing.
———. 1993b. IEEE Transactions on Signal Processing.
Vetterli. 1999. In AeroSense’99.
Wang, Smola, and Tibshirani. 2014. In Proceedings of the 31st International Conference on International Conference on Machine Learning - Volume 32. ICML’14.
Weidmann, and Vetterli. 2012. IEEE Transactions on Information Theory.
Weinert, and Kailath. 1974. In 1974 IEEE Conference on Decision and Control Including the 13th Symposium on Adaptive Processes.
Wiatowski, and Bölcskei. 2015. In Proceedings of IEEE International Symposium on Information Theory.
Wood. 1994. SIAM Journal on Scientific Computing.
Yarotsky, and Zhevnerchuk. 2020. In Proceedings of the 34th International Conference on Neural Information Processing Systems. NIPS’20.
Zeevi, and Meir. 1997. Neural Networks: The Official Journal of the International Neural Network Society.