Citizendia
Your Ad Here

For the usage in formal language theory, see convolution (computer science). In Computer science, specifically Formal languages a convolution is defined as follows Let ∑ be an alphabet # a symbol not in ∑

In mathematics and, in particular, functional analysis, convolution is a mathematical operator that takes two functions f and g and produces a third function that is typically viewed as a modified version of one of the original functions. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and For functional analysis as used in psychology see the Functional analysis (psychology article In Mathematics, an operator is a function which operates on (or modifies another function The Mathematical concept of a function expresses dependence between two quantities one of which is given (the independent variable, argument of the function Convolution is a mathematical tool with applications including statistics, computer vision, image and signal processing, and differential equations. Statistics is a mathematical science pertaining to the collection analysis interpretation or explanation and presentation of Data. Computer vision is the science and technology of machines that see Image processing is any form of Signal processing for which the input is an image such as photographs or frames of video the output of image processing can be either an image Signal processing is the analysis interpretation and manipulation of signals Signals of interest include sound, images, biological signals such as A differential equation is a mathematical Equation for an unknown function of one or several variables that relates the values of the

In electrical engineering, the third function is the output of a linear time-invariant system. Electrical engineering, sometimes referred to as electrical and electronic engineering, is a field of Engineering that deals with the study and application of LTI system theory or linear time-invariant system theory is a theory in the field of Electrical engineering, specifically in circuits Signal processing The function being modified is the input, and the other is the system's time-response to a brief but strong impulse (see impulse response). Input is the term denoting either an entrance or changes which are inserted into a System and which activate/modify a Process. The impulse response of a system is its output when presented with a very brief input signal an impulse At any given moment, the output is an accumulated effect of all the prior values of the input function, with the most recent values typically having the most influence (expressed as a multiplicative factor). The impulse response function provides that factor as a function of the elapsed time since each input value occurred.

Visual explanation of convolution. Make each waveform a function of the dummy variable τ. Time-invert one of the waveforms and add t to allow it to slide back and forth on the τ-axis while remaining stationary with respect to t. Finally, start the 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. If the stationary waveform is a unit impulse, the end result would be the original version of the sliding waveform, as it is time-inverted back again because the right edge hits the unit impulse first and the left edge last. This is also the reason for the time-inversion in general, as complex signals can be thought to consist of unit impulses.
Visual explanation of convolution. Make each waveform a function of the dummy variable τ. In Mathematics, and in other disciplines involving Formal languages including Mathematical logic and Computer science, a free variable is a Time-invert one of the waveforms and add t to allow it to slide back and forth on the τ-axis while remaining stationary with respect to t. Finally, start the 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. If the stationary waveform is a unit impulse, the end result would be the original version of the sliding waveform, as it is time-inverted back again because the right edge hits the unit impulse first and the left edge last. The Dirac delta or Dirac's delta is a mathematical construct introduced by the British theoretical physicist Paul Dirac. This is also the reason for the time-inversion in general, as complex signals can be thought to consist of unit impulses.

Contents

Definition

The convolution of f\, and g\, is written f * g \,. 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:

(f * g )(t) = \int_{-\infty}^{\infty} f(\tau) g(t - \tau)\, d\tau.

While the symbol t\, is used above, it need not represent the time domain. In Mathematics, an integral transform is any transform T of the following form (Tf(u = \int_{t_1}^{t_2} K(t u\ f(t\ dt But in that context, the convolution formula can be described as a weighted average of the function g\, at the moment t.\,  For \tau > 0,\,  f(\tau)\, is the weight/multiplier to be applied to the value that function g\, had \tau\, seconds prior to that moment. (And for \tau < 0,\,  it is the weight/multiplier to be applied to the value that function g\, has |\tau|\, seconds after the moment t.\,)  The time-reversal of one function relative to the other in the convolution integral leads to that interpretation. Conversely, defining a weighting function that way leads to the time-reversal. (LTI system theory)

Circular convolution

When g(t)\, is periodic, with period T,\, it can be shown that:

(f * g )(t) = \int_{t_o}^{t_o+T} \left[\sum_{k=-\infty}^{\infty} f(\tau - kT)\right] g(t - \tau)\ d\tau,\,

where to is an arbitrary parameter. LTI system theory or linear time-invariant system theory is a theory in the field of Electrical engineering, specifically in circuits Signal processing The summation is called a periodic extension of the function f.\,  If g\, is a periodic extension of another function, then (f * g )(t)\, is known as a circular, cyclic, or periodic convolution. A circular Convolution of two functions is defined in terms of the periodic extension of one or both functions As shown here, it can be computed by integration on either an infinite domain or a finite domain.

Discrete convolution

For discrete functions, the convolution operation is given by:

(f * g)(n) = \sum_{m=-\infty}^{\infty} {f[m]\cdot g[n - m]} \,

When multiplying two polynomials, the coefficients of the product are given by the convolution of the original coefficient sequences, extended with zeros where necessary to avoid undefined terms. In Mathematics, a polynomial is an expression constructed from Variables (also known as indeterminates and Constants using the operations In Mathematics, a sequence is an ordered list of objects (or events

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). In Topology and related branches of Mathematics, a Topological space is called locally compact if roughly speaking each small portion of the space looks In Mathematics, a topological group is a group G together with a topology on G such that the group's binary operation and the

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

Fast convolution algorithms

When f[n]\, is a finite duration function of length N, the formula above requires N arithmetic operations per output value and N2 operations for N outputs. That can be significantly reduced with any of several fast algorithms. Digital signal processing and other applications typically use fast convolution algorithms to increase the speed of the convolution to O(N log N) complexity. Digital signal processing ( DSP) is concerned with the representation of the signals by a sequence of numbers or symbols and the processing of these signals

The most common fast convolution algorithms use fast Fourier transform (FFT) algorithms via the circular convolution theorem. In Mathematics, the discrete Fourier transform (DFT is one of the specific forms of Fourier analysis. Specifically, the circular convolution of two finite-length sequences is found by taking an FFT of each sequence, multiplying pointwise, and then performing an inverse FFT. A circular Convolution of two functions is defined in terms of the periodic extension of one or both functions Convolutions of the type defined above are then efficiently implemented using that technique in conjunction with zero-extension and/or discarding portions of the output.

There are also many other fast convolution algorithms that do not employ FFTs per se, such as number-theoretic transform algorithms. The number-theoretic transform ( NTT) is similar to the Discrete Fourier transform, but operates with Modular arithmetic on Integers instead of

Properties

Commutativity

f * g = g * f \,

Associativity

f * (g * h) = (f * g) * h \,

Distributivity

f * (g + h) = (f * g) + (f * h) \,

Identity element

f * \delta = \delta * f = f \,

where δ denotes the Dirac delta

Associativity with scalar multiplication

a (f * g) = (a f) * g = f * (a g) \,

for any real (or complex) number a\,. In Mathematics, commutativity is the ability to change the order of something without changing the end result 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 In Mathematics, an identity element (or neutral element) is a special type of element of a set with respect to a Binary operation on that The Dirac delta or Dirac's delta is a mathematical construct introduced by the British theoretical physicist Paul Dirac.

Differentiation rule

\mathcal{D}(f * g) = \mathcal{D}f * g = f * \mathcal{D}g \,

where \mathcal{D}f denotes the derivative of f or, in the discrete case, the difference operator \mathcal{D}f(n) = f(n+1) - f(n). In Calculus, a branch of mathematics the derivative is a measurement of how a function changes when the values of its inputs change In Mathematics, a difference operator maps a function, f ( x) to another function f ( x + a) &minus f ( x 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.

Convolution theorem

The convolution theorem states that

\mathcal{F}(f * g) = k \left[\mathcal{F} (f)\right] \cdot \left[\mathcal{F} (g)\right]

where \mathcal{F}(f)\, denotes the Fourier transform of f, and k is a constant which depends upon the specific normalization of the Fourier transform (e. In Mathematics, the convolution theorem states that under suitableconditions the Fourier transform of a Convolution is the Pointwise product This article specifically discusses Fourier transformation of functions on the Real line; for other kinds of Fourier transformation see Fourier analysis and The concept of a normalizing constant arises in Probability theory and a variety of other areas of Mathematics. g. , k = 1 if \mathcal{F}\left[f(x)\right]\equiv\int^\infty_{-\infty}f(x)\exp(\pm 2 \pi i x \xi)dx). Versions of this theorem also hold for the Laplace transform, two-sided Laplace transform, Z-transform and Mellin transform. In Mathematics, the Laplace transform is one of the best known and most widely used Integral transforms It is commonly used to produce an easily soluble algebraic In Mathematics, the two-sided Laplace transform or bilateral Laplace transform is an Integral transform closely related to the Fourier transform In Mathematics and Signal processing, the Z-transform converts a discrete Time-domain signal which is a Sequence of real 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. The Titchmarsh convolution theorem is named after Edward Charles Titchmarsh.

Convolution inverse

Main article: Deconvolution

Many functions have an inverse element, f(-1), which satisfies the relationship:

f^{(-1)} * f = \delta \,

These functions form an abelian group, with the group operation being convolution. In Mathematics, deconvolution is an algorithm-based process used to reverse the effects of Convolution on recorded data In Mathematics, the idea of inverse element generalises the concepts of negation, in relation to Addition, and reciprocal, in relation to An abelian group, also called a commutative group, is a group satisfying the additional requirement that the product of elements does not depend on their order (the Group theory is a mathematical discipline the part of Abstract algebra that studies the Algebraic structures known as groups.

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 on G, then we can define their convolution by

(f * g)(x) = \int_G f(y)g(xy^{-1})\,dm(y) \,

The circle group T with the Lebesgue measure is an immediate example. In Mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element 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 In Topology and related branches of Mathematics, a Topological space is called locally compact if roughly speaking each small portion of the space looks In Topology and related branches of Mathematics, a Hausdorff space, separated space or T2 space is a Topological space In Mathematics, a topological group is a group G together with a topology on G such that the group's binary operation and the In Mathematical analysis, the Haar measure is a way to assign an "invariant volume" to subsets of Locally compact topological groups and subsequently define In Mathematics, the Integral of a non-negative function can be regarded in the simplest case as the Area between the graph of In Mathematics, the circle group, denoted by T (or in Blackboard bold by \mathbb T is the multiplicative group of all Complex For a fixed g in L1(T), we have the following familiar operator acting on the Hilbert space L2(T):

T f(x) = \frac{1}{2 \pi} \int_{\mathbb{T}} f(y) g( x - y) dy.

The operator T is compact. This article assumes some familiarity with Analytic geometry and the concept of a limit. In Functional analysis, Compact operators on Hilbert spaces are a direct extension of matrices in the Hilbert spaces they are precisely the closure of Finite A direct calculation shows that its adjoint T* is convolution with

\bar{g}(-y).

By the commutativity property cited above, T is normal, i. In Mathematics, especially Functional analysis, a normal operator on a Hilbert space H (or more generally in a C* algebra) is a 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. In Functional analysis, Compact operators on Hilbert spaces are a direct extension of matrices in the Hilbert spaces they are precisely the closure of Finite This characterizes convolutions on the circle. Specifically, we have

h_k (x) = e^{ikx},\;

which are precisely the characters of T. In Mathematics, a character is (most commonly a special kind of function from a group to a field (such as the Complex numbers) Each convolution is a compact multiplication operator in this basis. In Operator theory, a multiplication operator is a Linear operator T defined on some vector space of functions and whose value at a function This can be viewed as a version of the convolution theorem discussed above.

The above example may convince one that convolutions arise naturally in the context of harmonic analysis on groups. Harmonic analysis is the branch of Mathematics that studies the representation of functions or signals as the superposition of basic Waves It investigates and generalizes 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. In the mathematical field of Representation theory, group representations describe abstract groups in terms of Linear transformations of In Mathematics, the Peter–Weyl theorem is a basic result in the theory of Harmonic analysis, applying to Topological groups that are Compact 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. In Mathematics, a Lie group (ˈliː sounds like "Lee" is a group which is also a Differentiable manifold, with the property that the group

Convolution of measures

If μ and ν are measures on the family of Borel subsets of the real line, then the convolution μ * ν is defined by

(\mu * \nu)(A) = (\mu \times \nu)(\{\, (x,y) \in \mathbb{R}^2 \,:\, x+y \in A \,\}).

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. In Mathematics, the Borel algebra (or Borel &sigma-algebra) on a Topological space X is a &sigma-algebra of Subsets of In Mathematics, one may talk about absolute continuity of functions and absolute continuity of measures, and these two notions are closely connected In Mathematics, the Lebesgue measure, named after Henri Lebesgue, is the standard way of assigning a Length, Area or Volume to In Mathematics, the Radon–Nikodym theorem is a result in Functional analysis that states that given a measurable space ( X,&Sigma if a

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 ν. A probability space, in Probability theory, is the conventional Mathematical model of Randomness. In Probability theory and Statistics, a probability distribution identifies either the probability of each value of an unidentified Random variable In Probability theory, to say that two events are independent intuitively means that the occurrence of one event makes it neither more nor less probable that the other A random variable is a rigorously defined mathematical entity used mainly to describe Chance and Probability in a mathematical way

Applications

Convolution and related operations are found in many applications of engineering and mathematics.

See also

External links

MathWorld is an online Mathematics reference work created and largely written by Eric W

Dictionary

convolution

-noun

  1. Something that is folded or twisted.
  2. Any of the folds on the surface of the brain.
  3. The shape of something rotating; a vortex.
  4. (mathematics) A form of moving average.
  5. (computing) A function that puts elements of multiple strings into arrays.
© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic