Signal processing#

Some notes on signal processing, mostly fourier and wavelet analysis.

About this chapter

A signal can be studied in time, in frequency, or in both at once. The intro covers sampling and the common filters, and the figure at its end compares how each representation tiles the time-frequency plane. Fourier analysis is the frequency view: the discrete Fourier transform (DFT) writes a sequence as a sum of sinusoids and is computed with the FFT.

Wavelets give up some frequency precision to keep time information. The wavelet sections describe the basis (shifts and dilations of a mother wavelet), common choices such as Haar and Morlet, how the discrete wavelet transform is computed with low-pass and high-pass filters, and what properties (vanishing moments, regularity) separate one wavelet basis from another.

Basics#

  • dirac-delta infinity at one point, zero everywhere else

  • A sinusoid and its parameters: amplitude (here 3), period ($0.02\pi$) and phase shift (0.01).

    Fig. 6 Figure 1. A sinusoid and its parameters: amplitude (here 3), period (\(0.02\pi\)) and phase shift (0.01).#

Intro#

Sampling turns a continuous signal into numbers. Shannon’s statement below is the condition for losing nothing: a signal with no frequencies above \(B\) needs samples at least \(2B\) times per second.

Interactive 1. A 3 Hz sine sampled 10 times a second. Lower the sampling rate below \(2f\) (or raise \(f\) above \(f_s/2\)) and the same samples also fit a slower sinusoid (green, dashed): from the samples alone the two can't be told apart.
  • signal can be continuous or discrete based on its domain (not values)

  • analog signal - continuous in time

    • sampling - the process of taking individual values of a continuous-time signal

    • sampling rate \(f_s\) - the number of samples taken per second (Hz)

    • sampling period - time interval between samples

  • digital signal - discrete in time and value

  • ”If a function x(t) contains no frequencies higher than B hertz, it is completely determined by giving its ordinates at a series of points spaced 1 2B seconds apart” –Shannon

  • signals are usually studied in

    • time-domain (with respect to time)

    • frequency-domain (with respect to frequency) - use Fourier transform

    • time-frequency representation (TFR) - use short-time Fourier transform (STFT) or wavelets

  • harmonic analysis - studies relationship between time and frequency domain

  • common filters

    • low-pass filter - pass only low frequencies

    • high-pass filter - pass only high frequencies

    • band-pass filter - pass only frequencies within a specified range

    • band-stop filter - pass only frequences outside a specified range

  • power spectrum - how much of the signal is at a frequency \(\omega\)? - square of the magnitude of the coefficients of the Fourier coefficients for \(\omega\)

How each representation tiles the time-frequency plane. The raw time series resolves time but not frequency, the Fourier transform the reverse, and the short-time FT uses a uniform grid. The wavelet t

Fig. 7 Figure 2. How each representation tiles the time-frequency plane. The raw time series resolves time but not frequency, the Fourier transform the reverse, and the short-time FT uses a uniform grid. The wavelet transform uses narrow, tall cells at high frequencies and wide, short cells at low frequencies.#

Fourier analysis#

Each DFT coefficient \(X_k\) is the correlation between the signal and one complex sinusoid; its real part comes from the cosine and its imaginary part from the sine.

Interactive 2. A Fourier series rebuilt one harmonic at a time. The bars are the power spectrum, the squared coefficient of each harmonic. The triangle wave has no jumps and its power falls off fast, so a few harmonics are enough. The square wave and sawtooth jump: they need many more, and the partial sums keep wiggling next to each jump.
  • good tutorial

  • Fourier analysis - study of way general functions can be represented by Fourier series

  • Fourier series - periodic function composed of harmonically related sinusoids, combined by a weighted summation

    • one period of the summation can approximate an arbitrary function in that interval

  • (continuous) Fourier transform \(\hat f\): time (x) -> frequency (u)

    • \(\hat{f}(u) = \int_{-\infty}^{\infty} f(x)\ e^{-2\pi i x u}\,dx\)

    • \(f(x) = \int_{-\infty}^{\infty} \hat f(u)\ e^{2\pi i x u} \,du\)

    • 2-dimensional (good ref)

      • \(F(u, v) = \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} f(x, y) e^{-i 2 \pi (ux + vy)}\,dx\, dy\)

      • inverse: \(f(x,y) = \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} F(u, v) e^{i 2 \pi (ux + vy)}\,du\, dv\)

      • for each basis, magnitude of vector [u, v] is frequency and direction gives orientation

  • Fourier transform of Gaussian is Gaussian

  • discrete-time Fourier transform - values are still continuous

    • \(X_{2\pi}(\omega) = \sum_{n=-\infty}^{\infty} x_n \,e^{-i \omega n}\)

      • \(\omega\) is frequency

  • discrete Fourier transform (DFT or the analysis equation) - this is by far the most common

    • \[\begin{split}\begin{align}X_k &= \sum_{n=0}^{N-1} \cblue{x_n} \corange{e^{-2\pi i k n / N}}\\&=\sum_{n=0}^{N-1} \cblue{x_n} \left[ \cgreen{\cos(2\pi k \frac n N )} - i \cpink{\sin(2 \pi k \frac n N )}\right]\end{align}\end{split}\]
    • larger k is higher freq.

    • inverse transform: \(x_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k\cdot e^{i 2 \pi k n / N}\)

    • \(x_0, x_1, ... x_{N-1}\)\( is a sequence of N complex numbers (i.e. time domain) and we transform to another sequence of complex numbers \)\(X_0, X_1, ..., X_{N-1}\)

      • we write \(\mathbf X = \mathcal F (\mathbf x)\)

      • vectors \(u_k = \left[\left. e^{ \frac{i 2\pi}{N} kn} \;\right\vert \; n=0,1,\ldots,N-1 \right]^\mathsf{T}\) form an orthogonal basis over the set of N-dimensional complex vectors

    • interpreting units

      • a frequency of 1/N would correspond to a period of N

        • use \(2\pi/N\) so that it goes through one cycle with period of N

      • the n=0 parts correspond to a constant

      • all other frequencies are integer multiples of the first fundamental frequency

      • finding coefs: basically want to use the correlation between the signal and the basis element (this is what the summation and muliptlying does)

      • real part - corresponds to even part of the signal (the cosines)

      • imaginary part - corresponds to odd parts of the signal

  • can be quickly computed using the Fast Fourier Transform in \(O(n \log n)\) instead of \(O(n^2)\)

  • inverse discrete Fourier Transform (IDFT)

  • windowed fourier transform - chop signal into sections and analyze each section separately

Wavelet analysis#

A sinusoid lasts forever, so a Fourier coefficient says nothing about when a frequency occurs. A wavelet is a short wave: shifting it gives time information and stretching it gives frequency.

  • wavelet is localized in both time and frequency information

    • different wavelets thus vary in translation, scale, and sometimes orientation

    • many choices for wavelet basis, which replaces the sinusoid basis sinusoid \(\phi(x) = e^{i 2 \pi k x/N}\)

Wavelet basics#

Every wavelet basis is built from one mother wavelet \(\phi\) by translations \(b\) and dilations \(a\). The discrete wavelet transform restricts these to powers of 2 and integer shifts; the examples (Haar, Morlet, Mexican hat, Daubechies) differ in the shape of \(\phi\).

  • \(\phi(x)\) = mother wavelet (or analyzing wavelet)

    • basis consists of translations and dilations of the mother wavelet \(\phi(\frac{x-\cblue{b}}{\corange{a}})\)

  • wavelet vocab

    • discrete wavelet transform: set \(a=2^{-j}, b = k \cdot 2^{-j}\), where \(k\) and \(j\) are integers

      • starts from multiresolution analysis (mallat, 1989)

    • continuous wavelet transform: \(a > 0, b\) (still a point-by-point, digita transformation)

    • orthonormal

      • biorthogonal - more relaxed, still enables perfect reconstruction

    • undecimated - highly overparameterized, exists at every location

  • website to explore different wavelets

    • ex. Haar wavelet (step function on [0, 1]

      • The Haar mother wavelet, $+1$ on the first half of its interval and $-1$ on the second, and four scaled and shifted copies: two at the original width and two at half the width.

        Fig. 8 Figure 3. The Haar mother wavelet, \(+1\) on the first half of its interval and \(-1\) on the second, and four scaled and shifted copies: two at the original width and two at half the width.#

      • define translations and dilations \(\phi_{jk}(x) = \text{const} \cdot \phi(\corange{2^j} x - \cblue{k})\)

        • j, k are still integers

        • this is still orthogonal

    • ex. Gabor==Morlet wavelet: \(\phi_\sigma(x) = c \cdot \cblue{\underbrace{e^{-\frac 1 2 x^2}}_{\text{gaussian window}}} \corange{\underbrace{(e^{i\sigma x} - \kappa_\sigma)}_{\text{frequency}}}\)

    • ex. Mexican hat wavelet - 2nd deriv of Gaussian pdf (in 2d, called Laplacian of Gaussian)

    • ex. Daubechies wavelet

    • ex. coiflet

    • ex. scattering transform

    • ex. Mallat’s MRA - stretch/scale wavelets in a smart way to tile space

  • how are wavelets implemented? (figs taken from blog)

    • note: Continuous Wavelet Transform, (CWT), and the Discrete Wavelet Transform (DWT), are both, point-by-point, digital, transformations that are easily implemented on a computer

      • DWT restricts the value of the scale and translation of the wavelets (e.g. scale must increase in powers of 2 and translation must be integer)

    • The discrete wavelet transform of a chirp, a sinusoid whose frequency rises over time. Left: each level splits the previous low-pass (LP) output into a new low-pass and a high-pass (HP) part. Right: t

      Fig. 9 Figure 4. The discrete wavelet transform of a chirp, a sinusoid whose frequency rises over time. Left: each level splits the previous low-pass (LP) output into a new low-pass and a high-pass (HP) part. Right: the approximation (low-pass) and detail (high-pass) coefficients for levels 1 to 5. The fast end of the chirp shows up in the first levels’ details, the slow start only at the deepest levels.#

    • The approximation coefficients represent the output of the low pass filter (averaging filter) of the DWT.

    • The detail coefficients represent the output of the high pass filter (difference filter) of the DWT

    • pywt 2d can decompose in different ways

      • Ways to lay out a 2-D wavelet decomposition in pywt: the standard dyadic pyramid, a fully separable decomposition, and full and custom wavelet packets, which also split the detail bands.

        Fig. 10 Figure 5. Ways to lay out a 2-D wavelet decomposition in pywt: the standard dyadic pyramid, a fully separable decomposition, and full and custom wavelet packets, which also split the detail bands.#

      • wavelet packet uses linear combinations of wavelets

Properties of different wavelet bases#

What separates one basis from another. More vanishing moments give a smoother, more complex wavelet with longer support, and inverting the transform needs a wavelet with zero mean.

  • vanishing moments

    • higher number of vanishing moments = more complex wavelet

      • more accurate repr. of complex signal

      • longer support

      • p vanishing moments => polynomials up to pth order will not be identified

  • regularity

    • more vanishing moments = higher regularity

    • low regularity - more jagged wavelets, less smooth reconstructions

  • invertibility

    • requires admissibility condition, which at least requires wavelets have vanishing mean \(\int \psi(x) \mathrm{d} x=0\)

Wavelet analysis#

  • orthogonal wavelet basis: \(\phi_{(s,l)} (x) = 2^{-s/2} \phi (2^{-s} x-l)\)

    • scaling function \(W(x) = \sum_{k=-1}^{N-2} (-1)^k c_{k+1} \phi (2x+k)\) where \(\sum_{k=0,N-1} c_k=2, \: \sum_{k=0}^{N-1} c_k c_{k+2l} = 2 \delta_{l,0}\)

  • one pattern of coefficients is smoothing and another brings out detail = called quadrature mirror filter pair

  • there is also a fast discrete wavelet transform (Mallat)

  • basis of adapted waveform - best basis function for a given signal representation

  • differential operator and capable of being tuned to act at any desired scale

More general wavelets#

Extensions of the wavelet idea: generalized Daubechies and coiflet families, shearlets and curvelets for anisotropic features, and wavelets learned from data.

Key ideas

  • A signal with no frequencies above \(B\) is determined by samples taken at least \(2B\) times per second; sampling slower aliases high frequencies onto low ones.

  • Each DFT coefficient \(X_k\) is the correlation between the signal and one complex sinusoid, and the sinusoids form an orthogonal basis.

  • The FFT computes the DFT in \(O(n \log n)\) instead of \(O(n^2)\).

  • Fourier coefficients have no time information; wavelets, shifted and stretched copies of one mother wavelet, are localized in both time and frequency.

  • The discrete wavelet transform repeatedly splits a signal into low-pass approximation and high-pass detail coefficients.