Frames and Riesz bases

Generalisations of orthogonal bases

June 12, 2017 — February 24, 2021

functional analysis
Hilbert space
linear algebra
signal processing
sparser than thou
Figure 1: Overcomplete basis

You want a fancy basis for your vector space? Try frames! You might care in this case about restricted isometry properties.

Morgenshtern and Bölcskei (Morgenshtern and Bölcskei 2011):

Hilbert spaces and the associated concept of orthonormal bases are of fundamental importance in signal processing, communications, control, and information theory. However, linear independence and orthonormality of the basis elements impose constraints that often make it difficult to have the basis elements satisfy additional desirable properties. This calls for a theory of signal decompositions that is flexible enough to accommodate decompositions into possibly nonorthogonal and redundant signal sets. The theory of frames provides such a tool. This chapter is an introduction to the theory of frames, which was developed by Duffin and Schaeffer (Duffin and Schaeffer 1952) and popularized mostly through (Ingrid Daubechies 1992; I. Daubechies 1990; Heil and Walnut 1989; Young 2001). Meanwhile frame theory, in particular the aspect of redundancy in signal expansions, has found numerous applications such as, e.g., denoising, code division multiple access (CDMA), orthogonal frequency division multiplexing (OFDM) systems, coding theory, quantum information theory, analog-to-digital (A/D) converters, and compressive sensing (Candès and Tao 2006; David L. Donoho 2006; David L. Donoho and Elad 2003). A more extensive list of relevant references can be found in (Kovačević and Chebira 2008). For a comprehensive treatment of frame theory we refer to the excellent textbook (Christensen 2016).

A compact signal-processing-oriented intro for engineers is Jorgensen and Song (2007).

1 References

Candès, Eldar, Needell, et al. 2011. Compressed Sensing with Coherent and Redundant Dictionaries.” Applied and Computational Harmonic Analysis.
Candès, and Tao. 2006. Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies? IEEE Transactions on Information Theory.
Christensen. 2016. An Introduction to Frames and Riesz Bases. Applied and Numerical Harmonic Analysis.
Daubechies, I. 1990. The Wavelet Transform, Time-Frequency Localization and Signal Analysis.” IEEE Transactions on Information Theory.
Daubechies, Ingrid. 1992. Ten lectures on wavelets.
Daubechies, Ingrid, DeVore, Fornasier, et al. 2010. Iteratively Reweighted Least Squares Minimization for Sparse Recovery.” Communications on Pure and Applied Mathematics.
Donoho, David L. 2006. Compressed Sensing.” IEEE Transactions on Information Theory.
Donoho, David L., and Elad. 2003. Optimally Sparse Representation in General (Nonorthogonal) Dictionaries via ℓ1 Minimization.” Proceedings of the National Academy of Sciences.
Donoho, D. L., Elad, and Temlyakov. 2006. Stable Recovery of Sparse Overcomplete Representations in the Presence of Noise.” IEEE Transactions on Information Theory.
Duffin, and Schaeffer. 1952. A Class of Nonharmonic Fourier Series.” Transactions of the American Mathematical Society.
Heil, and Walnut. 1989. Continuous and Discrete Wavelet Transforms.” SIAM Review.
Jorgensen, and Song. 2007. Entropy Encoding, Hilbert Space and Karhunen-Loeve Transforms.” Journal of Mathematical Physics.
Kovačević, and Chebira. 2008. An Introduction to Frames.
Morgenshtern, and Bölcskei. 2011. A Short Course on Frame Theory.”
Young. 2001. An Introduction to Non-Harmonic Fourier Series, Revised Edition, 93.