Misplaced Pages

Symmetric convolution

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages)
This article may be confusing or unclear to readers. Please help clarify the article. There might be a discussion about this on the talk page. (February 2009) (Learn how and when to remove this message)
This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.
Find sources: "Symmetric convolution" – news · newspapers · books · scholar · JSTOR (September 2009)
(Learn how and when to remove this message)

In mathematics, symmetric convolution is a special subset of convolution operations in which the convolution kernel is symmetric across its zero point. Many common convolution-based processes such as Gaussian blur and taking the derivative of a signal in frequency-space are symmetric and this property can be exploited to make these convolutions easier to evaluate.

Convolution theorem

The convolution theorem states that a convolution in the real domain can be represented as a pointwise multiplication across the frequency domain of a Fourier transform. Since sine and cosine transforms are related transforms a modified version of the convolution theorem can be applied, in which the concept of circular convolution is replaced with symmetric convolution. Using these transforms to compute discrete symmetric convolutions is non-trivial since discrete sine transforms (DSTs) and discrete cosine transforms (DCTs) can be counter-intuitively incompatible for computing symmetric convolution, i.e. symmetric convolution can only be computed between a fixed set of compatible transforms.

Mutually compatible transforms

In order to compute symmetric convolution effectively, one must know which particular frequency domains (which are reachable by transforming real data through DSTs or DCTs) the inputs and outputs to the convolution can be and then tailor the symmetries of the transforms to the required symmetries of the convolution.

The following table documents which combinations of the domains from the main eight commonly used DST I-IV and DCT I-IV satisfy f g = h {\displaystyle f*g=h} where {\displaystyle *} represents the symmetric convolution operator. Convolution is a commutative operator, and so f {\displaystyle f} and g {\displaystyle g} are interchangeable.

f g h
DCT-I DCT-I DCT-I
DCT-I DST-I DST-I
DST-I DST-I -DCT-I
DCT-II DCT-I DCT-II
DCT-II DST-I DST-II
DST-II DCT-I DST-II
DST-II DST-I -DCT-II
DCT-II DCT-II DCT-I
DCT-II DST-II DST-I
DST-II DST-II -DCT-I
f g h
DCT-III DCT-III DCT-III
DCT-III DST-III DST-III
DST-III DST-III -DCT-III
DCT-IV DCT-III DCT-IV
DCT-IV DST-III DST-IV
DST-IV DCT-III DST-IV
DST-IV DST-III -DCT-IV
DCT-IV DCT-IV DCT-III
DCT-IV DST-IV DST-III
DST-IV DST-IV -DCT-III

Forward transforms of f {\displaystyle f} , g {\displaystyle g} and h {\displaystyle h} , through the transforms specified should allow the symmetric convolution to be computed as a pointwise multiplication, with any excess undefined frequency amplitudes set to zero. Possibilities for symmetric convolutions involving DSTs and DCTs V-VIII derived from the discrete Fourier transforms (DFTs) of odd logical order can be determined by adding four to each type in the above tables.

Advantages of symmetric convolutions

There are a number of advantages to computing symmetric convolutions in DSTs and DCTs in comparison with the more common circular convolution with the Fourier transform.

Most notably the implicit symmetry of the transforms involved is such that only data unable to be inferred through symmetry is required. For instance using a DCT-II, a symmetric signal need only have the positive half DCT-II transformed, since the frequency domain will implicitly construct the mirrored data comprising the other half. This enables larger convolution kernels to be used with the same cost as smaller kernels circularly convolved on the DFT. Also the boundary conditions implicit in DSTs and DCTs create edge effects that are often more in keeping with neighbouring data than the periodic effects introduced by using the Fourier transform.

References

Category: