The Living Thing / Notebooks :

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 and the analytic problem.

citizen design

Image: Married To The Sea

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

To discuss: loss functions.

An interesting 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.

Chebychev polynomials

Fourier bases

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? 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.