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.

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

## Readings

- AAKR08
- Arneodo, A., Audit, B., Kestener, P., & Roux, S. (2008) Wavelet-based multifractal analysis.
*Scholarpedia*, 3(3), 4103. DOI. - Barr89
- Barron, A. (1989) Minimum Complexity Estimation. (pp. 5_7–5_7). IEEE DOI.
- Barr93
- Barron, A. R.(1993) Universal approximation bounds for superpositions of a sigmoidal function.
*IEEE Transactions on Information Theory*, 39(3), 930–945. DOI. - BeIn09
- 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.
- BeMo10
- Beylkin, G., & Monzón, L. (2010) Approximation by exponential sums revisited.
*Applied and Computational Harmonic Analysis*, 28(2), 131–149. DOI. - BlDa08a
- 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
- BlDa08b
- Blumensath, T., & Davies, M. E.(2008b) Gradient Pursuits.
*IEEE Transactions on Signal Processing*, 56(6), 2370–2382. DOI. - CaFr85
- Carlson, R. E., & Fritsch, F. N.(1985) Monotone Piecewise Bicubic Interpolation.
*SIAM Journal on Numerical Analysis*, 22(2), 386–400. - ChLi09
- Cheney, E. W., & Light, W. A.(2009) A Course in Approximation Theory. . American Mathematical Soc.
- Davi98
- Davis, G. M.(1998) A wavelet-based analysis of fractal image compression.
*IEEE Transactions on Image Processing*, 7(2), 141–154. DOI. - EkTS11
- 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. - FrCa80
- Fritsch, F., & Carlson, R. (1980) Monotone Piecewise Cubic Interpolation.
*SIAM Journal on Numerical Analysis*, 17(2), 238–246. DOI. - Good97
- 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.
- Good01
- 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.
- GoVe99
- 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. - GoVe97
- 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.
- Grap95
- Graps, A. (1995) An introduction to wavelets.
*IEEE Computational Science Engineering*, 2(2), 50–61. DOI. - High92
- Higham, D. J.(1992) Monotonic piecewise cubic interpolation, with applications to ODE plotting.
*Journal of Computational and Applied Mathematics*, 39(3), 287–294. DOI. - HuZu07
- Huggins, P. S., & Zucker, S. W.(2007) Greedy Basis Pursuit.
*IEEE Transactions on Signal Processing*, 55(7), 3760–3772. DOI. - KYHP14
- 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.
- KrGY97
- 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. - PaRK93
- 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.
- Rams88
- Ramsay, J. O.(1988) Monotone Regression Splines in Action.
*Statistical Science*, 3(4), 425–441. DOI. - RiVe91
- Rioul, O., & Vetterli, M. (1991) Wavelets and signal processing.
*IEEE Signal Processing Mag.*, 8(4), 14–38. - RuBE10
- Rubinstein, R., Bruckstein, A. M., & Elad, M. (2010) Dictionaries for Sparse Representation Modeling.
*Proceedings of the IEEE*, 98(6), 1045–1057. DOI. - ToCo98
- Torrence, C., & Compo, G. P.(1998) A Practical Guide to Wavelet Analysis.
*Bulletin of the American Meteorological Society*, 79(1), 61–78. - Vett99
- Vetterli, M. (1999) Wavelets: approximation and compression–a review. In AeroSense’99 (Vol. 3723, pp. 28–31). International Society for Optics and Photonics DOI.
- WeVe12
- Weidmann, C., & Vetterli, M. (2012) Rate Distortion Behavior of Sparse Sources.
*IEEE Transactions on Information Theory*, 58(8), 4969–4992. DOI. - Wood94
- Wood, S. (1994) Monotonic Smoothing Splines Fitted by Cross Validation.
*SIAM Journal on Scientific Computing*, 15(5), 1126–1133. DOI. - ZeMe97
- 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.