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.

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.