convolve

Convolve is a mathematical operation that blends two functions to produce a third. For continuous signals, the convolution of f and g is defined as (f*g)(t) = ∫_{-∞}^{∞} f(τ) g(t−τ) dτ. For discrete signals, (f*g)[n] = ∑_{k=-∞}^{∞} f[k] g[n−k]. In both cases, the integral or sum is interpreted as sliding one function across the other and integrating or summing the product at each position. The term convolve comes from Latin convolvere, meaning to roll together.

Convolution arises naturally in linear time-invariant systems, where the output is the input convolved with the system's impulse response. It is a bilinear, commutative, and associative operation: f*g = g*f, (f*g)*h = f*(g*h). It is linear in each argument and preserves shifts.

The convolution theorem states that convolution in the time domain corresponds to pointwise multiplication in the frequency domain: F{f*g} = F{f} · F{g}. This enables efficient computation via fast Fourier transforms. In practice, discrete convolution is often implemented with zero-padding and FFTs for speed.

Two-dimensional convolution extends to functions on R^2, used in image processing. (f*g)(x,y) = ∬ f(u,v) g(x−u, y−v) du dv, with discrete versions summing over a kernel. Common kernels include Gaussian blurs, sharpeners, and edge detectors. Real-world use requires handling boundaries, via zero padding, reflection, or wrap-around.

Convolution is related to, but distinct from, cross-correlation, which does not flip the kernel: (f⋆g)(t) = ∫ f(τ) g(t+τ) dτ. In many contexts, “convolve” is used interchangeably with correlation for time series, but the mathematical definition uses reversal in one argument.