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 for regular data, for one thing.

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

- ChLi09: (2009)
*A Course in Approximation Theory*. American Mathematical Soc. - ToCo98: (1998) A Practical Guide to Wavelet Analysis.
*Bulletin of the American Meteorological Society*, 79(1), 61–78. - Davi98: (1998) A wavelet-based analysis of fractal image compression.
*IEEE Transactions on Image Processing*, 7(2), 141–154. DOI - DaMA97: (1997) Adaptive greedy approximations.
*Constructive Approximation*, 13(1), 57–98. DOI - Grap95: (1995) An introduction to wavelets.
*IEEE Computational Science Engineering*, 2(2), 50–61. DOI - BCDD08: (2008) Approximation and learning by greedy algorithms.
*The Annals of Statistics*, 36(1), 64–94. DOI - BeMo10: (2010) Approximation by exponential sums revisited.
*Applied and Computational Harmonic Analysis*, 28(2), 131–149. DOI - Cybe89: (1989) Approximation by superpositions of a sigmoidal function.
*Mathematics of Control, Signals and Systems*, 2, 303–314. DOI - Pink99: (1999) Approximation theory of the MLP model in neural networks.
*Acta Numerica*, 8, 143–195. DOI - GoVe97: (1997) Atomic decompositions of audio signals. In 1997 IEEE ASSP Workshop on Applications of Signal Processing to Audio and Acoustics, 1997. DOI
- Telg16: (2016) Benefits of depth in neural networks. In arXiv:1602.04485 [cs, stat].
- UnAE93a: (1993a) B-spline signal processing I Theory.
*IEEE Transactions on Signal Processing*, 41(2), 821–833. DOI - UnAE93b: (1993b) B-spline signal processing II Efficiency design and applications.
*IEEE Transactions on Signal Processing*, 41(2), 834–848. DOI - HoAn78: (1978) Cubic splines for image interpolation and digital filtering.
*IEEE Transactions on Acoustics, Speech and Signal Processing*, 26(6), 508–517. DOI - Dier96: (1996)
*Curve and surface fitting splines*. Oxford: Clarendon Press - ZeMe97: (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 - Dani17: (2017) Depth Separation for Neural Networks.
*ArXiv:1702.08489 [Cs, Stat]*. - RuBE10: (2010) Dictionaries for Sparse Representation Modeling.
*Proceedings of the IEEE*, 98(6), 1045–1057. DOI - LeBW96: (1996) Efficient agnostic learning of neural networks with bounded fan-in.
*IEEE Transactions on Information Theory*, 42(6), 2118–2132. DOI - PLRS16: (2016) Exponential expressivity in deep neural networks through transient chaos. In Advances in Neural Information Processing Systems 29 (pp. 3360–3368). Curran Associates, Inc.
- UnAE91: (1991) Fast B-spline transforms for continuous image representation and interpolation.
*IEEE Transactions on Pattern Analysis and Machine Intelligence*, 13(3), 277–285. DOI - BlDa08: (2008) Gradient pursuit for non-linear sparse signal modelling. In Signal Processing Conference, 2008 16th European (pp. 1–5). IEEE
- BlDa08: (2008) Gradient Pursuits.
*IEEE Transactions on Signal Processing*, 56(6), 2370–2382. DOI - HuZu07: (2007) Greedy Basis Pursuit.
*IEEE Transactions on Signal Processing*, 55(7), 3760–3772. DOI - KYHP14: (2014) Inferring sparse representations of continuous signals with continuous orthogonal matching pursuit. In Advances in Neural Information Processing Systems 27 (Vol. 27, pp. 1215–1223). Curran Associates, Inc.
- Orr96: (1996) Introduction to radial basis function networks. Technical Report, Center for Cognitive Science, University of Edinburgh
- Fome00: (2000) Inverse B-spline interpolation. Citeseer
- GoVe99: (1999) Matching pursuit and atomic signal models based on recursive filter banks.
*IEEE Transactions on Signal Processing*, 47(7), 1890–1902. DOI - Good97: (1997) Matching pursuit with damped sinusoids. In 1997 IEEE International Conference on Acoustics, Speech, and Signal Processing (Vol. 3, pp. 2037–2040). Munich, Germany: IEEE DOI
- Barr89: (1989) Minimum Complexity Estimation. (pp. 5_7-5_7). IEEE DOI
- WeKa74: (1974) Minimum energy control using spline functions. In 1974 IEEE Conference on Decision and Control including the 13th Symposium on Adaptive Processes (pp. 169–172). DOI
- KrGY97: (1997) Modelling of natural sounds by time–frequency and wavelet representations.
*Organised Sound*, 2(03), 179–191. DOI - CaFr85: (1985) Monotone Piecewise Bicubic Interpolation.
*SIAM Journal on Numerical Analysis*, 22(2), 386–400. - FrCa80: (1980) Monotone Piecewise Cubic Interpolation.
*SIAM Journal on Numerical Analysis*, 17(2), 238–246. DOI - Rams88: (1988) Monotone Regression Splines in Action.
*Statistical Science*, 3(4), 425–441. DOI - High92: (1992) Monotonic piecewise cubic interpolation, with applications to ODE plotting.
*Journal of Computational and Applied Mathematics*, 39(3), 287–294. DOI - Wood94: (1994) Monotonic Smoothing Splines Fitted by Cross Validation.
*SIAM Journal on Scientific Computing*, 15(5), 1126–1133. DOI - HoSW89: (1989) Multilayer feedforward networks are universal approximators.
*Neural Networks*, 2(5), 359–366. DOI - Good01: (2001) Multiscale overlap-add sinusoidal modeling using matching pursuit and refinements. In IEEE Workshop on Applications of Signal Processing to Audio and Acoustics.
- PoGi90: (1990) Networks for approximation and learning.
*Proceedings of the IEEE*, 78(9), 1481–1497. DOI - Telg17: (2017) Neural Networks and Rational Functions. In PMLR (pp. 3387–3393).
- DoEH89: (1989) Nonnegativity-, monotonicity-, or convexity-preserving cubic and quintic Hermite interpolation.
*Mathematics of Computation*, 52(186), 471–494. DOI - LGMR17: (2017) On the ability of neural nets to express distributions. In arXiv:1702.07028 [cs].
- SVWX17: (2017) On the Complexity of Learning Neural Networks.
*ArXiv:1707.04615 [Cs]*. - PaRK93: (1993) Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition. In Conference Record of The Twenty-Seventh Asilomar Conference on Signals, Systems and Computers (pp. 40–44 vol.1). DOI
- KWSR16: (2016) Parsimonious Online Learning with Kernels via Sparse Projections in Function Space.
*ArXiv:1612.04111 [Cs, Stat]*. - WeVe12: (2012) Rate Distortion Behavior of Sparse Sources.
*IEEE Transactions on Information Theory*, 58(8), 4969–4992. DOI - EkTS11: (2011) Recovery of Sparse Translation-Invariant Signals With Continuous Basis Pursuit.
*IEEE Transactions on Signal Processing*, 59(10), 4735–4744. DOI - BHBR16: (2016) Saturating Splines and Feature Selection.
*ArXiv:1609.06764 [Stat]*. - BeIn09: (2009) Sequential sparse matching pursuit. In 2009 47th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2009 (pp. 36–43). DOI
- WaST14: (2014) The Falling Factorial Basis and Its Statistical Applications.
*ArXiv:1405.0558 [Stat]*. - RoTe17: (2017) The power of deeper networks for expressing natural functions.
*ArXiv:1705.05502 [Cs, Stat]*. - Barr93: (1993) Universal approximation bounds for superpositions of a sigmoidal function.
*IEEE Transactions on Information Theory*, 39(3), 930–945. DOI - RiVe91: (1991) Wavelets and signal processing.
*IEEE Signal Processing Magazine*, 8(4), 14–38. DOI - Vett99: (1999) Wavelets: approximation and compression–a review. In AeroSense’99 (Vol. 3723, pp. 28–31). International Society for Optics and Photonics DOI