Convolution

In the functional analysis, a branch of mathematics, describes the fold, even convolution ( convolvere from the Latin, " roll up " ), a mathematical operator that provides two functions and a third function. The folding can thus be understood as a product of functions.

Is the weighted average of vivid, wherein the weighting is given by. The function value is weighted with. This gives for each a different weighted average. The resulting " overlay " between f and a mirrored and shifted version of g can eg be used to form a moving average.

• 5.1 Algebraic properties
• 5.2 Derivation rule
• 5.3 integration
• 5.4 convolution
• 5.5 Reflection operator
• 5.6 folding dual Lp- functions is continuous
• 5.7 Generalized Young's inequality

• 7.1 Definition
• 7.2 applications

• 8.1 convolution with a function
• 8.2 Convolution of two distributions
• 8.3 Algebraic properties
• 8.4 convolution

Definition

Convolution of functions on Rn

The convolution of two functions is defined by

To keep the definition as general as possible, first one does not reduce the space of admissible functions and calls instead that the integral is well defined for almost all values ​​of.

In the case, that is integrable functions whose improper integral sum is finite, one can show that this condition is always fulfilled. So can the convolution as a product to understand.

Convolution of periodic functions

For periodic functions of a real variable with period is defined as the convolution

Where the integration over an arbitrary interval extends with period length. It is again a periodic function with period.

Convolution of functions on intervals

In the case of a bounded domain of definition are employed and continued to the entire area to perform the convolution can. For this there are several approaches depending on the application.

In general, the convolution for such continuous functions is not well defined. A frequently occurring exceptions are continuous functions with compact support, which are by zero to an integrable function in resumable.

Importance

An obvious interpretation of the one-dimensional convolution is the weight of a dependent of the time function with another. The function value of the weight function at a point indicates how strong the received to past value of the weighted function, ie, in the value of the result function at the time.

The convolution is a suitable model for the description of many physical processes.

Smoothing kernel

A method, a function f "smooth " is to fold with a so-called smoothing kernel. The resulting function F is smooth ( infinitely differentiable ), their support is only slightly larger than that of f, and the variation in the L1 norm can be limited by a given positive constant.

A d -dimensional smoothing kernel (English mollifier ) is an infinitely differentiable function which is non-negative, their means in the closed unit ball B (0, 1) and the integral 1, by appropriate choice of constants c, has.

An example is the smoothing kernel

For this feature you can make more smoothing kernels by a number between 0 and 1 are employed for e:

Smoothing kernels j and j1 / 2

Examples

Be

By folding ( shown in red ) with the smoothing kernel creates a smooth function ( shown in blue ) with compact support, which differs from f in the L1 norm to about 0.4, ie

In the convolution with small e 1/2 we obtain smooth functions that are even closer in the integral norm at f.

Properties of the convolution

Algebraic properties

The amount, together with the convolution a commutative ring that has no neutral element. In detail, that is, the following characteristics apply:

• Commutativity

• Associativity

• Distributivity

• Associativity of scalar multiplication

Derivation rule

It is distributional derivative of. If ( total) is differentiable, then vote distributional derivative and (total ) consistent derivation. Two interesting examples of this are:

• Where the derivative of the delta function is. The derivation can thus be interpreted as convolution operator.
• Wherein the step function is, gives an antiderivative for.

Integration

Are integrable functions and so applies

This is a simple consequence of the Fubini's theorem.

Convolution theorem

Where is the Fourier transform of describes. A similar theorem applies to the Laplace transform. The inversion of the convolution theorem states:

Reflection operator

It is the reflection operator with for all, then applies

• And

Folding dual Lp- functions is continuous

Be with and. Then the convolution is a bounded continuous function. If, as the convolution vanishes at infinity, is therefore a function. This statement is also true if a real Hardy function is and is in BMO.

Generalized Young's inequality

From the Hölder inequality, the generalized Young's inequality follows

For and.

Convolution integral operator as

Be, then you can understand the folding as integral operator with the integral kernel. This means you can define the convolution as an operator by

Interpret. This is a linear operator and more compact, which is also normal. Its adjoint operator is given by

Further, a Hilbert-Schmidt operator.

Discrete convolution

In the digital signal processing and digital image processing has mostly to do with discrete functions that are to be folded together. In this case takes the place of the integral of a sum and one speaks of the discrete-time convolution.

Definition

Be functions with the discrete domain. Then the discrete convolution is defined by

The summation range is the entire domain of both functions. In the case of a bounded domain of definition and usually continued by zeros.

If the domain is finite, then the two functions can also be understood as vectors, respectively. The folding is then added as a matrix-vector product:

With the matrix

With and

If one of periodically under and above the columns continues instead to be completed with zeros, is a circulant matrix, and to obtain the cyclic folding.

Applications

The product of two polynomials, and is, for example the discrete convolution of continued with zeros coefficient sequences. As the resulting infinite series have always only finitely many summands, which are equal to zero. Analogously one defines the product of two formal Laurent series with finite principal part.

A more efficient with respect to the algorithm for computing the calculation of the convolution being the discrete fast convolution, which is based in turn on the Fast Fourier Transform (FFT ) for the efficient computation of the discrete Fourier transform.

Distributions

The convolution was extended by Laurent Schwartz, who is considered the founder of the distribution theory on distributions.

Convolution with a function

Another generalization is the convolution of a distribution with a function. This is defined by

With a translation and reflection operator, which is defined by.

Convolution of two distributions

Let and be two distributions, one having a compact support. Then the convolution between these distributions for all defined by

A more detailed statement ensures that there is a unique distribution with

For everyone.

Algebraic properties

Be, and distributions, then applies

• Commutativity

• Distributivity

• Associativity of scalar multiplication

• Neutral Element Where the delta function is.

Convolution theorem

With the Fourier transform of distributions is called. Let now a tempered distribution and a distribution with compact support. Then, and it is

Topological groups

The two convolution terms can be described and generalized jointly by a general folding concept for complex m- integrable functions on a suitable topological group G with a measure m (eg a locally compact Hausdorff topological group with a hair - degree ):

This folding concept plays a central role in the representation theory of these groups, whose main representatives are the Lie groups. The algebra of integrable functions with the convolution product is the analogue of the group ring of a finite group for compact groups. Further topics are:

• Set of Peter -Weyl
• Harmonic Analysis

Application

• In the optical system a wide variety of image interference can be modeled as a convolution of the original image with a corresponding core. In digital image processing, the convolution is therefore used to simulate such effects. Other digital effects based on the fold. In determining the direction of image edges 3x3 and 5x5 folds are essential.

• For a linear, time-invariant transfer element, the response to excitation is given by convolution of the excitation function with the impulse response of the transmission member. For example, the linear filtering of an electronic signal, the convolution of the original function with the pulse s response

• Folds are used to construct special solutions of certain partial differential equations. If the fundamental solution of the partial differential operator, then a solution of the partial differential equation.

• Diffusion processes can be described by the convolution.

• When X and Y are two stochastically independent random variables with the probability density functions f and g, the density of the sum x y is equal to the convolution.

• In the acoustic ( music), the fold ( with the aid of FFT = fast Fourier transform ) is used for the digital generation of Hall and echoes and for adjusting sound qualities. For this purpose, the impulse response of the room, the sound characteristics you want to take, with the signal that you want to affect, folded.

• In engineering mathematics, and the signal processing input signals ( external influences ) convolved with the impulse response ( response of the system in a Diracimpuls as a signal input, and weight function ) in order to compute the response of an LTI system to any input signal. The impulse response is not to be confused with the step response. The former describes the entirety of the system and a Dirac pulse as input test function, the latter of the whole system and a step function as input test function. The calculations usually do not take place in the time domain but in the frequency domain. These need to be transformed, both the signal and the system behavior descriptive impulse response spectral functions are present in the frequency range, or possibly from the time domain by Fourier transformation or one-sided Laplace transform. The corresponding spectral function of the impulse response is called the frequency response or transfer function.

• In the numerical analysis is obtained by convolution of the box function with the B -spline basis function for the vector space of piecewise polynomials of degree k

• Also in the numerical analysis, the folding for an efficient calculation of the multiplication vielstelliger numbers can be used, since the multiplication is essentially a convolution with subsequent transfer. The complexity of this procedure is linear with close, while the " education process " has quadratic complexity, in which the number of points is. This is worthwhile, despite the additional effort, the case for the Fourier transform ( and its inverse ) is required.

• In hydrology, using the convolution to calculate the produced by a rainfall-runoff event runoff in a catchment area for a given amount and duration of precipitation. For this purpose, the so-called " unit hydrograph " ( unit hydrograph ) - the hydrograph to a unit rainfall of specified duration - convolved with the temporal function of the precipitate.