The Living Thing / Notebooks : Function approximation

On constructing an approximation and measuring the badness of your approximation, of some arbitrary function, for use in computation.

I mean computable things here here, rather than abstract tools such as truncated functional Taylor expansions, which are used in theory not practice.

citizen design

Image: Married To The Sea

Choosing the best approximation

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

This is not in itself a statistical thing; you might want a simpler or more convenient approximation, or a more compact one, as in MP3 audio or JPEG images.

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 has some finite-sample guarantees.

To discuss: loss functions.

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

Polynomial spline smoothing of observations

The classic, and not just for functional data, but filed here because that’s where the action is now.

Special superpowers: Easy to differentiate and integrate.

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

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é)

Really handy for computation. Trivial to implement once calculated.

Easy to differentiate. OK to integrate if you cheat using a computation mathematics package.


Arneodo, A., Audit, B., Kestener, P., & Roux, S. (2008) Wavelet-based multifractal analysis. Scholarpedia, 3(3), 4103. DOI.
Barron, A. (1989) Minimum Complexity Estimation. (pp. 5_7–5_7). IEEE DOI.
Barron, A. R.(1993) Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information Theory, 39(3), 930–945. DOI.
Berinde, R., & Indyk, P. (2009) Sequential sparse matching pursuit. In 2009 47th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2009 (pp. 36–43). DOI.
Beylkin, G., & Monzón, L. (2010) Approximation by exponential sums revisited. Applied and Computational Harmonic Analysis, 28(2), 131–149. DOI.
Blumensath, T., & Davies, M. E.(2008a) Gradient pursuit for non-linear sparse signal modelling. In Signal Processing Conference, 2008 16th European (pp. 1–5). IEEE
Blumensath, T., & Davies, M. E.(2008b) Gradient Pursuits. IEEE Transactions on Signal Processing, 56(6), 2370–2382. DOI.
Carlson, R. E., & Fritsch, F. N.(1985) Monotone Piecewise Bicubic Interpolation. SIAM Journal on Numerical Analysis, 22(2), 386–400.
Cheney, E. W., & Light, W. A.(2009) A Course in Approximation Theory. . American Mathematical Soc.
Davis, G. M.(1998) A wavelet-based analysis of fractal image compression. IEEE Transactions on Image Processing, 7(2), 141–154. DOI.
Ekanadham, C., Tranchina, D., & Simoncelli, E. P.(2011) Recovery of Sparse Translation-Invariant Signals With Continuous Basis Pursuit. IEEE Transactions on Signal Processing, 59(10), 4735–4744. DOI.
Fritsch, F., & Carlson, R. (1980) Monotone Piecewise Cubic Interpolation. SIAM Journal on Numerical Analysis, 17(2), 238–246. DOI.
Goodwin, M. (1997) Matching pursuit with damped sinusoids. In Acoustics, Speech, and Signal Processing, 1997. ICASSP-97., 1997 IEEE International Conference on (Vol. 3, pp. 2037–2040). IEEE DOI.
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., & Vetterli, M. (1999) Matching pursuit and atomic signal models based on recursive filter banks. IEEE Trans. Signal Process., 47(7), 1890–1902. DOI.
Goodwin, M., & Vetterli, M. (1997) Atomic decompositions of audio signals. In 1997 IEEE ASSP Workshop on Applications of Signal Processing to Audio and Acoustics, 1997 (p. 4 pp.–). DOI.
Graps, A. (1995) An introduction to wavelets. IEEE Computational Science Engineering, 2(2), 50–61. DOI.
Higham, D. J.(1992) Monotonic piecewise cubic interpolation, with applications to ODE plotting. Journal of Computational and Applied Mathematics, 39(3), 287–294. DOI.
Huggins, P. S., & Zucker, S. W.(2007) Greedy Basis Pursuit. IEEE Transactions on Signal Processing, 55(7), 3760–3772. DOI.
Knudson, K. C., Yates, J., Huk, A., & Pillow, J. W.(2014) Inferring sparse representations of continuous signals with continuous orthogonal matching pursuit. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, & K. Q. Weinberger (Eds.), Advances in Neural Information Processing Systems 27 (Vol. 27, pp. 1215–1223). Curran Associates, Inc.
Kronland-Martinet, R., Guillemain, P., & Ystad, S. (1997) Modelling of natural sounds by time–frequency and wavelet representations. Organised Sound, 2(03), 179–191. DOI.
Pati, Y. C., Rezaiifar, R., & Krishnaprasad, P. S.(1993) Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition. In 1993 Conference Record of The Twenty-Seventh Asilomar Conference on Signals, Systems and Computers, 1993 (pp. 40–44 vol.1). DOI.
Ramsay, J. O.(1988) Monotone Regression Splines in Action. Statistical Science, 3(4), 425–441. DOI.
Rioul, O., & Vetterli, M. (1991) Wavelets and signal processing. IEEE Signal Processing Mag., 8(4), 14–38.
Rubinstein, R., Bruckstein, A. M., & Elad, M. (2010) Dictionaries for Sparse Representation Modeling. Proceedings of the IEEE, 98(6), 1045–1057. DOI.
Torrence, C., & Compo, G. P.(1998) A Practical Guide to Wavelet Analysis. Bulletin of the American Meteorological Society, 79(1), 61–78.
Vetterli, M. (1999) Wavelets: approximation and compression–a review. In AeroSense’99 (Vol. 3723, pp. 28–31). International Society for Optics and Photonics DOI.
Weidmann, C., & Vetterli, M. (2012) Rate Distortion Behavior of Sparse Sources. IEEE Transactions on Information Theory, 58(8), 4969–4992. DOI.
Wood, S. (1994) Monotonic Smoothing Splines Fitted by Cross Validation. SIAM Journal on Scientific Computing, 15(5), 1126–1133. DOI.
Zeevi, A. J., & Meir, R. (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. DOI.