Talk:Convolution

Derivative of convolution

The Convolution#Differentiation rule section was recently updated from:

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

to

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

I'm pretty sure it was correct the first time.

We know (using Laplace transform#Proof of the Laplace transform of a function's derivative) that:

${\mathcal {L}}\{{\mathcal {D}}f\}=s{\mathcal {L}}\{f\}$

${\mathcal {L}}\{{\mathcal {D}}g\}=s{\mathcal {L}}\{g\}$

and that:

${\begin{aligned}{\mathcal {L}}\{{\mathcal {D}}\{f*g\}\}&=s{\mathcal {L}}\{f*g\}\\&=s{\mathcal {L}}\{f\}{\mathcal {L}}\{g\}\\&={\mathcal {L}}\{{\mathcal {D}}f\}{\mathcal {L}}\{g\}\\&={\mathcal {L}}\{f\}{\mathcal {L}}\{{\mathcal {D}}g\}\end{aligned}}$

Therefore, I've changed it back for now. Oli Filth 15:36, 29 August 2007 (UTC)

Sorry, my mistake, thank you for correcting me :) Crisófilax 16:16, 30 August 2007 (UTC)

Mathworld lists it as the sum of the two terms: http://mathworld.wolfram.com/Convolution.html Can someone look it up in a textbook or verify numerically in Matlab? I'm changing it back to a sum. AhmedFasih (talk) 18:45, 25 February 2008 (UTC)

Update: I tried a simple test (convolving a triangle with a sinusoid, then differentiating) in Matlab, the Mathworld version, D(f*g)=Df*g+f*Dg, is numerically equivalent to the sum of the two expressions previously given here. I am inclined to believe the Mathworld version. AhmedFasih (talk) 18:56, 25 February 2008 (UTC)

A few points:

• I'm aware that Mathworld differs, but I'd stake my life on the fact that it's incorrect on this one.
• See the derivation above for why I think Mathworld is wrong.
• Numerical evaluations of discrete-time convolution can't prove anything about the continuous-time convolution. (The most they can do is indicate what may be the case.)
• However, it would seem you've messed up your experiment; try the code below:

t = [-4*pi:0.01:4*pi];
f = sin(t);
g = zeros(size(t));
g(length(t)/2 - 1 - (0:200)) = linspace(1,0,201);
g(length(t)/2 + (0:200)) = linspace(1,0,201);
Df = f(2:end) - f(1:end-1);
Dg = g(2:end) - g(1:end-1);
Df_g = conv(Df, g);
f_Dg = conv(f, Dg);
fg = conv(f, g);
Dfg = fg(2:end) - fg(1:end-1);
figure
cla, hold on, plot(Dfg, 'b'), plot(f_Dg, 'r'), plot(Df_g, 'k'), plot(Df_g + f_Dg, 'm')

Obviously, if D(f*g) = D(f)*g = f*D(g), then clearly D(f)*g + f*D(g) = 2.D(f)*g, which is what the example above shows.

• Either way, you and I playing around with Matlab is original research; this can't be the basis of anything in the article.

Based on all of this, I'm going to remove the statement of the "convolution rule" until we can get this straightened out. Oli Filth^(talk) 20:04, 25 February 2008 (UTC)

Actually, I'm not. See the ref that Michael Slone cited below, or [1], or p.582 of "Digital Image Processing", Gonzalez + Woods, 2nd. ed. I think we can safely assume that Mathworld is wrong on this one. Oli Filth^(talk) 20:14, 25 February 2008 (UTC)

Yes, MathWorld just flubbed it. The derivative is just another impulse response convolution, and these commute. There's no add involved; someone who was editing that page probably got confused, thinking the * was a mutiply. Dicklyon (talk) 03:56, 26 February 2008 (UTC)

FWIW, Mathworld is now corrected. Oli Filth^(talk) 22:05, 2 April 2008 (UTC)

In the discrete case (if one sums over all of Z), one can directly compute that D(f * g) = (Df * g). Theorem 9.3 in Wheeden and Zygmund asserts (omitting some details) that if f is in L^p and K is a sufficiently smooth function with compact support, then D(f*K) = f*(DK). The proof appears on pp. 146 – 147. I am no analyst, but this appears to support the claim that convolution does not respect the Leibniz rule. Michael Slone (talk) 20:03, 25 February 2008 (UTC)

I feel you, I just looked it up in my Kamen/Heck "Fundamentals of signals and systems," 2nd ed., p. 125 and you are 100% right. Whew, a research problem just got a little bit easier, thanks much. AhmedFasih (talk) 13:11, 26 February 2008 (UTC)

The visualization figure

...in the article is good. But it would be even better if the resultant convoluted function was shown. It can be a little bit hard to image in ones brain what the integral of the product of the two shown functions look like as the two functions slide over each other. I am not new to convolution I just have not used it for seven years or so and went here to see and quickly recap what it is all about. And for such a use case of the article a good figure is very powerfull. -- Slaunger 14:15, 24 October 2007 (UTC)

I Agree that the visualization figure is very powerfull, but am reverting to previous version because I believe that now the Visual explanation of convolution figure is clutterring the article and is essentially a helper to the text. It was cleaner before. This is my opinion, if anyone else disagrees we could discuss. --D1ma5ad (talk) 22:28, 2 March 2008 (UTC)

Ok. I can deal with the revert. (For reference purposes, this was the edit in question.) I think the image really needs to go, though, since it overwhelms the lead. Perhaps someone should write an "explanation" section, and include this image as an accompanying visual aid. siℓℓy rabbit (talk) 21:51, 17 July 2008 (UTC)

I have to agree with the first comment, I can think of no reason not to include the convolved function. It would only take a few more inches of real estate and no additional explanation. —Preceding unsigned comment added by 98.167.177.9 (talk) 03:29, 18 December 2008 (UTC)

Why the time inversion?

The article doesn't explain why g is reversed. What is the point of time inverting it? Egriffin 17:46, 28 October 2007 (UTC)

What do you mean by "the point"? Convolution is defined with time inversion, and as such, happens to have many useful applications. If you don't perform time-inversion, you have cross-correlation instead; which also has lots of useful applications. Oli Filth^(talk) 17:56, 28 October 2007 (UTC)

Or why g instead of f? If you look at it, it makes no difference, since the variable of integration could just as well run the other way, and gets integrated out. In the result, you'll find that if either f or g is shifted to later, then their convolution shifts to later. For this to work this way, the integral needs to measure how they align against each other in opposite order. But think of the variable of integration as some "sideways" dimension, not time, and there's not no "time reversal" to bother you. Or think in terms of the PDF of the sum of two independent random variables: their PDFs convolve, as you can work out, but there is no time involved and no reversal except relative inside the integral. Dicklyon (talk) 16:27, 26 February 2008 (UTC)

It helps to think of $\int _{-\infty }^{\infty }f(\tau )g(t-\tau )\,d\tau$ as a weighted average of the function $g(\tau )$:

• • up to the moment "t", if $f(\tau )$ happens to be zero for all negative values of $\tau$, or
  • centered around the moment "t", if $f(\tau )$ happens to be symmetrical around $\tau =0$.

The weighting coefficient, $f(\tau ),$ for a positive value of $\tau ,$ is the weight applied to the value of function $g$ that occurred $\tau$ units (e.g. "seconds") prior to the moment "t". You may either infer that from the formula, or you may define  $f(\tau )$ that way and infer (i.e. derive) the formula from that definition.

Maybe your point is that something like this needs to be stated in the article, not here.

--Bob K (talk) 12:03, 1 May 2008 (UTC)

Note to associativity

(H * δ') * 1 = (H' * δ) * 1 = (δ * δ) * 1 = δ * 1 = 1

H * (δ' * 1) = H * (δ * 1') = H * (δ * 0) = H * 0 = 0

where H represents heaviside's step function whose derivative is dirac's delta function

• • sorry for the form in which I am presenting this, but I am not well familiarized with input of math equations

intro section

This section is so incredibly abstract! Get a grip, you lofty mathematicians! I much prefer Wolfram's opening sentence: "A convolution is an integral that expresses the amount of overlap of one function g as it is shifted over another function f." -Reddaly (talk) 22:05, 4 August 2008 (UTC)

Good point. I prefer starting out very basic and working up to the "heights". Then readers can drop out when they find themselves outside their own comfort zone.

--Bob K (talk) 01:12, 6 August 2008 (UTC)

Comments

• I would like to see some discussion of the convolution in several variables, since this is important in areas of mathematics outside signal processing, such as partial differential equations and harmonic analysis. For instance, solutions to a linear pde such as the heat equation can be obtained on suitable domains by taking a convolution with a fundamental solution. I also note that some of the applications listed in the article clearly require convolutions of several variables. However, the current article focuses exclusively on the one-variable case. I think this is a rather serious limitation.
• Nothing is said here about the domain of definition, merely that ƒ and g are two "functions". I would like to see some discussion of the fact that the convolution is well-defined (by the formula given) if ƒ and g are two Lebesgue integrable functions (i.e., L¹ functions). Moreover, if just ƒ is L¹ and g is L^p, then ƒ*g is L^p.
• Furthermore, continuing the above comment, some of the basic analytic properties of convolution should also be covered. Among these are the estimate that if ƒ ∈ L¹(R^d) and g ∈ L^p(R^d), then

$\|f\ast g\|_{p}\leq \|f\|_{1}\|g\|_{p}.$

From this estimate, a great many important results follow on the convergence in the mean of convolutions of functions. It can be used, for instance, to show that smooth functions with compact support are dense in the L^p spaces. The process of smoothing a function by taking a convolution with a mollifier also deserves to be included as this has applications, not only in proving the aforementioned result, but is also a ubiquitous principle used in applications (such as Gaussian blur).

• I also feel that a section should be created which at least mentions convolution of a function with a distribution (and related definitions), since these are significant for applications to PDE where one needs to be able to make sense of expressions such as ƒ*δ where δ is the delta function. The article itself seems to treat convolution with a distribution as well-defined implicitly. I would prefer to have this made explicit, as well as the precise conditions under which the convolution may be defined.

I'm not sure how to reorganize the article. I am leaning towards an expansion of the "Definition" section to include the case of several variables, and moving some of the discussion particular to signal processing somewhere else (I'm not sure where yet). The definition section should, I think, be followed by a "Domain of definition" section containing the details of what sort of functions (and distributions) are allowed. This should probably be followed by "Properties" (I think the circular and discrete convolutions should be grouped together with the other generalizations given towards the end of the article). I would then like to expand the "Properties" section. siℓℓy rabbit (talk) 14:03, 16 July 2008 (UTC)

I would prefer the article to build up to generalizations, like several variables. Many important points can be made first, with just the one-variable case. Fourier transforms can be defined in multiple dimensions, but we don't begin the article with that.

--Bob K (talk) 21:29, 17 July 2008 (UTC)

It is my intention to build up to generalizations (such as the convolution of a function with a distribution). However, I don't think the convolution on R^d is a very substantial generalization. The discrete version immediately following the "Definition" section is much more substantial, and probably less often used. siℓℓy rabbit (talk) 22:53, 17 July 2008 (UTC)

Not that it matters, but I would have guessed that the discrete version is the most commonly used form in this "digital age" of FIR filtering.

--Bob K (talk) 01:07, 18 July 2008 (UTC)

References

Some additional references I plan to use in my improvements of the article are:

• Sobolev, V.I. (2001) [1994], "Convolution of functions", Encyclopedia of Mathematics, EMS Press.
• Hörmander, L. (1983), The analysis of linear partial differential operators I, Grundl. Math. Wissenschaft., vol. 256, Springer, ISBN 3-540-12104-8, MR0717035.
• Stein, Elias; Weiss, Guido (1971), Introduction to Fourier Analysis on Euclidean Spaces, Princeton University Press, ISBN 0-691-08078-X.
• Titchmarsh, E (1948), Introduction to the theory of Fourier integrals (2nd ed.) (published 1986), ISBN 978-0828403245.

I plan to add more to this list as I progress. siℓℓy rabbit (talk) 15:07, 16 July 2008 (UTC)

Cyclic discrete convolution

I think this notation is too cryptic:

$c_{k}=\sum _{i+j\equiv k\mod n}a_{i}b_{j}.$

Please keep in mind that this is an encyclopedia, and we have plenty of space.

--Bob K (talk) 15:46, 18 July 2008 (UTC)

I think that notation is extremely clarifying; we should probably add it alongside the more traditional notation, since we have room. Dicklyon (talk) 16:00, 18 July 2008 (UTC)

The "ugly" one, i.e.:

$c_{k}=\sum _{i=0}^{k}a_{i}b_{k-i}+\sum _{i=1}^{n-k-1}a_{k+i}b_{n-i}.$

is understandable to me. It's what you get if you periodically extend the b sequence with period n, reverse it in time, delay it by k, and then sum the product of the sequences over the extent of a (or equivalently to infinity).

So a more elegant way of making the point without losing clarity is:

$c[k]\,$	$=(a*b_{n})_{k}\,$      for k=0,1,2,...,n-1
	$=\sum _{i=0}^{n-1}a[i]\cdot b_{n}[k-i]\,$

where b_n is the periodic extension of b:

$b_{n}[i]\ {\stackrel {\mathrm {def} }{=}}\ \sum _{m=-\infty }^{\infty }b[i-mn]=\sum _{m=-\infty }^{\infty }b[i+mn].$

Those who already understand normal convolution will be able to leverage that insight to help them understand this. Those who don't understand normal convolution either shouldn't be here at all, or they should be inspired to go back and brush up on it.

--Bob K (talk) 20:44, 18 July 2008 (UTC)

Why not just leverage the circularity of the mod function at least:

$c_{k}=\sum _{i=0}^{n}a[i]\cdot b[(k-i)\mod {n}]$

Dicklyon (talk) 21:26, 18 July 2008 (UTC)

That works too. But since this whole article is about convolution, it's better to reinforce that relationship, IMHO. Since they are not mutually exclusive we can, and probably should, mention both explanations. Let the reader pick his own poison.

--Bob K (talk) 21:34, 18 July 2008 (UTC)

I think the section looks pretty good now. One thing I would like is a good reference for the periodization of the discrete functions. A text on Fourier series seems a natural place to look. I'll see what I can dig up. siℓℓy rabbit (talk) 03:44, 19 July 2008 (UTC)

Translation invariance

I have added a short and rough section on translation invariance. Obviously more should be said, since this is "the" most important property of convolutions. Hopefully we can iterate to get this new addition of mine into a more reasonable shape. siℓℓy rabbit (talk) 16:12, 24 July 2008 (UTC)

"Visual explanation of convolution" is wrong!

At first glance, I thought it is correct. But last two figures are actually wrong. Considering the expression:

$\int f(\tau )\cdot g(t-\tau )\,d\tau$

As the expression suggests, ƒ(τ) and g(t - τ) coincide—g(t - τ) is weighting ƒ(τ). But look at the figures in question, ƒ(1) and g(t - 1) don't coincide! This mathematical expression is all about, of a specific interval, giving g as a weighing function of ƒ. So it is not just sliding g, but it is patching g to ƒ like an adhesive bandage. Visual explanation should reflect this fact. The annotation will also need to be revised a bit.--Shigerello (talk) 12:08, 23 December 2008 (UTC)

I'm not sure I understand. $f(1)$ and $g(t-1)$ coincide only when $t=2$. For all other values of t, there is no coincidence. Oli Filth^{(talk|contribs)} 18:05, 23 December 2008 (UTC)

First of all, sorry for my lack of knowledge. I shouldn't have rushed to post my thought without taking it well. I mistakenly imagined that, in every snapshot of sliding g, the calculation is focused on a specific point of ƒ and g (not quite, but like impulse response). But actually, in every snapshot, the calculation is done between whole waveform of g (t as variable) and a specific point of ƒ. And integration to sum all calculated snapshot waveforms... Visualization is not wrong, solely it's my mistake. I think this part should be remove to not let people take in this wrong concept. What do you say?--Shigerello (talk) 19:30, 23 December 2008 (UTC)