# Chapter 115. Signal Processing # Chapter 115. Signal Processing Signal processing studies how to represent, transform, analyze, filter, compress, and reconstruct signals. A signal is a quantity that varies over an index. The index may be time, space, frequency, pixel position, sensor number, or another ordered set. A speech waveform is a signal. An image is a two-dimensional signal. A sequence of temperature measurements is a signal. A voltage trace is a signal. A vector of samples is also a signal. Linear algebra enters signal processing because finite signals are vectors, filters are linear transformations, convolution can be written as matrix multiplication, and frequency analysis is a change of basis. The Fourier transform is a linear operator that maps a signal into its frequency-domain representation, and convolution becomes multiplication after transformation under standard Fourier conventions. ## 115.1 Signals as Vectors A finite discrete signal can be written as a vector $$ x = \begin{bmatrix} x_0 \\ x_1 \\ \vdots \\ x_{N-1} \end{bmatrix}. $$ The entry \(x_k\) is the value of the signal at sample index \(k\). For example, $$ x = \begin{bmatrix} 2 \\ 1 \\ -1 \\ 0 \end{bmatrix} $$ is a signal of length \(4\). Once a signal is written as a vector, the usual operations of linear algebra apply. Two signals of the same length may be added: $$ (x+y)_k = x_k+y_k. $$ A signal may be scaled: $$ (cx)_k = cx_k. $$ These two operations make finite signals elements of a vector space. ## 115.2 Continuous and Discrete Signals A continuous-time signal is a function $$ x(t), $$ where \(t\) varies continuously. A discrete-time signal is a sequence $$ x[n], $$ where \(n\) is an integer. A finite discrete signal is a finite sequence $$ x[0],x[1],\ldots,x[N-1]. $$ Digital signal processing works with finite discrete signals because computers store finite arrays of numbers. | Signal type | Mathematical form | |---|---| | Continuous-time signal | \(x(t)\) | | Discrete-time signal | \(x[n]\) | | Finite signal | \(x \in \mathbb{R}^N\) or \(x \in \mathbb{C}^N\) | | Image | Matrix or tensor | | Multichannel signal | Vector-valued sequence | The linear algebra viewpoint is most direct for finite signals. ## 115.3 Sampling Sampling converts a continuous-time signal into a discrete-time signal. Given a sampling interval \(T_s>0\), define $$ x[n] = x(nT_s). $$ The sampling frequency is $$ f_s = \frac{1}{T_s}. $$ Sampling replaces a function by a sequence of values. This process is fundamental in digital signal processing. The sampling process also has a frequency-domain interpretation: sampled spectra are related to shifted copies of the original spectrum, which explains aliasing when the sampling rate is too low. ## 115.4 Energy and Norms The energy of a finite signal is $$ \|x\|^2 = \sum_{k=0}^{N-1}|x_k|^2. $$ This is the squared Euclidean norm. The norm $$ \|x\| $$ measures the size or strength of the signal. For two signals \(x\) and \(y\), the inner product is $$ \langle x,y\rangle = \sum_{k=0}^{N-1} x_k\overline{y_k}. $$ If $$ \langle x,y\rangle=0, $$ then the signals are orthogonal. Orthogonality means that the signals contain independent components with respect to this inner product. ## 115.5 Linear Systems A system maps an input signal to an output signal. If \(T\) is a system, then $$ y = T(x) $$ means that input \(x\) produces output \(y\). A system is linear if $$ T(ax+bz)=aT(x)+bT(z) $$ for all signals \(x,z\) and all scalars \(a,b\). Linearity means that scaling and superposition are preserved. If a signal is decomposed into simpler parts, a linear system may be applied to each part separately, and the results may be added. This principle is central in filtering, Fourier analysis, convolution, and system identification. ## 115.6 Filters A filter is a system designed to modify a signal. A filter may remove noise, smooth a signal, sharpen edges, suppress unwanted frequencies, or extract features. For a finite signal, a linear filter can be represented by a matrix: $$ y = Hx. $$ Here \(H\) is the filter matrix. For example, a simple three-point smoothing filter may average neighboring samples: $$ y_k = \frac{1}{3}(x_{k-1}+x_k+x_{k+1}). $$ This operation replaces each sample by a local average. In matrix form, such a filter has nonzero entries near the diagonal. ## 115.7 Impulse Response The impulse signal is zero everywhere except at one position. For a discrete signal, the unit impulse at index \(0\) is $$ \delta[n] = \begin{cases} 1, & n=0, \\ 0, & n\neq 0. \end{cases} $$ The impulse response of a linear time-invariant system is the output produced by the impulse input. It is usually denoted by $$ h[n]. $$ For a linear time-invariant system, the impulse response completely determines the system. Once \(h\) is known, the output for any input \(x\) can be computed by convolution. ## 115.8 Convolution The convolution of two discrete signals \(x\) and \(h\) is $$ y[n] = (x*h)[n] = \sum_k x[k]h[n-k]. $$ This formula defines the output of a linear time-invariant filter with impulse response \(h\). Convolution combines shifted copies of the impulse response, weighted by the input samples. If \(x[k]\) is large, then a large shifted copy of \(h\) contributes to the output. Thus convolution expresses a signal as a superposition of shifted impulse responses. ## 115.9 Convolution as Matrix Multiplication For finite signals, convolution can be written as matrix multiplication. Suppose $$ h = \begin{bmatrix} h_0 \\ h_1 \\ h_2 \end{bmatrix} $$ and $$ x = \begin{bmatrix} x_0 \\ x_1 \\ x_2 \\ x_3 \end{bmatrix}. $$ A causal convolution output may be written as $$ y = \begin{bmatrix} h_0 & 0 & 0 & 0 \\ h_1 & h_0 & 0 & 0 \\ h_2 & h_1 & h_0 & 0 \\ 0 & h_2 & h_1 & h_0 \\ 0 & 0 & h_2 & h_1 \\ 0 & 0 & 0 & h_2 \end{bmatrix} \begin{bmatrix} x_0 \\ x_1 \\ x_2 \\ x_3 \end{bmatrix}. $$ The matrix is a Toeplitz matrix because its diagonals are constant. Thus filtering by convolution is a structured linear transformation. ## 115.10 Circular Convolution For finite periodic signals of length \(N\), convolution is often treated cyclically. The circular convolution of \(x\) and \(h\) is $$ y[n] = \sum_{k=0}^{N-1} x[k]h[(n-k)\bmod N]. $$ Circular convolution can be represented by a circulant matrix. A circulant matrix is a square matrix whose rows are cyclic shifts of one another. Circulant matrices are diagonalized by the discrete Fourier transform, which makes them important in numerical analysis and signal processing. ## 115.11 Frequency Domain Signals can be represented in the time domain or the frequency domain. The time-domain representation shows values over time or index. The frequency-domain representation shows how much of each frequency is present. The Fourier transform converts a signal from time domain to frequency domain: $$ x[n] \quad \longmapsto \quad X[\omega]. $$ In finite computation, the discrete Fourier transform maps a finite sequence to a finite sequence of frequency coefficients. The frequency domain is useful because many filters become simpler there. A convolution in the time domain becomes multiplication in the frequency domain: $$ \mathcal{F}(x*h) = \mathcal{F}(x)\mathcal{F}(h). $$ This identity is one of the main algebraic reasons Fourier methods are widely used in signal processing. ## 115.12 The Discrete Fourier Transform For a length \(N\) signal \(x\), the discrete Fourier transform is $$ X_k = \sum_{n=0}^{N-1} x_n e^{-2\pi i kn/N}, \qquad k=0,\ldots,N-1. $$ The inverse transform is $$ x_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k e^{2\pi i kn/N}. $$ The DFT is a linear transformation. It can be written as $$ X = Fx, $$ where \(F\) is the Fourier matrix. The normalized Fourier matrix is unitary, so it preserves inner products and energy. ## 115.13 Filtering in the Frequency Domain Let \(h\) be a filter and \(x\) be a signal. In the time domain, $$ y = h*x. $$ In the frequency domain, $$ Y_k = H_kX_k. $$ Here \(H_k\) is the frequency response of the filter. Thus a filter acts by scaling each frequency component. | Filter type | Frequency-domain behavior | |---|---| | Low-pass | Keeps low frequencies | | High-pass | Keeps high frequencies | | Band-pass | Keeps a middle frequency band | | Notch | Suppresses selected frequencies | | Smoothing | Reduces high-frequency content | | Differencing | Emphasizes high-frequency content | This is a diagonalization principle: convolution is complicated in the time basis but simple in the Fourier basis. ## 115.14 Noise Noise is unwanted variation in a signal. A measured signal may be modeled as $$ y = x + \varepsilon, $$ where \(x\) is the true signal and \(\varepsilon\) is noise. Signal processing tries to recover useful information from \(y\). If noise is mostly high frequency, a low-pass filter may reduce it. If noise occupies a known frequency band, a notch or band-stop filter may suppress it. If noise has statistical structure, methods based on covariance matrices, projections, and low-rank approximation may be used. ## 115.15 Denoising by Projection Suppose the useful signal lies approximately in a subspace \(S\). Let $$ P_S $$ be the orthogonal projection onto \(S\). Given noisy data $$ y=x+\varepsilon, $$ a denoised estimate is $$ \hat{x}=P_Sy. $$ This removes components orthogonal to the chosen signal subspace. The effectiveness depends on whether the subspace captures signal rather than noise. This is the same geometric idea used in least squares. ## 115.16 Compression Compression represents a signal using fewer numbers. The basic idea is to choose a basis in which the signal has only a few large coefficients. Let $$ x = \sum_{k=1}^{N} c_k q_k $$ be an expansion in an orthonormal basis. If most coefficients are small, we approximate $$ x \approx \sum_{k\in S} c_k q_k $$ using only selected indices \(S\). The discarded coefficients produce error. Compression therefore depends on basis choice, coefficient decay, and approximation error. Fourier, cosine, and wavelet bases are common in signal and image compression. ## 115.17 Low-Rank Approximation Images and multichannel signals are often stored as matrices. A grayscale image may be represented as a matrix $$ X \in \mathbb{R}^{m\times n}. $$ The singular value decomposition gives $$ X = U\Sigma V^T. $$ Keeping only the largest \(r\) singular values gives the rank-\(r\) approximation $$ X_r = U_r\Sigma_rV_r^T. $$ This is useful for compression and denoising. The singular values measure the importance of orthogonal modes. Small singular values often correspond to fine detail or noise. ## 115.18 Correlation Correlation measures similarity between signals. For finite real signals, the inner product $$ \langle x,y\rangle = \sum_{k=0}^{N-1}x_ky_k $$ is a basic similarity measure. If the signals are normalized, then the inner product measures cosine similarity. Cross-correlation compares one signal with shifted versions of another: $$ r_{xy}[m] = \sum_k x[k]y[k+m]. $$ Correlation is used in detection, alignment, pattern matching, radar, audio processing, and image registration. It is closely related to convolution. Discrete correlation can be expressed using a reversed version of convolution. ## 115.19 Matched Filtering A matched filter is designed to detect a known signal shape inside noisy data. Suppose the target pattern is \(s\). Given measured data \(y\), compute $$ \langle y,s\rangle. $$ If this inner product is large, then \(y\) contains a component similar to \(s\). For shifted patterns, use correlation: $$ r_{ys}[m] = \sum_k y[k]s[k+m]. $$ The index \(m\) with large correlation indicates where the pattern occurs. This is an application of projection: the measurement is tested against a known direction in signal space. ## 115.20 Linear Prediction Linear prediction estimates a future sample from previous samples. A simple model is $$ \hat{x}[n] = a_1x[n-1]+a_2x[n-2]+\cdots+a_px[n-p]. $$ The coefficients \(a_1,\ldots,a_p\) are chosen from data. This leads to a least squares problem. Collect many equations of the form $$ x[n]\approx a_1x[n-1]+\cdots+a_px[n-p]. $$ Then solve $$ Xa \approx y. $$ Linear prediction is used in speech coding, time-series analysis, spectral estimation, and adaptive filtering. ## 115.21 Adaptive Filtering An adaptive filter changes its coefficients based on incoming data. Let the filter output be $$ \hat{y}_n = w_n^Tx_n, $$ where \(w_n\) is the current coefficient vector and \(x_n\) is the current input vector. The error is $$ e_n = y_n-\hat{y}_n. $$ A simple update rule is $$ w_{n+1}=w_n+\alpha e_n x_n. $$ This is related to gradient descent on a least squares objective. Adaptive filtering is used in echo cancellation, noise cancellation, channel equalization, and online prediction. ## 115.22 Images as Signals An image is a two-dimensional signal. A grayscale image can be represented as a matrix $$ X = \begin{bmatrix} x_{11} & x_{12} & \cdots & x_{1n} \\ x_{21} & x_{22} & \cdots & x_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ x_{m1} & x_{m2} & \cdots & x_{mn} \end{bmatrix}. $$ Each entry is a pixel intensity. Filtering an image means applying local linear transformations to neighborhoods of pixels. Common image filters include smoothing, sharpening, edge detection, deblurring, and denoising. Two-dimensional convolution is the standard matrix-based operation behind many image filters. ## 115.23 Transform Coding Transform coding changes the basis before storing or transmitting data. The steps are: | Step | Operation | |---|---| | Transform | Convert signal to coefficients | | Quantize | Approximate coefficients | | Encode | Store coefficients efficiently | | Decode | Reconstruct approximate signal | | Inverse transform | Return to original domain | The transform is chosen so that most energy is concentrated in relatively few coefficients. This is a linear algebra strategy: choose a basis where the data are sparse or compressible. The discrete cosine transform, Fourier transform, and wavelet transform are common examples. ## 115.24 Wavelets Wavelets provide localized basis functions. Fourier basis functions extend across the whole domain. Wavelets are localized in both position and scale. This makes wavelets useful for signals with sharp changes, edges, bursts, or multiscale structure. Wavelet transforms decompose a signal into coarse and detailed components. In filter-bank form, this is done by applying low-pass and high-pass filters, followed by downsampling. Polyphase matrices provide a matrix representation of filter banks used in subband coders and discrete wavelet transforms. ## 115.25 Signal Processing and Linear Algebra The main connection is that signal processing operations are linear or approximately linear. | Signal processing object | Linear algebra object | |---|---| | Finite signal | Vector | | Image | Matrix | | Multichannel signal | Matrix or tensor | | Filter | Linear operator | | Convolution | Toeplitz or circulant matrix | | Fourier transform | Unitary change of basis | | Frequency response | Diagonal operator | | Denoising | Projection | | Compression | Sparse or low-rank approximation | | Correlation | Inner product | | Adaptive filtering | Least squares and gradient descent | This table summarizes why linear algebra is the basic language of signal processing. ## 115.26 Summary Signal processing studies signals and systems. Linear algebra gives finite signals the structure of vectors and gives filters the structure of matrices. Convolution is a structured matrix operation. The Fourier transform changes the basis so that convolution becomes multiplication. Frequency-domain filtering is diagonal action in a Fourier basis. Noise reduction can be viewed as projection. Compression can be viewed as basis selection, coefficient truncation, or low-rank approximation. The central principle is representation. A signal may be difficult to interpret in one basis and simple in another. Linear algebra supplies the tools for changing representations and for understanding which information is preserved, suppressed, or approximated.