List of transforms

List of transformsMain

Community hub

List of transforms

7 pages, 0 posts

0 subscribers

Recent from talks

Be the first to start a discussion here.

Recent from talks

Be the first to start a discussion here.

Contribute something

About hubMembersContent overviewUpdatesRules

Main reference articles

List of transforms

View on Wikipedia

from Wikipedia

This is a list of transforms in mathematics.

Integral transforms

[edit]

Discrete transforms

[edit]

Binomial transform
Discrete Fourier transform, DFT
- Fast Fourier transform, a popular implementation of the DFT
Discrete cosine transform
- Modified discrete cosine transform
Discrete Hartley transform
Discrete sine transform
Discrete wavelet transform
Hadamard transform (or, Walsh–Hadamard transform)
- Fast wavelet transform
Hankel transform, the determinant of the Hankel matrix
Discrete Chebyshev transform
- Equivalent, up to a diagonal scaling, to a discrete cosine transform
Finite Legendre transform
Irrational base discrete weighted transform
Mojette transform
Number-theoretic transform
Spherical Harmonic transform
Stirling transform

Discrete-time transforms

[edit]

These transforms have a continuous frequency domain:

Data-dependent transforms

[edit]

Karhunen–Loève transform

Other transforms

[edit]

External links

[edit]

Tables of Integral Transforms at EqWorld: The World of Mathematical Equations.

Revisions and contributors Edit on Wikipedia Read on Wikipedia

View on Grokipedia

from Grokipedia

A list of transforms in mathematics refers to a compilation of mathematical operations that convert a function or sequence from its original domain into a representation in another domain, often to simplify the solution of differential equations, analyze signals, or study physical systems. These transforms are broadly categorized into integral transforms, which involve integrals of the form

g(\alpha) = \int_a^b f(t) K(\alpha, t) \, dt

where

K(\alpha, t)

is the kernel function, and discrete transforms that operate on finite or infinite sequences.^[1]^[2] Among the most prominent integral transforms are the Fourier transform, which decomposes functions into frequency components and is fundamental in signal processing and quantum mechanics; the Laplace transform, widely used for solving linear ordinary differential equations with initial value problems in control theory and circuit analysis; and the Mellin transform, which relates to the Laplace transform via a change of variables and aids in solving problems involving multiplicative convolutions.^[3]^[4] Other notable integral transforms include the Hankel transform, essential for problems with radial symmetry in two dimensions; the Hilbert transform, which shifts the phase of sinusoidal components and appears in causality relations; and the Radon transform, crucial for tomography and image reconstruction.^[5] Discrete transforms, such as the discrete Fourier transform (DFT), provide finite approximations of their continuous counterparts and are computed efficiently via the fast Fourier transform (FFT) algorithm, enabling applications in digital signal processing and data compression.^[6]^[7] Additional discrete variants include the Z-transform, used for analyzing discrete-time signals and systems in digital control; the number theoretic transform, a variant of the DFT over finite fields for cryptographic applications; and the Hartley transform, a real-valued alternative to the Fourier transform for efficient computation.^[8]^[9] These lists serve as references for researchers and practitioners, highlighting transforms' kernels, inversion formulas, and applications across pure and applied mathematics.^[2]

Continuous transforms

Fourier-based transforms

Fourier-based transforms represent a class of integral transforms that decompose functions or signals into their frequency components using oscillatory kernels, primarily enabling the analysis of periodic and aperiodic phenomena in continuous domains. These transforms are foundational in fields such as physics, engineering, and mathematics, where they facilitate the transition from time or spatial domains to frequency domains for solving differential equations and understanding wave propagation. The core idea stems from expressing arbitrary functions as superpositions of complex exponentials, revealing underlying harmonic structures.^[3] The Fourier transform was developed by Joseph Fourier in his 1822 treatise on heat conduction, where it was introduced to model temperature distributions as sums of sinusoidal functions.^[10] The continuous Fourier transform of a function

f(t)

is defined as

\hat{f}(\omega) = \int_{-\infty}^{\infty} f(t) e^{-i \omega t} \, dt,

with the inverse transform recovering the original function via

f(t) = \frac{1}{2\pi} \int_{-\infty}^{\infty} \hat{f}(\omega) e^{i \omega t} \, d\omega.

This formulation, common in physics contexts, assumes

f(t)

is integrable and uses angular frequency

\omega

.^[11] For periodic functions with period

T

, the Fourier series expansion employs discrete coefficients

a_n = \frac{1}{T} \int_{0}^{T} f(t) e^{-i n \omega_0 t} \, dt, \quad \omega_0 = \frac{2\pi}{T},

allowing

f(t)

to be represented as

\sum_{n=-\infty}^{\infty} a_n e^{i n \omega_0 t}

.^[12] Key properties underpin the utility of Fourier-based transforms. Linearity ensures that the transform of a linear combination is the linear combination of the transforms:

\mathcal{F}\{a f + b g\} = a \hat{f} + b \hat{g}

.^[3] The convolution theorem states that the transform of a convolution equals the product of the transforms:

\mathcal{F}\{f * g\} = \hat{f} \cdot \hat{g}

, simplifying the analysis of systems with linear time-invariant responses.^[13] Parseval's theorem preserves energy between domains, asserting

\int_{-\infty}^{\infty} |f(t)|^2 \, dt = \frac{1}{2\pi} \int_{-\infty}^{\infty} |\hat{f}(\omega)|^2 \, d\omega

, which quantifies power distribution in frequency space.^[14] In applications, continuous Fourier transforms excel at solving partial differential equations, such as the heat equation

\frac{\partial u}{\partial t} = \alpha \frac{\partial^2 u}{\partial x^2}

, by transforming it into an ordinary differential equation in the frequency domain via separation of variables and integration over spatial exponentials.^[15] This approach diagonalizes the operator, yielding solutions as superpositions of decaying exponentials modulated by initial conditions. Variants of the Fourier transform adapt to symmetry properties. The continuous Fourier transform applies generally to

L^1

functions. The Fourier cosine transform, suited for even functions on

[0, \infty)

, is

\hat{f}_c(\omega) = \sqrt{\frac{2}{\pi}} \int_{0}^{\infty} f(t) \cos(\omega t) \, dt,

f^c(ω)=π2

∫0∞f(t)cos(ωt)dt, with a similar inverse form. The Fourier sine transform, for odd functions, uses $\hat{f}_s(\omega) = \sqrt{\frac{2}{\pi}} \int_{0}^{\infty} f(t) \sin(\omega t) \, dt.$

∫0∞f(t)sin(ωt)dt. These reduce computational complexity for functions with known parity.^[16]^[17]

The Laplace transform is an integral transform that converts a function of time

f(t)

, typically defined for

t \geq 0

, into a function of a complex variable

s = \sigma + i\omega

. It is defined as

\mathcal{L}\{f(t)\}(s) = F(s) = \int_{0}^{\infty} f(t) e^{-st} \, dt,

where the integral converges for values of

s

in a region determined by the growth of

f(t)

. This transform is particularly useful for analyzing functions that are zero for negative time, making it suitable for causal systems in engineering and physics. The Laplace transform was developed in the late 18th century by French mathematician Pierre-Simon Laplace as part of his work on probability theory and differential equations, with early forms appearing in his 1782 publications on celestial mechanics. It was later popularized in the late 19th century by English engineer Oliver Heaviside, who applied it extensively to electrical circuit analysis through his operational calculus, though Heaviside did not use the integral form explicitly. The inverse Laplace transform recovers

f(t)

from

F(s)

and is given by the Bromwich integral:

f(t) = \frac{1}{2\pi i} \int_{\gamma - i\infty}^{\gamma + i\infty} F(s) e^{st} \, ds,

where

\gamma

is chosen to the right of all singularities of

F(s)

; for practical computation, the residue theorem from complex analysis is often used to evaluate this contour integral by summing residues at the poles of

F(s)

.^[18]^[19]^[20] Key properties of the Laplace transform facilitate its use in solving differential equations. For differentiation, the transform of the derivative satisfies

\mathcal{L}\{f'(t)\}(s) = sF(s) - f(0)

, with higher-order derivatives following recursively by incorporating initial conditions. The initial value theorem states that

\lim_{t \to 0^+} f(t) = \lim_{s \to \infty} sF(s)

, provided the limits exist, while the final value theorem gives

\lim_{t \to \infty} f(t) = \lim_{s \to 0^+} sF(s)

for stable systems. These properties allow initial value problems to be converted into algebraic equations in the s-domain. In applications to linear time-invariant (LTI) systems, the transfer function is defined as

H(s) = Y(s)/X(s)

, where

Y(s)

and

X(s)

are the Laplace transforms of the output and input, respectively, enabling straightforward analysis of system stability and response via pole-zero plots.^[21]^[22] Related variants include the bilateral Laplace transform, defined over the entire real line as

\int_{-\infty}^{\infty} f(t) e^{-st} \, dt

, which extends the analysis to non-causal signals. When the real part

\sigma = 0

, the unilateral Laplace transform reduces to the Fourier transform, linking the two for functions with sufficient decay.^[23]^[24]

Other integral transforms

The Hankel transform is an integral transform particularly suited for functions exhibiting circular symmetry, defined as

\mathcal{H}_\nu \{f\}(k) = \int_0^\infty f(r) J_\nu (kr) r \, dr,

where

J_\nu

denotes the Bessel function of the first kind of order

\nu

, and the transform applies to radially symmetric functions in two dimensions, equivalent to a Fourier transform under radial coordinates.^[25] This transform is self-inverse, meaning applying it twice returns the original function (up to scaling conventions), a property that facilitates inversion in problems with cylindrical symmetry.^[25] Named after the German mathematician Hermann Hankel, who introduced it in 1869, the transform has found applications in optics, where it models diffraction patterns from circular apertures, such as in the computation of focal fields for cylindrically symmetric beams.^[26]^[27] The Mellin transform serves as a multiplicative analog to the Fourier transform, defined by

\mathcal{M}\{f\}(s) = \int_0^\infty f(x) x^{s-1} \, dx,

for complex

s

in a suitable strip of convergence, and it relates to the Fourier transform through the logarithmic substitution

x = e^{-u}

, transforming multiplicative convolutions into additive ones.^[11] Key properties include its role in establishing identities involving the Gamma function, such as Mellin-Barnes representations for special functions, which arise from contour integrals of the transform.^[11] Introduced by the Finnish mathematician Robert Hjalmar Mellin in 1895, it plays a central role in number theory, particularly in deriving the functional equation of the Riemann zeta function via its connection to the Gamma function and Poisson summation.^[28]^[29] The Hilbert transform, defined as the Cauchy principal value integral

\mathcal{H}\{f\}(t) = \frac{1}{\pi} \pvint_{-\infty}^\infty \frac{f(\tau)}{t - \tau} \, d\tau,

produces the imaginary part of the analytic signal representation of a real-valued function

f(t)

, where the analytic signal is

f(t) + i \mathcal{H}\{f\}(t)

, suppressing negative frequency components in the Fourier domain.^[11] This transform is bounded on

L^p

spaces for

1 < p < \infty

, with the operator norm given by

\tan(\pi/(2p))

or its cotangent counterpart depending on

p

, ensuring stability in signal analysis applications.^[11] It finds use in signal processing for envelope detection and instantaneous frequency estimation, forming the basis for techniques like single-sideband modulation.^[30]

Discrete transforms

Frequency-domain discrete transforms

The frequency-domain discrete transforms provide a framework for analyzing the frequency content of finite-length discrete signals, serving as discrete analogs to continuous Fourier analysis in digital signal processing. These transforms map time-domain sequences into frequency-domain representations using complex exponentials or equivalent bases, enabling efficient computation of spectral components for applications such as filtering and modulation analysis. Central to this category is the Discrete Fourier Transform (DFT), which underpins much of modern signal processing by decomposing signals into sums of sinusoids at discrete frequencies. The Discrete Fourier Transform (DFT) of a finite sequence

x_n

of length

N

is given by

X_k = \sum_{n=0}^{N-1} x_n e^{-i 2\pi k n / N}, \quad k = 0, 1, \dots, N-1,

where

X_k

represents the amplitude and phase at the

k

-th frequency bin. This formulation assumes equally spaced samples and produces periodic spectra with period

N

. The DFT exhibits key properties such as linearity, periodicity in both domains (with the transform sequence repeating every

N

points), and symmetry for real-valued inputs, where

X_{N-k} = X_k^*

. Computationally, the direct evaluation requires

O(N^2)

operations, but the Fast Fourier Transform (FFT) algorithm reduces this to

O(N \log N)

by exploiting the symmetry and periodicity of the exponential basis through a divide-and-conquer approach, such as the radix-2 decimation-in-time method. The FFT was introduced by James W. Cooley and John W. Tukey in their seminal 1965 paper, which popularized efficient digital implementation and revolutionized fields like seismology and image processing. Historically, the DFT concept traces back to Carl Friedrich Gauss's work on least-squares fitting in 1805, but it was formalized for digital computation in the 1940s amid wartime radar signal analysis. In applications, the DFT facilitates spectral analysis of digital audio signals by identifying dominant frequencies and harmonics, as seen in equalization and noise reduction tasks where the magnitude spectrum

|X_k|

reveals tonal content. For instance, in audio processing, the DFT enables the visualization of spectrograms, which plot frequency versus time to detect pitch variations in music or speech. A notable variant is the Goertzel algorithm, which computes a single

X_k

(or its magnitude) more efficiently than the full DFT or FFT when only one or few frequencies are of interest, using a second-order recursive filter with complexity

O(N)

independent of the number of bins. Developed by Gerald Goertzel in 1958, this method is particularly useful for tone detection in telephony, such as dual-tone multi-frequency signaling. The Number Theoretic Transform (NTT) extends the DFT to finite fields, defined modulo a prime

p

X_k = \sum_{n=0}^{N-1} x_n \omega^{k n} \mod p,

where

\omega

is a primitive

N

-th root of unity modulo

p

, ensuring exact arithmetic without floating-point precision issues inherent in the DFT. This property allows the NTT to perform fast cyclic convolutions exactly, avoiding rounding errors that can accumulate in FFT-based implementations. Introduced by John M. Pollard in 1971, the NTT leverages FFT-like algorithms over rings like

\mathbb{Z}/p\mathbb{Z}

for efficient polynomial multiplication. In cryptography, NTTs accelerate lattice-based schemes such as those in post-quantum encryption by enabling secure homomorphic operations on encrypted data. Additionally, NTTs support error-correcting codes by facilitating high-speed decoding in systems like Reed-Solomon codes, where exact transforms over finite fields detect and correct transmission errors in digital communications.

Orthogonal and unitary discrete transforms

Orthogonal and unitary discrete transforms represent a class of linear transformations that utilize orthogonal matrices for real-valued signals or unitary matrices for complex-valued signals, ensuring energy preservation through the relation

\|Qx\| = \|x\|

, where

Q

is the transform matrix and

x

is the input vector.^[31] These properties arise from orthogonality, satisfying

Q^T Q = I

for real orthogonal matrices, or unitarity, satisfying

Q^H Q = I

for complex cases with Hermitian transpose

Q^H

.^[32] Such transforms are particularly valuable in signal processing for decorrelating data and achieving compact representations, with fast algorithms reducing computational complexity from

O(N^2)

O(N \log N)

via recursive decompositions, as in the fast DCT.^[33] Unlike complex exponential-based transforms, they employ real bases like cosines, sines, or binary sequences, making them suitable for applications requiring real arithmetic and boundary-adapted decompositions.^[34] The Discrete Cosine Transform (DCT), introduced by Ahmed, Natarajan, and Rao in 1974, expresses a sequence

x_n

in terms of cosine functions and exists in four variants (types I–IV) to accommodate different boundary conditions, such as even or odd extensions of the signal. The type-II DCT, most widely used, is given by

X_k = \sum_{n=0}^{N-1} x_n \cos\left[ \frac{\pi (2n+1) k}{2N} \right], \quad k = 0, 1, \dots, N-1,

which approximates the continuous cosine transform and provides excellent energy compaction for smooth signals.^[34] Type-I DCT assumes even symmetry at both ends, type-III at one end only, and type-IV handles periodic extensions with half-sample shifts, enabling flexibility in block-based processing.^[34] Due to its orthogonality and near-optimal Karhunen–Loève approximation for natural images, the DCT forms the core of compression standards like JPEG for still images and MPEG for video, where it concentrates signal energy into low-frequency coefficients for efficient quantization and encoding. The Discrete Sine Transform (DST), akin to the DCT but using sine functions, supports odd boundary extensions and is defined for type-I as

X_k = \sum_{n=0}^{N-1} x_n \sin\left[ \frac{\pi (n+1)(k+1)}{N+1} \right], \quad k = 0, 1, \dots, N-1,

with analogous types I–IV for varied symmetries.^[34] Initially described alongside the DCT in the 1974 paper by Ahmed et al., the DST offers similar orthogonality and is applied in scenarios requiring sine-based decompositions, such as certain boundary-matched filters. The Hadamard transform employs the Walsh–Hadamard matrix

H

, a square matrix with entries

\pm 1

that is symmetric and orthogonal, applied as

Hx

to binary or low-precision data for rapid decomposition into Walsh basis functions.^[35] Hadamard matrices trace back to constructions by Hadamard in 1893, building on Sylvester's 1867 work, and their

\pm 1

entries enable multiplication-free computation via additions and subtractions.^[35] In applications, the transform supports error detection and correction in coding schemes, such as Hadamard codes that achieve high minimum distances for reliable transmission over noisy channels.^[36]

Sequence and combinatorial discrete transforms

Sequence and combinatorial discrete transforms encompass mathematical tools for analyzing and inverting functions defined on discrete structures, such as sequences and partially ordered sets (posets), with applications in enumerative combinatorics and discrete analysis. These transforms facilitate the manipulation of sums over combinatorial objects, enabling inversions and identities that parallel continuous calculus but tailored to finite or countable domains. Unlike frequency-domain methods, they emphasize relational and enumerative properties, such as inclusion-exclusion principles and difference operators, to derive closed-form expressions for counting problems. The Z-transform provides a generating function framework for bilateral sequences, defined as

Z\{x_n\} = \sum_{n=-\infty}^{\infty} x_n z^{-n}

, where

z

is a complex variable and

x_n

represents coefficients of a discrete sequence without inherent temporal ordering.^[37] This formulation, analogous to ordinary generating functions in combinatorics, supports operations like convolution inversion for sequence enumeration, such as partitioning problems, by converting recursive relations into algebraic equations. Its bilateral nature accommodates sequences extending in both directions, useful for symmetric combinatorial identities, though it shares structural similarities with one-sided generating functions employed in asymptotic analysis. Historically, the Z-transform emerged in the 1940s as a discrete analog to the Laplace transform, initially for control systems but adaptable to combinatorial sequence manipulation.^[38] The Möbius transform operates on functions over posets, transforming

f

f'(x) = \sum_{y \leq x} \mu(y,x) f(y)

, where

\mu

denotes the Möbius function of the poset, quantifying interval structures via recursive definitions like

\mu(x,x) = 1

and

\sum_{z: x \leq z \leq y} \mu(x,z) = 0

for

x < y

. This transform underpins the Möbius inversion theorem, which states that if

g(x) = \sum_{y \leq x} f(y)

, then

f(x) = \sum_{y \leq x} \mu(y,x) g(y)

, providing a discrete inverse akin to differentiation. The theorem generalizes the inclusion-exclusion principle to arbitrary posets, where the Möbius function encodes overcounting corrections through sign alternations based on chain lengths. Introduced by August Ferdinand Möbius in 1832 within number theory, the function and its inversion extend to broader poset contexts, influencing modern combinatorial enumeration.^[39]^[40] The finite difference transform, or forward difference operator, is given by

\Delta^k f(n) = \sum_{i=0}^k (-1)^{k-i} \binom{k}{i} f(n+i)

, representing the k-th discrete derivative for sequences

f: \mathbb{Z} \to \mathbb{R}

. This operator satisfies linearity and the summation rule

\Delta (f + g) = \Delta f + \Delta g

, with higher orders capturing curvature analogs in discrete settings. In discrete calculus, it enables summation formulas via the discrete fundamental theorem, where

\sum_{i=a}^b \Delta f(i) = f(b+1) - f(a)

, mirroring integration by parts for exact solutions to recurrence relations. Applications include solving linear difference equations in combinatorial optimization, such as counting lattice paths or binomial identities, without approximation errors inherent in continuous limits.^[41] Key properties of these transforms interlink through generating function relations; for instance, the Z-transform of finite differences yields factors like

(1 - z^{-1})^k

, facilitating exponential generating function conversions for permutation enumerations. The Möbius inversion theorem ensures invertibility on locally finite posets, preserving combinatorial interpretations across transforms. In applications, the Möbius transform computes chromatic polynomials of graphs via the subset lattice, where

P_G(k) = \sum_{S \subseteq V} (-1)^{|S|} k^{c(S)}

inverts inclusion counts of independent sets, as detailed in analyses of graph colorability.^[42] Finite differences underpin discrete calculus for exact summation in algorithms, such as evaluating hypergeometric series in probabilistic combinatorics. These tools collectively advance non-frequency discrete analysis, with the Möbius function's 1832 origins laying foundational inversion principles later echoed in mid-20th-century sequence methods.

Time-domain and signal processing transforms

Discrete-time frequency transforms

The Discrete-Time Fourier Transform (DTFT) provides a frequency-domain representation for infinite-duration discrete-time signals, serving as a bridge between continuous-time Fourier analysis and discrete processing. It is defined for a discrete-time signal

x

X(e^{j\omega}) = \sum_{n=-\infty}^{\infty} x e^{-j \omega n},

where

\omega

is the normalized angular frequency in radians per sample, and the transform is periodic with period

2\pi

. This periodicity arises from the discrete time indexing, allowing the spectrum to repeat every full cycle in frequency. The inverse DTFT recovers the original signal via

x = \frac{1}{2\pi} \int_{-\pi}^{\pi} X(e^{j\omega}) e^{j \omega n} \, d\omega.

The DTFT is particularly suited for aperiodic signals but extends naturally to periodic discrete-time sequences. For a periodic signal

x

with period

N

, the DTFT consists of Dirac impulses at harmonics

\omega_k = 2\pi k / N

for integer

k

, with coefficients

c_k = \frac{1}{N} \sum_{n=0}^{N-1} x e^{-j 2\pi k n / N}

, mirroring the discrete Fourier series. These coefficients are obtained by sampling the DTFT at the harmonic frequencies, enabling efficient spectral analysis of repeating discrete patterns.^[43] Key properties of the DTFT underpin its utility in signal analysis. Linearity holds such that the DTFT of a sum of signals is the sum of their DTFTs, and time shifts correspond to phase multiplication by

e^{-j \omega m}

. The convolution theorem states that the DTFT of the circular or linear convolution of two sequences equals the product of their individual DTFTs, facilitating frequency-domain multiplication for time-domain filtering. Additionally, Parseval's relation equates the energy in the time and frequency domains:

\sum_{n} |x|^2 = \frac{1}{2\pi} \int_{-\pi}^{\pi} |X(e^{j\omega})|^2 \, d\omega

. These properties relate directly to sampling phenomena, where the DTFT illustrates aliasing as spectral folding when sampling rates fall below the Nyquist limit.^[43] In digital signal processing, the DTFT is essential for designing infinite impulse response (IIR) and finite impulse response (FIR) filters by specifying desired frequency responses on the unit circle. It also aids in analyzing aliasing in sampled systems, ensuring reconstruction fidelity per the sampling theorem. Historically, the DTFT emerged in the 1940s amid developments in sampling theory, notably formalized through Claude Shannon's 1949 work on communication in noisy channels, which established the foundations for discrete spectral representations. A brief variant, the short-time DTFT (or windowed DTFT), adapts it for non-stationary signals by applying a sliding window to capture local frequency content, as used in spectrogram analysis.^[44]

Z-transforms and generating functions

The Z-transform provides a powerful framework for analyzing discrete-time signals and systems by mapping sequences from the time domain to the complex z-plane, where operations such as convolution become multiplication. As a Laurent series expansion, it generalizes the discrete-time Fourier transform by allowing convergence in annular regions of the complex plane, enabling the study of causality, stability, and transient behavior in digital systems. This transform is essential for discrete signal processing, particularly in control theory and filter design, where it simplifies the solution of linear constant-coefficient difference equations.^[45] For one-sided (causal) sequences where

x = 0

for

n < 0

, the unilateral Z-transform is defined as

X(z) = \mathcal{Z}\{x\} = \sum_{n=0}^{\infty} x z^{-n},

with the region of convergence (ROC) consisting of values of

z

for which the infinite sum converges absolutely, typically an exterior of a circle

|z| > r

determined by the sequence's growth rate. For two-sided sequences extending to negative indices, the bilateral Z-transform extends the summation limits:

X(z) = \sum_{n=-\infty}^{\infty} x z^{-n},

where the ROC is an annulus

r_1 < |z| < r_2

between inner and outer radii, uniquely specifying the sequence when combined with

X(z)

. The ROC is critical for distinguishing sequences with identical transforms but different support, such as finite-duration versus infinite-duration signals.^[45] Key properties of the Z-transform include linearity,

\mathcal{Z}\{a x_1 + b x_2\} = a X_1(z) + b X_2(z)

, and time shifting. For a delay by

k > 0

units in the unilateral case,

\mathcal{Z}\{x[n - k]\} = z^{-k} X(z) + \sum_{m=1}^{k} x[-m] z^{-k + m}

, accounting for initial conditions; for advances (

k < 0

), the formula adjusts accordingly with future values. The inverse Z-transform recovers the sequence via the complex contour integral

x = \frac{1}{2\pi i} \oint_C X(z) z^{n-1} \, dz,

where

C

is a counterclockwise closed path in the ROC encircling the origin, often computed using partial fraction expansion and residue theorem for rational

X(z)

. These properties mirror those of the Laplace transform and facilitate frequency-domain analysis.^[46] The Z-transform maintains a direct connection to generating functions from combinatorics and analysis. The ordinary generating function for a sequence

\{x_n\}

G(z) = \sum_{n=0}^{\infty} x_n z^n

, and the unilateral Z-transform relates via

X(z) = G(1/z)

, allowing algebraic manipulations of recurrences to translate between domains. Exponential generating functions,

\sum_{n=0}^{\infty} x_n \frac{z^n}{n!}

, arise in contexts involving permutations or labeled objects and share similar inversion techniques, though scaled by factorials; this link enables cross-application of methods, such as using Z-transform poles for asymptotic sequence behavior.^[47] In applications, the Z-transform excels at solving linear homogeneous or inhomogeneous recurrence relations, such as those governing digital filter responses or queueing models, by converting them to polynomial equations in

z

, solving for

X(z)

, and applying the inverse transform. For instance, the recurrence

x = a x[n-1] + b \delta

yields

X(z) = b / (1 - a z^{-1})

, with solution via partial fractions. Stability analysis for causal LTI systems relies on pole locations: the system is BIBO stable if all poles lie inside the unit circle

|z| < 1

, ensuring the ROC encompasses

|z| \geq 1

and bounded impulse responses.^[48] Historically, the Z-transform's foundations lie in 18th-century generating functions pioneered by Leonhard Euler for enumerative problems, such as partition identities, where formal power series encoded sequence relations without convergence concerns. It was reintroduced in engineering by Witold Hurewicz in 1947 to handle sampled-data control systems via difference equations. The term "Z-transform" was formalized in 1952 by John R. Ragazzini and Lotfi A. Zadeh, who applied it systematically to sampled-data analysis, distinguishing it from the continuous Laplace transform by the variable

z = e^{sT}

.^[49]^[50]^[48]

Multirate and filter-bank transforms

Multirate signal processing involves techniques for changing the sampling rate of discrete-time signals, such as decimation and interpolation, which are fundamental to efficient filter-bank implementations. Polyphase decomposition represents a signal

x

as a sum of

M

lower-rate components for

M

-rate processing, expressed as

x = \sum_{k=0}^{M-1} x_{M,k}[n/M]

, where each

x_{M,k}

is a polyphase component obtained by downsampling the original signal by factor

M

after appropriate delays. This decomposition enables computationally efficient realizations of multirate filters by avoiding unnecessary computations at higher rates, leveraging the noble identities that commute filtering and rate changes.^[51]^[52] Filter banks in multirate systems consist of parallel analysis filters followed by downsamplers for subband decomposition, with synthesis filters and upsamplers for reconstruction. Modulated filter banks generate the subband filters from a single prototype using discrete Fourier transform (DFT) or cosine modulation, ensuring perfect reconstruction under certain conditions. In DFT-modulated banks, the filters are shifts of the prototype in the frequency domain, while cosine-modulated banks, such as those based on time-domain aliasing cancellation (TDAC), use cosine functions for real-valued signals and achieve aliasing cancellation through paired filter designs. Key properties include critically sampled banks, where the total downsampling factor equals the number of bands, minimizing redundancy while relying on aliasing cancellation for distortion-free reconstruction.^[51] These transforms find applications in subband coding for compression, such as wavelet filter banks that approximate continuous wavelet transforms via discrete multirate structures, though detailed wavelet analysis is beyond this scope. In audio compression, the MP3 standard employs a hybrid polyphase filter bank with 32 subbands followed by a modified discrete cosine transform (MDCT) for perceptual coding, enabling efficient bitrate reduction while preserving audio quality. Historically, multirate concepts were formalized in the 1980s by Crochiere and Rabiner, who developed foundational theory for decimation and interpolation in subband coding applications.^[52]^[53] Variants like oversampled filter banks introduce redundancy by downsampling at a factor less than the number of bands, enhancing robustness to channel noise, quantization errors, and modeling mismatches in applications such as acoustic echo cancellation and robust transmission. This oversampling provides greater design flexibility and improved noise immunity compared to critically sampled systems, at the cost of increased computational load.

Data-dependent and statistical transforms

Principal component analysis variants

Principal component analysis (PCA) is a dimensionality reduction technique that transforms a dataset into a new coordinate system where the greatest variances are captured by the first coordinates, known as principal components. This orthogonal transformation decorrelates the variables and orders the components by decreasing explained variance, enabling efficient representation of high-dimensional data. The method relies on the eigen-decomposition of the data's covariance matrix, denoted as

\Sigma = V \Lambda V^T

, where

V

is the matrix of eigenvectors (principal directions) and

\Lambda

is the diagonal matrix of corresponding eigenvalues (variances along those directions). Projection of the centered data onto the leading eigenvectors yields the principal components, with the first component maximizing the variance across all possible linear combinations of the original variables.^[54]^[55] The origins of PCA trace back to Karl Pearson's 1901 work on finding lines and planes of closest fit to systems of points in space, which laid the foundational geometric interpretation.^[56] Harold Hotelling expanded this in 1933 by formalizing the analysis of correlated statistical variables into uncorrelated components, emphasizing its utility in multivariate statistics. Key properties include the orthogonality of components, which ensures no redundancy, and their ordering by eigenvalues, allowing truncation of lower-variance components for approximation without significant information loss. This variance maximization criterion distinguishes PCA as an optimal linear unsupervised method for capturing data structure.^[55] For datasets where the number of observations exceeds features or vice versa, forming non-square data matrices, singular value decomposition (SVD) provides a robust alternative to direct eigen-decomposition. In this framework, the centered data matrix

X

is factored as

X = U \Sigma V^T

, where

V

contains the right singular vectors serving as principal components,

\Sigma

the singular values (square roots of eigenvalues), and

U

the left singular vectors. SVD handles numerical stability better for ill-conditioned matrices and extends PCA seamlessly to rectangular forms.^[57] PCA finds applications in noise reduction for images, where similar pixel blocks are grouped, transformed via PCA, and reconstructed after thresholding small coefficients to suppress noise while preserving edges and textures.^[58] In machine learning, it facilitates feature extraction by compressing high-dimensional inputs into lower-dimensional spaces that retain principal variances, improving model efficiency and generalization in tasks like classification.^[59] A prominent variant, kernel PCA, addresses nonlinear data structures by mapping observations into a higher-dimensional reproducing kernel Hilbert space via a kernel function, such as the radial basis function, before applying standard PCA. This implicit mapping captures nonlinear manifolds without explicit computation of high-dimensional coordinates, enabling separation of complex distributions.^[60]

Karhunen-Loève and empirical transforms

The Karhunen-Loève transform (KLT) represents an optimal orthogonal expansion for stationary random processes, deriving its basis functions from the eigenfunctions of the process's autocorrelation function

R(\tau)

. This transform decomposes a zero-mean stochastic process

X(t)

into a series

X(t) = \sum_{n=1}^\infty Z_n \phi_n(t)

, where

\phi_n(t)

are the eigenfunctions solving the integral equation

\int R(\tau - \sigma) \phi_n(\sigma) \, d\sigma = \lambda_n \phi_n(\tau)

, and

Z_n

are uncorrelated random coefficients with variances

\lambda_n

. Originally developed by Kari Karhunen in 1947 and independently by Michel Loève in the early 1950s, the KLT provides a theoretically ideal framework for representing correlated data in terms of uncorrelated components ordered by decreasing energy.^[61]^[62] A key property of the KLT is its minimization of the mean-square reconstruction error when truncating the expansion to the first

k

terms, achieving the lowest possible distortion for a fixed dimensionality in the

L^2

sense among all orthogonal transforms. This optimality stems from the eigenbasis aligning with the process's second-order statistics, concentrating signal energy in the leading eigenvalues for efficient approximation. In applications, the KLT excels in compressing correlated data, such as in image coding or multivariate time series, where retaining the dominant components preserves most of the information while reducing redundancy.^[63]^[64] For discrete-time signals observed over finite samples, the KLT is approximated via principal component analysis on the empirical covariance matrix, yielding the eigenvectors as the transform basis. This discrete variant maintains near-optimality for stationary processes under mild assumptions and is computationally feasible through eigendecomposition.^[64] The empirical mode decomposition (EMD) offers an adaptive, data-driven approach to analyzing non-stationary signals by sifting them into intrinsic mode functions (IMFs) without predefined bases. Introduced by Norden E. Huang and colleagues in 1998, EMD iteratively identifies local extrema in the signal, constructs upper and lower envelopes via cubic spline interpolation, and subtracts their mean from the signal to extract a single IMF, repeating until a residue remains. Each IMF represents a simple oscillatory mode with balanced positive and negative excursions, enabling decomposition of complex signals into components of varying time scales.^[65] Applying the Hilbert transform to each IMF yields the analytic signal, from which instantaneous amplitude and frequency are derived, forming the Hilbert spectrum—a time-frequency representation that captures nonlinear and non-stationary behaviors through localized energy distributions. Unlike fixed transforms, EMD's sifting process adapts to the signal's intrinsic structure, avoiding mode mixing and providing a physically meaningful instantaneous frequency for embedded oscillations.^[65] In biomedical applications, EMD is particularly valuable for processing signals like electrocardiograms (ECGs), where it denoises artifacts, extracts features such as QRS complexes, and reveals transient rhythms in non-stationary heart activity. For instance, EMD-based filtering has improved ECG signal-to-noise ratios by isolating physiological modes from noise, outperforming traditional methods in variable-rate scenarios. As a data-adaptive alternative to fixed-basis techniques like wavelets, EMD suits empirical analysis of irregular processes.^[66]^[67]

Adaptive and learning-based transforms

Adaptive and learning-based transforms represent a class of data-dependent methods that leverage machine learning techniques to derive transform bases tailored to specific datasets, enabling more efficient representations than fixed or statistical alternatives. These transforms optimize parameters through iterative training on input data, often in an unsupervised manner, to capture underlying structures such as sparsity or low-dimensional manifolds. Prominent examples include autoencoder-based transforms and sparse coding transforms, which have found applications in signal processing, computer vision, and generative modeling. Autoencoder-based transforms employ neural networks structured as an encoder-decoder pair, where the encoder compresses input data

\mathbf{x}

into a lower-dimensional latent representation

\mathbf{z} = f(\mathbf{x})

, and the decoder reconstructs it as

\hat{\mathbf{x}} = g(\mathbf{z})

. The network is trained to minimize a reconstruction loss, typically the mean squared error

\mathcal{L} = \|\mathbf{x} - \hat{\mathbf{x}}\|^2

, enforced via backpropagation, allowing the bottleneck layer to learn adaptive features that preserve essential information while discarding noise or redundancies. This architecture, popularized by Hinton and colleagues in 2006, facilitates dimensionality reduction and feature extraction by adapting to the data's intrinsic geometry.^[68] Sparse coding transforms, in contrast, learn an overcomplete dictionary

\mathbf{D}

of basis elements to represent signals as sparse linear combinations

\mathbf{x} \approx \mathbf{D} \boldsymbol{\alpha}

, where

\boldsymbol{\alpha}

has few non-zero entries. Optimization alternates between sparse coding steps, solving

\min_{\boldsymbol{\alpha}} \|\mathbf{x} - \mathbf{D} \boldsymbol{\alpha}\|^2 + \lambda \|\boldsymbol{\alpha}\|_1

for each signal, and dictionary update steps that refine

\mathbf{D}

to minimize the overall reconstruction error across the dataset. Introduced by Olshausen and Field in 1996, this approach mimics biological vision systems by promoting sparsity, which enhances efficiency in representing natural images.^[69] A core property of these transforms is their adaptivity to the underlying data distribution, achieved through unsupervised training that adjusts bases without labeled supervision, contrasting with linear baselines like principal component analysis. They enable scalable learning of hierarchical or nonlinear representations, with training often converging to sparse, localized features that align with data statistics. Additionally, their unsupervised nature allows deployment on unlabeled datasets, making them versatile for real-world applications. In applications, sparse coding transforms excel in image denoising by learning patch-specific dictionaries from noisy inputs, iteratively thresholding sparse codes to suppress artifacts while preserving edges, achieving superior performance over wavelet methods on natural images. Autoencoder variants similarly support generative models, where the learned latent space enables sampling of new data instances, as seen in probabilistic extensions. These methods have impacted fields like medical imaging and audio processing by providing compact, interpretable representations. Historically, sparse coding emerged from efforts to model receptive fields in the visual cortex, with Olshausen's 1996 work demonstrating how sparsity constraints yield oriented filters akin to simple cells. Autoencoders built on this foundation, with Hinton's 2006 advancements enabling deep architectures through restricted Boltzmann machine pretraining, bridging representation learning and neural networks. Variants such as variational autoencoders (VAEs) extend the deterministic framework by incorporating a probabilistic latent space, optimizing a variational lower bound on the log-likelihood to enable structured generation and uncertainty estimation, as formulated by Kingma and Welling in 2013.^[70] This probabilistic adaptation enhances robustness in tasks like anomaly detection, maintaining the adaptive essence while adding generative capabilities.

Specialized and geometric transforms

Radon and projection transforms

The Radon transform is an integral transform that computes the line integrals of a function over a family of lines in the Euclidean plane, providing a foundational tool for projection-based imaging. Formally, for a two-dimensional function

f(\mathbf{x})

, the Radon transform is defined as

Rf(\theta, s) = \int_{\mathbb{R}^2} f(\mathbf{x}) \delta(\mathbf{x} \cdot \mathbf{n}_\theta - s) \, d\mathbf{x},

where

\mathbf{n}_\theta = (\cos \theta, \sin \theta)

is the unit vector perpendicular to the line at angle

\theta

s

is the signed distance from the origin to the line, and

\delta

is the Dirac delta function. This transform, introduced by Austrian mathematician Johann Radon in 1917, originally addressed the inversion of integrals along manifolds but laid the groundwork for modern tomographic reconstruction. Practical applications in medicine emerged in the 1970s, with the development of computed tomography (CT) scanners that utilized Radon projections to generate cross-sectional images.^[71] A key property of the Radon transform is the central slice theorem, which establishes a direct link to the Fourier transform: the one-dimensional Fourier transform of the projection

Rf(\theta, \cdot)

at angle

\theta

equals the two-dimensional Fourier transform of

f

restricted to the radial line through the origin at angle

\theta

. This theorem enables efficient reconstruction algorithms by leveraging Fourier domain interpolation. The inverse Radon transform, essential for recovering

f

from its projections, is commonly implemented via filtered backprojection. In this method, each projection is filtered by convolution with the inverse Fourier transform of a ramp function

|\omega|

(where

\omega

is the angular frequency) to compensate for the transform's low-pass nature, followed by summation (backprojection) over all angles. This approach achieves exact inversion for bandlimited functions and forms the basis of standard CT reconstruction. In applications, the Radon transform underpins computed tomography, where X-ray attenuation projections at multiple angles reconstruct volumetric density distributions, revolutionizing medical diagnostics since the first clinical CT images in 1971.^[71] Allan Cormack and Godfrey Hounsfield received the 1979 Nobel Prize in Physiology or Medicine for advancing these techniques from theoretical projections to practical imaging systems.^[71] In computer vision, the transform aids in shape parametrization and feature extraction by representing object boundaries through projection profiles, facilitating tasks like object detection and alignment.^[72] The discrete Hough transform acts as a computational analog for detecting lines in digital images via parameterized voting. Variants of the Radon transform adapt to real-world acquisition geometries. The X-ray transform extends the model to finite beam widths by integrating over thin strips rather than idealized lines, accounting for partial volume effects in practical scanners. Divergent beam projections, used in fan-beam or cone-beam CT, handle non-parallel ray paths originating from a point source, with inversion formulas relating them to parallel-beam Radon data through rebinning or direct filtered backprojection adaptations.^[73] Recent advances include deep learning methods to accelerate Radon inversion for applications such as single-cell phase-contrast tomography.^[74]

Wavelet and time-frequency transforms

Wavelet transforms provide a framework for multi-resolution analysis of signals, enabling the examination of features at varying scales and locations in time, which is particularly useful for non-stationary signals where traditional Fourier methods fall short due to their fixed time-frequency resolution. Unlike the short-time Fourier transform, which uses a fixed window size and thus offers constant resolution across frequencies, wavelet transforms employ scalable and translatable basis functions called wavelets to achieve variable resolution, with finer details captured at higher frequencies and broader trends at lower ones.^[75] The continuous wavelet transform (CWT) of a signal

f(t)

is defined as

W(a,b) = \frac{1}{\sqrt{|a|}} \int_{-\infty}^{\infty} f(t) \psi^*\left(\frac{t - b}{a}\right) \, dt,

W(a,b)=∣a∣

1∫−∞∞f(t)ψ∗(at−b)dt, where $\psi(t)$ is the mother wavelet, $a \neq 0$ is the scale parameter controlling dilation, $b$ is the translation parameter for time localization, and the asterisk denotes complex conjugation. For the CWT to be invertible and allow perfect reconstruction of $f(t)$ , the mother wavelet must satisfy the admissibility condition $\int_{-\infty}^{\infty} \frac{|\hat{\psi}(\omega)|^2}{|\omega|} \, d\omega < \infty,$ ensuring zero mean and sufficient frequency spread, with the constant $C_\psi$ determining the reconstruction factor. This formulation was introduced by Grossmann and Morlet in their 1984 work on decomposing Hardy functions into square-integrable wavelets of constant shape, laying the foundation for time-frequency analysis in geophysics and beyond.^[76]^[75] The discrete wavelet transform (DWT) discretizes the CWT parameters, typically using dyadic scales $a = 2^j$ and translations $b = k \cdot 2^j$ for integers $j, k$ , to achieve efficient computation via filter banks that perform orthogonal decomposition into approximation and detail coefficients. This multiresolution structure, formalized by Mallat in 1989, enables a hierarchical representation where signals are successively low-pass and high-pass filtered and downsampled, preserving energy through perfect reconstruction filter banks. Daubechies' 1988 construction of compactly supported orthogonal wavelets provided the practical filters for this, balancing smoothness and support length for numerical stability. Key properties include multi-resolution analysis (MRA), which builds nested subspaces approximating the signal at dyadic scales, and vanishing moments, where the wavelet integrates to zero against polynomials up to a certain degree, allowing sparse representations of smooth signals by annihilating low-order trends.^[77]^[78] Wavelet transforms find wide application in signal denoising, where soft-thresholding of DWT coefficients removes noise while preserving edges, as developed by Donoho in 1995, achieving near-optimal risk bounds for Gaussian noise. In image compression, the DWT forms the core of the JPEG2000 standard, using biorthogonal 9/7-tap filters to yield superior rate-distortion performance over DCT-based JPEG, especially for high-fidelity lossless coding. Common wavelet variants include the Morlet wavelet, a complex Gaussian-modulated sinusoid favored for its frequency localization in CWT applications like seismic analysis, and the Mexican hat wavelet, the second derivative of a Gaussian, valued for detecting singularities. The stationary wavelet transform (SWT), or undecimated DWT, avoids downsampling to maintain translation invariance, enhancing denoising and fusion tasks by averaging shifted decimated transforms, as proposed by Coifman and Donoho in 1995.^[79]^[80]^[76] Recent developments as of 2025 include combining discrete wavelet transforms with LSTM models for enhanced financial time-series forecasting.^[81]

Topological and manifold transforms

Topological and manifold transforms extend classical transform theory to non-Euclidean spaces, leveraging algebraic topology to capture intrinsic geometric and structural properties of data lying on curved manifolds or exhibiting complex connectivity. These methods address limitations of Euclidean-based approaches by focusing on features like holes, voids, and connectivity that persist across scales, enabling robust analysis in high-dimensional, irregular domains. Unlike linear approximations such as principal component analysis, which assume flat structures, topological transforms provide invariance to deformations and support dimensionality reduction while preserving global shape information.^[82] The persistent homology transform is a cornerstone of this framework, tracking the evolution of topological features—such as connected components (0-dimensional holes), loops (1-dimensional), and voids (higher-dimensional)—across multiple scales through a process called filtration. In this approach, a point cloud or simplicial complex is progressively built by adding simplices (points, edges, triangles, etc.) ordered by a parameter like distance or density, creating a nested sequence of spaces. Homology groups compute the birth and death of these features at specific scales, represented as barcodes or persistence diagrams that visualize intervals of persistence, quantifying which structures are noise (short-lived) versus signal (long-lived). This transform yields topological invariants stable under small perturbations, as formalized by bottleneck distance metrics between diagrams, allowing reliable shape comparison on manifolds. Introduced by Edelsbrunner, Letscher, and Zomorodian in the early 2000s, persistent homology facilitates dimensionality reduction by embedding data into a space of persistent features, effective for curved geometries where traditional metrics fail.^[82]^[83] Diffusion maps provide another key transform for manifold learning, constructing low-dimensional embeddings that preserve intrinsic diffusion distances on non-Euclidean data. Starting from a graph representation of the data points, the method approximates the manifold's Laplace-Beltrami operator via the graph Laplacian

L

, then applies the diffusion semigroup

e^{-tL}

to define coordinates

\Psi_t(x) = (\lambda_1^t \psi_1(x), \lambda_2^t \psi_2(x), \dots)

, where

\lambda_k

and

\psi_k

are eigenvalues and eigenfunctions of the normalized Laplacian. This embedding captures geodesic-like distances adapted to the manifold's geometry, revealing clusters and trajectories without assuming linearity. Developed by Coifman and Lafon in 2006, diffusion maps excel in dimensionality reduction for curved spaces, offering topological-like invariance through their reliance on local connectivity rather than global alignment.^[84]^[85] A notable variant is the Mapper algorithm, which summarizes high-dimensional data topologically by combining partial clustering with a filter function to build a simplicial complex graph. It projects data onto a low-dimensional lens (e.g., via density or PCA), clusters overlapping bins, and connects clusters sharing points, yielding a coarse-grained representation of the manifold's structure like branches or loops. This method, introduced by Singh, Memoli, and Carlsson in 2007, complements persistent homology by providing interpretable visualizations for exploratory analysis.^[86] These transforms find applications in shape analysis for biological data, where persistent homology quantifies morphological variations in structures like leaves or proteins by detecting persistent voids and loops invariant to scaling or noise. In machine learning, diffusion maps enable manifold learning tasks such as trajectory inference in single-cell data, embedding curved state spaces to uncover transitions without Euclidean distortion. As of 2025, persistent homology is applied to identify tumor shapes in medical images, enhancing prognostic models.^[87] Overall, their properties of topological invariance and scale-aware dimensionality reduction make them indispensable for modern data analysis on non-flat domains.^[88]^[89]^[85]

History

List of transforms

Recent from talks

Recent from talks

Contribute something

Contribute something

Media Pages

Timelines

Articles

Notes collections

Notes

Notes

Days in Chronicle

List of transforms

Integral transforms

Discrete transforms

Discrete-time transforms

Data-dependent transforms

Other transforms

See also

External links