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.

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.