|
In mathematics and, in particular, functional analysis, convolution is a mathematical operator which takes two functions f and g and produces a third function that in a sense represents the amount of overlap between f and a reversed and translated version of g. Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ...
Functional analysis is the branch of mathematics, and specifically of analysis, concerned with the study of spaces of functions. ...
In mathematics, an operator is a function that performs some sort of operation on a number, variable, or function. ...
Graph of example function, The mathematical concept of a function expresses the intuitive idea of deterministic dependence between two quantities, one of which is viewed as primary (the independent variable, argument of the function, or its input) and the other as secondary (the value of the function, or output). A...
Typically, one of the functions is taken to be a fixed filter impulse response, and is known as a kernel. Such a convolution is a kind of generalized moving average, as one can see by taking the kernel to be an indicator function of an interval. The Impulse response from a simple audio system. ...
The term moving average is used in different contexts. ...
In the mathematical subfield of set theory, the indicator function, or characteristic function, is a function defined on a set X which is used to indicate membership of an element in a subset A of X. Remark. ...
In mathematics, interval is a concept relating to the sequence and set-membership of one or more numbers. ...
Visual explanation of convolution. First, create a dummy variable (in this case τ) and make each waveform a function of this variable. Second, time-invert one of the waveforms (it does not matter which) and add t. This allows the function to "slide" back and forth on the τ-axis while remaining stationary with respect to t. (The front edge of the "travelling" waveform is always t–1 in this case.) Finally, start one function at negative infinity and slide it all the way to positive infinity. Wherever the two functions intersect, find the integral of their product. The resulting waveform (not shown here) is the convolution of the two functions. Image File history File links Size of this preview: 553 × 599 pixelsFull resolution (914 × 990 pixel, file size: 29 KB, MIME type: image/png) Author/Source: E. Mote I, the creator of this work, hereby release it into the public domain. ...
Image File history File links Size of this preview: 553 × 599 pixelsFull resolution (914 × 990 pixel, file size: 29 KB, MIME type: image/png) Author/Source: E. Mote I, the creator of this work, hereby release it into the public domain. ...
In computer programming, a free variable is a variable referred to in a function that is not a local variable or an argument of that function. ...
Definition The convolution of  and  is written  . It is defined as the integral of the product of the two functions after one is reversed and shifted. As such, it is a particular kind of integral transform: In mathematics, an integral transform is any transform T of the following form: The input of this transform is a function f, and the output is another function Tf. ...
 The integration range depends on the domain on which the functions are defined; often a = -∞ and b = +∞. While the symbol  is used above, it need not represent the time domain. In the case of a finite integration range, and are often considered to extend periodically in both directions, so that the term  does not imply a range violation. This use of periodic domains is sometimes called a cyclic, circular or periodic convolution. Of course, extension with zeros is also possible. Using zero-extended or infinite domains is sometimes called a linear convolution, especially in the discrete case below. In mathematics, the domain of a function is the set of all input values to the function. ...
In mathematics, a periodic function is a function that repeats its values after some definite period has been added to its independent variable. ...
It has been suggested that this article or section be merged into convolution. ...
A brief comment will be made concerning clarity in the order of operations convolution imposes when evaluating proofs originating from the root defitinion. Consider the following example, convolution with a similarity operation ( ) on
 The question is does one mentally apply the operation on first and then apply the definition (which appears to ignore 's arguments by way of the integral's dummy variable of integration) or vice versa?   The second form is the correct interpretation of the involved notation, and in general 
Discrete convolution
Normal convolution For discrete functions, one can use a discrete version of the convolution. It is given by  When multiplying two polynomials, the coefficients of the product are given by the convolution of the original coefficient sequences, in this sense (using extension with zeros as mentioned above). In mathematics, a polynomial is an expression that is constructed from one variable or more variables and constants, using only the operations of addition, subtraction, multiplication, and constant positive whole number exponents. ...
For other senses of this word, see sequence (disambiguation). ...
Generalizing the above cases, the convolution can be defined for any two integrable functions defined on a locally compact topological group (see convolutions on groups below). Integrability is a mathematical concept used in different areas. ...
In topology and related branches of mathematics, a topological space is called locally compact if, roughly speaking, each small portion of the space looks like a small portion of a compact space. ...
In mathematics, a topological group G is a group that is also a topological space such that the group multiplication G × G → G and the inverse operation G → G are continuous maps. ...
A different generalization is the convolution of distributions. In mathematical analysis, distributions (also known as generalized functions) are objects which generalize functions and probability distributions. ...
Evaluating discrete convolutions takes O(N2) arithmetic operations. For other uses, see Big O. In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithms usage of computational resources (usually running time or memory). ...
Fast convolution In practice, digital signal processing typically uses fast convolution to increase the speed of the convolution. Digital signal processing (DSP) is the study of signals in a digital representation and the processing methods of these signals. ...
Calculating convolution via a fast convolution algorithm consists of taking the fast Fourier transform (see FFT) of two separate sequences, multiplying them together, and then computing the inverse fast Fourier transform, known as the IFFT. FFT may be: Fast Fourier transform Finite Fourier transform, another name for the discrete Fourier transform US Navy hull classification symbol for Reserve Training Frigates Final Fantasy Tactics, a video game. ...
A Fast Fourier Transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. ...
Fast convolution can be implemented using circular convolution. It has been suggested that this article or section be merged into convolution. ...
When using large sequences, evaluating fast discrete convolutions takes O(N log N) arithmetical operations.
Properties
 Example showing the commutativity of addition (3 + 2 = 2 + 3) For other uses, see Commute (disambiguation). ...
 In mathematics, associativity is a property that a binary operation can have. ...
 In mathematics, and in particular in abstract algebra, distributivity is a property of binary operations that generalises the distributive law from elementary algebra. ...
Identity element  where δ denotes the Dirac delta The Dirac delta function, introduced by Paul Dirac, can be informally thought of as a function δ(x) that has the value of infinity for x = 0, the value zero elsewhere, and a total integral of one. ...
Associativity with scalar multiplication  for any real (or complex) number  .
Differentiation rule  where  denotes the derivative of f or, in the discrete case, the difference operator  . Consequently, convolution can be viewed as a "smoothing" operation: the convolution of f and g is differentiable as many times as either f or g is, whichever is greater. For a non-technical overview of the subject, see Calculus. ...
In mathematics, a difference operator maps a function f(x) to another function f(x + a) − f(x + b). ...
Convolution theorem The convolution theorem states that In mathematics, the convolution theorem states that under suitable conditions the Fourier transform of a convolution is the point-wise product of Fourier transforms. ...
![mathcal{F}(f * g) = k left[mathcal{F} (f)right] cdot left[mathcal{F} (g)right]](http://upload.wikimedia.org/math/7/0/8/708c715ecd462ef018ff17d97d1e254b.png) where  denotes the Fourier transform of f, and k is a constant which depends upon the specific normalization of the Fourier transform (e.g., k = 1 if ![mathcal{F}left[f(x)right]equivint^infty_{-infty}f(x)exp(pm 2 pi i x &# 0;dx](http://upload.wikimedia.org/math/5/0/a/50a10a01b87b7afe49651d9fdaa7911e.png) ). Versions of this theorem also hold for the Laplace transform, two-sided Laplace transform, Z-transform and Mellin transform. In mathematics, the Fourier transform is a certain linear operator that maps functions to other functions. ...
The concept of a normalizing constant arises in probability theory and a variety of other areas of mathematics. ...
In the branch of mathematics called functional analysis, the Laplace transform, , is a linear operator on a function f(t) (original ) with a real argument t (t ≥ 0) that transforms it to a function F(s) (image) with a complex argument s. ...
In mathematics, the two-sided Laplace transform or bilateral Laplace transform is an integral transform closely related to the Fourier transform, the Mellin transform, and the ordinary or one-sided Laplace transform. ...
In mathematics and signal processing, the Z-transform converts a discrete time domain signal, which is a sequence of real numbers, into a complex frequency domain representation. ...
In mathematics, the Mellin transform is an integral transform that may be regarded as the multiplicative version of the two-sided Laplace transform. ...
See also less trivial Titchmarsh convolution theorem. In mathematics, the Titchmarsh convolution theorem is a result that describes the properties of the support of the convolution of two functions. ...
Convolutions on groups If G is a suitable group endowed with a measure m (for instance, a locally compact Hausdorff topological group with the Haar measure) and if f and g are real or complex valued m-integrable functions of G, then we can define their convolution by This picture illustrates how the hours on a clock form a group under modular addition. ...
In mathematics the concept of a measure generalizes notions such as length, area, and volume (but not all of its applications have to do with physical sizes). ...
In topology and related branches of mathematics, a topological space is called locally compact if, roughly speaking, each small portion of the space looks like a small portion of a compact space. ...
In topology and related branches of mathematics, a Hausdorff space is a topological space in which points can be separated by neighbourhoods. ...
In mathematics, a topological group G is a group that is also a topological space such that the group multiplication G × G → G and the inverse operation G → G are continuous maps. ...
In mathematical analysis, the Haar measure is a way to assign an invariant volume to subsets of locally compact topological groups and subsequently define an integral for functions on those groups. ...
In mathematics, the integral of a function of one real variable can be regarded as the area of a plane region bounded by the graph of that function. ...
 The circle group T with the Lebesgue measure is an immediate example. For a fixed g in L1(T), we have the following familiar operator acting on the Hilbert space L2(T): In mathematics, the circle group, denoted by T (or in blackboard bold by ), is the multiplicative group of all complex numbers with absolute value 1. ...
The mathematical concept of a Hilbert space (named after the German mathematician David Hilbert) generalizes the notion of Euclidean space in a way that extends methods of vector algebra from the plane and three-dimensional space to spaces of functions. ...
 The operator T is compact. A direct calculation shows that its adjoint T* is convolution with In functional analysis, compact operators on Hilbert spaces are a direct extension of matrices: in the Hilbert spaces, they are the precisely the closure of finite rank operators in the uniform operator topology. ...
 By the commutativity property cited above, T is normal, i.e. T*T = TT*. Also, T commutes with the translation operators. Consider the family S of operators consisting of all such convolutions and the translation operators. S is a commuting family of normal operators. According to spectral theory, there exists an orthonormal basis {hk} that simultaneously diagonalizes S. This characterizes convolutions on the circle. Specifically, we have In functional analysis, a normal operator on a Hilbert space is a continuous linear operator that commutes with its hermitian adjoint : The main importance of this concept is that the spectral theorem applies to normal operators. ...
In functional analysis, compact operators on Hilbert spaces are a direct extension of matrices: in the Hilbert spaces, they are the precisely the closure of finite rank operators in the uniform operator topology. ...
 which are precisely the characters of T. Each convolution is a compact multiplication operator in this basis. This can be viewed as a version of the convolution theorem discussed above. In operator theory, a multiplication operator is a linear operator T defined on some vector space of functions and whose value at a function φ is given by multiplication by a fixed function f. ...
The above example may convince one that convolutions arise naturally in the context of harmonic analysis on groups. For more general groups, it is also possible to give, for instance, a Convolution Theorem, however it is much more difficult to phrase and requires representation theory for these types of groups and the Peter-Weyl theorem . It is very difficult to do these calculations without more structure, and Lie groups turn out to be the setting in which these things are done. Harmonic analysis is the branch of mathematics that studies the representation of functions or signals as the superposition of basic waves. ...
Group representation theory is the branch of mathematics that studies properties of abstract groups via their representations as linear transformations of vector spaces. ...
The Peter-Weyl theorem is a basic result in the theory of harmonic analysis, applying to topological groups that are compact, but are not necessarily abelian. ...
In mathematics, a Lie group, named after Norwegian mathematician Sophus Lie (IPA pronunciation: , sounds like Lee), is a group which is also a differentiable manifold, with the property that the group operations are compatible with the smooth structure. ...
Convolution of measures If μ and ν are measures on the family of Borel subsets of the real line, then the convolution μ * ν is defined by In mathematics, the Borel algebra (or Borel σ-algebra) on a topological space is either of two σ-algebras on a topological space X: The minimal σ-algebra containing the open sets. ...
 In case μ and ν are absolutely continuous with respect to Lebesgue measure, so that each has a density function, then the convolution μ * ν is also absolutely continuous, and its density function is just the convolution of the two separate density functions. // Absolute continuity of real functions In mathematics, a real-valued function f of a real variable is absolutely continuous on a specified finite or infinite interval if for every positive number ε, no matter how small, there is a positive number δ small enough so that whenever a sequence of pairwise disjoint...
In mathematics, the Lebesgue measure is the standard way of assigning a length, area or volume to subsets of Euclidean space. ...
In mathematics, the Radon-Nikodym theorem is a result in functional analysis that states that if a measure Q is absolutely continuous with respect to another sigma-finite measure P then there is a measurable function f, taking values in [0,∞], on the underlying space such that for any...
If μ and ν are probability measures, then the convolution μ * ν is the probability distribution of the sum X + Y of two independent random variables X and Y whose respective distributions are μ and ν. In mathematics, a probability space is a set S, together with a σ-algebra X on S and a measure P on that σ-algebra such that P(S) = 1. ...
In mathematics and statistics, a probability distribution is a function of the probabilities of a mutually exclusive and exhaustive set of events. ...
In probability theory, a random variable is a quantity whose values are random and to which a probability distribution is assigned. ...
Applications Convolution and related operations are found in many applications of engineering and mathematics. - In statistics, as noted above, a weighted moving average is a convolution.
- In probability theory, the probability distribution of the sum of two independent random variables is the convolution of their individual distributions.
- In optics, many kinds of "blur" are described by convolutions. A shadow (e.g. the shadow on the table when you hold your hand between the table and a light source) is the convolution of the shape of the light source that is casting the shadow and the object whose shadow is being cast. An out-of-focus photograph is the convolution of the sharp image with the shape of the iris diaphragm. The photographic term for this is bokeh.
- Similarly, in digital image processing, convolutional filtering plays an important role in many important algorithms in edge detection and related processes.
- In linear acoustics, an echo is the convolution of the original sound with a function representing the various objects that are reflecting it.
- In artificial reverberation (digital signal processing, pro audio), convolution is used to map the impulse response of a real room on a digital audio signal (see previous and next point for additional information).
- In electrical engineering and other disciplines, the output (response) of a (stationary, or time- or space-invariant) linear system is the convolution of the input (excitation) with the system's response to an impulse or Dirac delta function. See LTI system theory and digital signal processing.
- In time-resolved fluorescence spectroscopy, the excitation signal can be treated as a chain of delta pulses, and the measured fluorescence is a sum of exponential decays from each delta pulse.
- In physics, wherever there is a linear system with a "superposition principle", a convolution operation makes an appearance.
- This is the fundamental problem term in the Navier Stokes Equations relating to the Clay Mathematics Millennium Problem and the associated million dollar prize.
- In digital signal processing, frequency filtering can be simplified by convolving two functions (data with a filter) in the time domain, which is analogous to multiplying the data with a filter in the frequency domain.
This article is about the field of statistics. ...
In statistics, autoregressive moving average (ARMA) models, sometimes called Box-Jenkins models after George Box and G. M. Jenkins, are typically applied to time series data. ...
Probability theory is the branch of mathematics concerned with analysis of random phenomena. ...
In mathematics and statistics, a probability distribution is a function of the probabilities of a mutually exclusive and exhaustive set of events. ...
In probability theory, a random variable is a quantity whose values are random and to which a probability distribution is assigned. ...
For the book by Sir Isaac Newton, see Opticks. ...
Look up shape in Wiktionary, the free dictionary. ...
The astounding bokeh of a Helios-40 lens A photograph of jonquil flowers with background bokeh Compare a photograph of jonquil flowers with low background bokeh Bokeh (from the Japanese boke ã¼ã‘, blur) is a photographic term describing the subjective aesthetic qualities of out-of-focus areas in an image produced...
Digital image processing is the use of computer algorithms to perform image processing on digital images. ...
In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite list of well-defined instructions for accomplishing some task that, given an initial state, will terminate in a defined end-state. ...
The goal of edge detection is to mark the points in a digital image at which the luminous intensity changes sharply. ...
Acoustics is a branch of physics and is the study of sound (mechanical waves in gases, liquids, and solids). ...
This article is about audio effect. ...
Digital signal processing (DSP) is the study of signals in a digital representation and the processing methods of these signals. ...
The Impulse response from a simple audio system. ...
In mathematics, an invariant is something that does not change under a set of transformations. ...
A linear system is a model of a system based on some kind of linear operator. ...
The Dirac delta function, introduced by Paul Dirac, can be informally thought of as a function δ(x) that has the value of infinity for x = 0, the value zero elsewhere, and a total integral of one. ...
In electrical engineering, specifically in signal processing and control theory, LTI system theory investigates the response of a linear, time-invariant system to an arbitrary input signal. ...
Digital signal processing (DSP) is the study of signals in a digital representation and the processing methods of these signals. ...
Fluorescence spectroscopy or fluorometry is a type of electromagnetic spectroscopy used for analyzing fluorescent spectra. ...
A magnet levitating above a high-temperature superconductor demonstrates the Meissner effect. ...
A linear system is a model of a system based on some kind of linear operator. ...
In linear algebra, the principle of superposition states that, for a linear system, a linear combination of solutions to the system is also a solution to the same linear system. ...
In fluid dynamics, the Navier-Stokes equations, named after Claude-Louis Navier and George Gabriel Stokes are a set of nonlinear partial differential equations that describe the flow of fluids such as liquids and gases. ...
The Clay Mathematics Institute (CMI) is a private, non-profit foundation, based in Cambridge, Massachusetts, and dedicated to increasing and disseminating mathematical knowledge. ...
See also In the mathematical discipline of linear algebra, a Toeplitz matrix or diagonal-constant matrix, named after Otto Toeplitz, is a matrix in which each descending diagonal from left to right is constant. ...
In linear algebra, a circulant matrix is a special kind of Toeplitz matrix where each row vector is shifted one element to the right relative to the preceding row vector. ...
In statistics, the term cross-correlation is sometimes used to refer to the covariance cov(X, Y) between two random vectors X and Y, in order to distinguish that concept from the covariance of a random vector X, which is understood to be the matrix of covariances between the scalar...
Deconvolution is a process used to reverse the effects of convolution on recorded data. ...
In mathematics, the Dirichlet convolution is a binary operation defined for arithmetic functions; it is of importance in number theory. ...
In mathematics, the Titchmarsh convolution theorem is a result that describes the properties of the support of the convolution of two functions. ...
If is a function and is a natural number, then one can define the convolution power as follows: where * denotes the convolution operation. ...
Analog signal processing is any signal processing conducted on analog signals. ...
External links Look up convolution in Wiktionary, the free dictionary. |
Feeds |
Contact