Talk:Convolution/Archive 2

This is an archive of past discussions about Convolution. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

Archive 1

Archive 2

Archive 3

Archive 4

Start off easy, then push the reader over a cliff

Another lousy wikipedia article written by self-claimed experts to wank on about how they edited a wikipedia article.

The first paragraph is not bad.

The second paragraph, about the use of convolution in other groups is total wiki bullshit.

Put that crap down lower in the article. I don't care you have a Ph.D and that you are correct. Are you writing for more jackholes or for people that actually want to learn?

Similarly, get rid of stupid animations that have no ability to stop and let the person read.

DEMAND ATTENTION DEMAND ATTENTION DEMAND ATTENTION.

I made an animation, and regardless of how distracting it is, I will force you to read it.

In summation, typical crappy wikipedia article.

68.106.47.124 (talk) 17:35, 6 March 2012 (UTC)

The lead of the article is supposed to provide a capsule summary of the article. It isn't necessarily supposed to be the easiest part. Since much of the article does focus on generalizations of the convolution, the second paragraph is appropriate and roughly proportional to the prominence of this topic in the article. It's true that there should be more detail in the earlier sections on things that a larger group of readers might be interested in, like applications to image processing. These can then also be mentioned in the lead, which has ample room for expansion. At this point, I have no opinion about the animation. I seem to recall lobbying for its removal in the past whilst other editors have favored it's inclusion. I think it should probably stay, at least pending a wider discussion. Sławomir Biały (talk) 18:53, 6 March 2012 (UTC)

I don't understand the ambivalence about the .gif animation. I think it is clearly a positive feature of the article, and an excellent example of what computer-based learning can offer that hardcover books cannot. A pause button would also be a nice, but minor, addition. Perhaps someday Wikipedia will also figure out how to write articles on multiple levels... high school, undergrad, & grad. Good things take time.--Bob K (talk) 12:27, 10 March 2013 (UTC)

Lead images

The lead images to this article are not good. They are so wide that they completely dominate the lead, squashing all of the text aside. Moreover, the new captions I think are worse. They are much less succinct that the original captions, and dwell on things like the difference between cross-correlation and convolution, which the images don't even illustrate. If someone wants to write an examples section that includes these (or other) images, along with detailed explanations, that might be better. Sławomir Biały (talk) 01:50, 12 March 2013 (UTC)

I think the .gif "movies" are not helpful at their current location. They would be more helpful with the formulas (Definition section) that they serve to illustrate. The reason I brought up cross-correlation is so that I could equate

g(t-\tau )

to

g(\tau -t),

which is easier to grasp. It was awkward, I agree, but maybe less awkward than

g(t-\tau ).

That was the hope. I also thought it important to say how

t

is defined. But all those details became cumbersome. I think it is better now. --Bob K (talk) 04:25, 12 March 2013 (UTC)

Examples of convolution

I saw the wiki page, but I couldn't find any examples using actual numbers evaluating the formula. Could you give some examples of convolution, please? Mathijs Krijzer (talk) 22:44, 9 March 2013 (UTC)

The two .gif files at the top of the article are doing convolutions with actual numbers. It doesn't get much better than that.

But if you want to "get your own hands dirty", I suggest you download Octave (it's free), and play around with the conv function. You might find some of the info at http://en.wikipedia.org/wiki/User_talk:Olli_Niemitalo#Window_function helpful for getting started. I'm using version 3.6.2. Version 3.4 has an installer, but I found that Octave and qtOctave don't need to be installed. I think the word for that property is "portable".

There are four instances of the conv() function in this script: http://commons.wikimedia.org/wiki/File:Circular_convolution_example.png#Octave_script

They use actual numbers generated elsewhere in the script.

Similarly, there are two instances in this script: http://commons.wikimedia.org/wiki/File:Overlap-save_algorithm.png#Octave_script

--Bob K (talk) 00:44, 10 March 2013 (UTC)

Yes, but the .gif files don't explain all the formulas step by step. What does this mean?:

In other words, compute a sliding, weighted-average of function $f(\tau )$ , where the weighting function is $g(-\tau ).$
The resulting waveform (not shown here) is the convolution of functions f and g. If f(t) is a unit impulse, the result of this process is simply g(t), which is therefore called the impulse response.

--Mathijs Krijzer (talk) 13:42, 10 March 2013 (UTC)

Sorry... it took me a while to realize that you've raised a very important point. The article needs to say more about topics such as Dirac_delta_function#Translation and LTI_system_theory#Impulse_response_and_convolution. In the meantime, maybe those links will help you. --Bob K (talk) 19:24, 11 March 2013 (UTC)

It already does, in plain sight actually, in more than one way. Same goes for the examples listed below. Usual problem with articles like this. Engineers can't read math and math people don't care to translate. Mct mht (talk) 21:32, 18 March 2013 (UTC)

Definition

The convolution of f and g is written f∗g, using an asterisk or star. 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)\ \ \,$	${\stackrel {\mathrm {def} }{=}}\ \int _{-\infty }^{\infty }f(\tau )\,g(t-\tau )\,d\tau$
	$=\int _{-\infty }^{\infty }f(t-\tau )\,g(\tau )\,d\tau .$ (commutativity)

Domain of definition

The convolution of two complex-valued functions on R^d

(f*g)(x)=\int _{\mathbf {R} ^{d}}f(y)g(x-y)\,dy

is well-defined only if f and g decay sufficiently rapidly at infinity in order for the integral to exist. Conditions for the existence of the convolution may be tricky, since a blow-up in g at infinity can be easily offset by sufficiently rapid decay in f. The question of existence thus may involve different conditions on f and g.

Circular discrete convolution

When a function g_N is periodic, with period N, then for functions, f, such that f∗g_N exists, the convolution is also periodic and identical to:

(f*g_{N})[n]\equiv \sum _{m=0}^{N-1}\left(\sum _{k=-\infty }^{\infty }{f}[m+kN]\right)g_{N}[n-m].\,

Circular convolution

When a function g_T is periodic, with period T, then for functions, f, such that f∗g_T exists, the convolution is also periodic and identical to:

(f*g_{T})(t)\equiv \int _{t_{0}}^{t_{0}+T}\left[\sum _{k=-\infty }^{\infty }f(\tau +kT)\right]g_{T}(t-\tau )\,d\tau ,

where t_o is an arbitrary choice. The summation is called a periodic summation of the function f.

Discrete convolution

For complex-valued functions f, g defined on the set Z of integers, the discrete convolution of f and g is given by:

(f*g)[n]\ {\stackrel {\mathrm {def} }{=}}\ \sum _{m=-\infty }^{\infty }f[m]\,g[n-m]

=\sum _{m=-\infty }^{\infty }f[n-m]\,g[m].

(commutativity)

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; this is known as the Cauchy product of the coefficients of the two polynomials.

Deleted References to GNU C-Graph

The following is re-posted, here, on advice from PamD noted at the end of this section.

Long before I wrote the proposed article "GNU C-Graph", I included references under the articles Convolution theorem and Convolution for the benefit of students and their professors teaching and learning about convolution. These references were removed by MrOllie and Hu12. Notwithstanding my belief that GNU C-Graph meets the WP:Notability criteria, Mark viking pointed out "external links aren't required to be WP notable, just relevant".

Most reasonable people would agree that removing the reference to the only software that easily demonstrates the convolution theorem would be a disservice to the public. The text of the references reads:

Under Convolution#External_links:

GNU C-Graph, a free software package for visualizing the convolution theorem, and displaying signals with their spectral plots.

Under Convolution_theorem#Additional_resources:

GNU C-Graph, a free software package for demonstrating the convolution theorem, and displaying signals with their spectral plots.

No doubt some WP:AGF administrator will recognise the educational value and reinstate the references for the benefit of the public.Visionat (talk) 14:16, 24 April 2013 (UTC)

Visionat, the places for these discussions are Talk:Convolution theorem and Talk:Convolution, not your own talk page. Those pages are also where you should have suggested the addition of links to the software you have written, bearing in mind WP:COI: to avoid any interpretation that you are promoting your own software, you should suggest the addition of the links on the talk page and allow independent editors (not necessarily administrators) to decide whether the links are an asset to the articles. If you look at WP:COIU, you will see that an editor with a possible conflict of interest may "make edits where there is clear consensus on the talk page (though it is better to let someone else do it)". That's the way to go. It's nothing personal, so your talk page is not the place for the discussion. I hope that helps. PamD

Discrete convolution

The formulae are wrong in that the limits of m may be finite, not infinite. A good example of this is in Numerical smoothing and differentiation. Petergans (talk) 08:47, 5 May 2013 (UTC)

To get the discrete convolution of finite sequences, you must extend those sequences by zero outside their domain. In fact, it even seems to be necessary to do this in the formulae in the article that you linked to. Sławomir Biały (talk) 11:12, 5 May 2013 (UTC)

I have clarified the text of that article. The finite convolution formula there is now written explicitly as

(C\otimes y)_{j}\ =\sum _{i=-(m-1)/2}^{i=(m-1)/2}C_{i}\,y_{j-i}

,

m is a finite odd integer. Petergans (talk) 15:37, 5 May 2013 (UTC)

If the sequence y has length m, then you need to extend by zero whenever

j-i>(m-1)/2

. Sławomir Biały (talk) 18:45, 5 May 2013 (UTC)

No, y has length n, n>>m. The formula is the exact counterpart of the (continuous) definition, but with discrete values for i and finite limits for the summation. The number of calculated convolution points is equal to n-m+1, so this formula should only be used when n>>m. You can see an application in spectroscopic line shape#derivative spectroscopy: I used m=5 and n=100 to construct the diagram.Note that int(m/2) points at the start and end of the result are undefined; one could use zero extensions for those points, but that would be arbitrary and unnecessary. In the diagram only the central data from a wider dataset are shown, so that the undefined points are outside the plot. Petergans (talk) 08:54, 6 May 2013 (UTC)

Ok, but you're still going to run into trouble when

j-i

is out of bounds. It seems quite strange to argue that the present article is wrong by comparison with such a manifestly inadequate definition. Sławomir Biały (talk) 18:45, 7 May 2013 (UTC)

I gotta say, Sławomir Biały, you're very patient. Mct mht (talk) 19:06, 7 May 2013 (UTC)

The point is that j-i does not go out of bounds, because the formula is only to be applied when this quantity is in bounds. Numerical smoothing and differentiation has been used for many years, since Savizki and Golay published tables of convolution coefficients in 1964 It is accepted that the outermost points are undefined. Look at the way smoothing using a 5-point quadratic function is used at the start of the data, y.

{\begin{pmatrix}{Y_{3}}\\{Y_{4}}\\\end{pmatrix}}={\begin{pmatrix}{-3/35}&{12/35}&{17/35}&{12/35}&{-3/35}&0\\0&{-3/35}&{12/35}&{17/35}&{12/35}&{-3/35}\\\end{pmatrix}}{\begin{pmatrix}{y_{1}}\\{y_{2}}\\{y_{3}}\\{y_{4}}\\{y_{5}}\\{y_{6}}\\\end{pmatrix}}.

The values of Y₁ and Y₂ are undefined. Similarly the last 2 points in the series will be undefined. The points which are undefined when using this formula can be obtained by using other formulae. User:Sławomir Biały, your objections are based on hypothetical circumstances which do not occur in practice because everyone should know, as you do, that they are invalid.. Petergans (talk) 11:32, 9 May 2013 (UTC)

"The point is that j-i does not go out of bounds, because the formula is only to be applied when this quantity is in bounds." — Then why does it matter so much how the convolution is defined, if the only cases you object to are never going to be applied? The mathematical definition of convolution certainly requires the group structure of the underlying space (in this case the group of integers). There is no applicable notion of "out of bounds" in the mathematical sense. Of course, which bounds are reasonable will depend on the application, but the same is true any time a mathematical device is used in numerical work. Also, I should add that the mathematical notion of convolution (even fairly sophisticated versions in locally compact groups) predate the source that you just cited by at least 15 years. Sławomir Biały (talk) 12:21, 9 May 2013 (UTC)

If I read the first displayed formula correctly, it's wrong, unless C has length ≤ m. The length of y is irrelevant. The formula with infinite limits is correct; if either f or g has finite support, the limits can be made finite. — Arthur Rubin (talk) 18:30, 9 May 2013 (UTC)

What I object to is the sentence "The convolution of two finite sequences is defined by extending the sequences to finitely supported functions on the set of integers." Extending the sequence is merely one way of dealing with the end-points which I describe above as undefined. I can give others if need be. The issue with infinite limits is a lack generality, particularly in view of the widespread use of the formula above when using Savitzki-Golay coefficients (yes, I know that the idea goes back into the 19th. century, it's a simple application of least-squares theory). It seems to me that there are two classes of application: f and g may be either functions or vectors. Let's make this explicit in the article and close this discussion. Agreed? Petergans (talk) 19:20, 9 May 2013 (UTC)

I can see your point about "is defined"; perhaps replace by "can be computed by", or replace the infinite sums by summing only over where the coeficients are defined. It makes no difference whether f is a function with finite support or a vector, and the fact that it makes no difference is important. Arthur Rubin (talk) 19:49, 9 May 2013 (UTC)

Having looked at the Savitzki-Golay article that you seem to think is the final authority on convolution, it's clear that the authors have confused the convolution with the cross-correlation. While this is not directly germane to the discussion, it does rather cast doubt on whether that can be considered a reliable source on Fourier analysis. Sławomir Biały (talk) 19:57, 9 May 2013 (UTC)

This is insulting. See my book "Data fitting in the chemical sciences", section 9.3, p. 202, "Convolution and cross-correlation". Petergans (talk) 10:10, 10 May 2013 (UTC)

I think folks are arguing a bit at cross purposes. There are different kinds of convolution being discussed here. For continuous domains, there is convolution defined on the real line and circular convolution defined on a finite segment of the real line; both allow for the convolution theorem to hold true. Taking discrete subsets, we have discrete convolution over the integers and circular discrete convolution over a finite range of integers. Suitably defined, both discrete types satisfy a version of the discrete convolution theorem. The convolution theorem is important both for pure math and for practical calculation. Fast convolution using the discrete Fourier transform is

n\log(n)

and straight multiplication and addition is

n^{2}

.

So given two finite sequences of length

n

and

m

with

n\geq m

, how do we convolve? First of all, mapping to discrete circular convolution, already being finite, is the way to go. If you want to use fast convolution, the discrete convolution theorem requires both sequences be of length

n

, so zero-padding is necessary here to extend the shorter sequence. If you want to convolve using simple multiplication and addition, you have two options. Either you can use zero padding, which makes the iteration logic simple. Or you can avoid zero padding and add extra conditionals to the iteration code to prevent access of out-of-bounds sequence elements. Convolution with finite sequences is nicely discussed in section 13.1 of Numerical Recipes in C, 2nd. ed.

It would be useful to elucidate these issues in the article. My recommendation would be to discuss convolution with finite sequences in the Circular discrete convolution section --Mark viking (talk) 22:48, 9 May 2013 (UTC)

No, that's not what Petergans is saying. His argument is ad hoc, mathematically unsophisticated and wrong. The mathematicians are saying that convolution is defined using the group structure of the underlying group. That dictates how you you convolve. When the group is the integers, then necessarily the elements of the group algebra are absolutely summable sequences. When the group is, say, cyclic abelian of finite order n, then the group algebra consists of finite sequences of length n and you get the "discrete circular convolution." Real line, same thing, you have L^1 functions. The convolution is defined the same way for any locally compact abelian group and the Fourier analysis goes through just the same. To say that convolution is undefined for sequences is non-sensical. Mct mht (talk) 23:16, 9 May 2013 (UTC)

Another insult! My argument is not "wrong". It concerns a practical application, which needs to be taken into account in the mathematics. I'm not saying that "convolution is undefined"; some points at the start and end of the convolved sequence are undefined.

(C\otimes y)_{j}\ =\sum _{i=-(m-1)/2}^{i=(m-1)/2}C_{i}\,y_{j-i}\qquad j=(m-1)/2+1,...,n-(m-1)/2

n is the length of the y-vector and, implicitly, m is an odd integer. Thus, for j=1,..,(m-1)/2 the convolved points are undefined, and similarly at the end of the sequence. In total m-1 points are undefined. As I mentioned before, values for the points that are undefined with this formula can be obtained by other means. Incidentally, on p209 of my book Fig. 9.8 shows part of the discrete Fourier transform of a vector of 15 quadratic/cubic smoothing coefficients, C. Petergans (talk) 10:10, 10 May 2013 (UTC)

I don't have access to your book, but if you're doing DFT, then the companion notion of convolution is actually the cyclic convolution (which should never be "undefined"). Sławomir Biały (talk) 10:47, 10 May 2013 (UTC)

With a 5-point function the above formula gives

Y_{1}=C_{-2}y_{-1}+C_{-1}y_{0}+C_{0}y_{1}+C_{1}y_{2}+C_{2}y_{3}

Y₁ is undefined because y_-1 and y₀ do not exist (see example above). Circular convolution has nothing to do with this.Petergans (talk) 15:46, 10 May 2013 (UTC)

You're the one that brought up the discrete Fourier transform. If you really believe that the circular convolution has nothing to do with this, then you don't have a clue what you're talking about. Sławomir Biały (talk) 15:59, 10 May 2013 (UTC)

I don't have much time to comment, but I see what Petergans is up to, I think. The difference is between the values other than specified being undefined, and the values other than specified being assumed zero. The former (Petergans) has absoutely nothing to do with FFT or DFTs, though. — Arthur Rubin (talk) 16:31, 10 May 2013 (UTC)

I agree. Also agreed that this has nothing to do with circular discrete convolution or DFTs. As Mct mht nicely summarized above, mathematicians have a single concept of convolution based on abstract harmonic analysis on various topological groups or semigroups. But for other fields of endeavor, (data analysis, signal processing, etc.) convolution often has alternative meanings. Some of those alternative meanings may be considered ad hoc compared to the pure math concept, but they are in current use, discussed in reliable sources, and WP should cover them. As another example, consider image convolution in Gimp, an image processing program like Photoshop. In Gimp, there are different options for handling image borders in the convolution operation: extend, wrap, or crop. If I understand Petergans' example above, he advocates a 'crop' in his instance. 'Wrap' is more akin to mapping to discrete circular convolution. And I know of other conventions in image processing for handling convolution at the borders. Ideally, we cover it all. --Mark viking (talk) 17:55, 10 May 2013 (UTC)

There is an applications section for ad hoc applications such as these. I emphasize that just because some people do not define the convolution outside of some bounds does not make the definition in the article "wrong" as Peter Gans is insisting. Sławomir Biały (talk) 18:28, 10 May 2013 (UTC)

That's enough! After a third insult I quit this discussion. (Help:Wikipedia: The Missing Manual/Collaborating with Other Editors/Handling Incivility and Personal Attacks) Petergans (talk) 18:47, 10 May 2013 (UTC)

Time for a change?

It's a little misleading for the article to list these formulas before giving the definition in the general case. It gives and reinforces, as above exchange shows, various confusions: the domain is not clear, there are "different" convolutions, etc. Maybe that should be changed?

Convolution theorem actually embodies this problem: two "different" proofs for two special cases. Mct mht (talk) 04:38, 10 May 2013 (UTC)

I agree that taking the abstract harmonic analysis approach to convolution allows for a pretty unification of the different domains, as you nicely noted above. But from my experience, most electrical engineers, computer scientists, photographers, etc., don't know what a group is. And in the real world, signals are finite, symmetry is often broken, and periodicity is a convenient fiction to make the math easier. I think we would need to be careful not to scare away users with heavy math at the beginning of the article. --Mark viking (talk) 05:34, 10 May 2013 (UTC)

From Numerical Recipies, Pascal edition, p. 450, quote: Evidently, we have just described in words the following definition of discrete convolution with a response function of finite duration, M

(r*s)_{j}\ =\sum _{k=-(M-1)/2+1}^{M/2}s_{j-k}r_{k}\qquad (12.4.1)

unquote

This definition conflicts with the definition given in the article

(f*g)[n]\ {\stackrel {\mathrm {def} }{=}}\ \sum _{m=-\infty }^{\infty }f[m]\,g[n-m]

because the summation limits are finite in one expression and infinite in the other. Petergans (talk) 09:28, 11 May 2013 (UTC)

I thought that Peter Gans had said he would leave this discussion! To stop these useless discussion, I have the following suggestion: change the title of this discrete section to "convolution on Z", put more math in it, like a discussion of the Wiener algebra A(T) and perhaps some convolution on finite cyclic groups. Create somewhere else a section about practical use of convolution. I like the idea of User:Mark viking to describe the problems at the boundary with Gimp, and the ad hoc solutions available. One last comment: this article starts with "in MATHEMATICS"... Bdmy (talk) 09:41, 11 May 2013 (UTC)

Unacceptable reversion

The reversion by user:Bdmy is unacceptable. The title of this article is Convolution, and the formula fits the general definition (Numerical Recipes, p. 450).

This formula must be included because it covers a range of applications. For example, in numerical smoothing and differentiation the term convolution is linked to this article, so it is essential that a reader, using the link from that article, will find a consistent definition here. Petergans (talk) 13:19, 14 May 2013 (UTC)

Your proposed edit is inconsistent with the source you cited, where f is explicitly an infinite signal and g is a finite impulse response. Moreover, the formula you gave

(f*g)_{n}=\sum _{m=1}^{M}f_{n-\left({\frac {M+1}{2}}-m\right)}g_{m}\qquad {\frac {M+1}{2}}\leq n\leq N-{\frac {M-1}{2}}

is just wrong. In particular, it doesn't appear in any of the sources cited in the article, nor indeed any sources that I am familiar with. Sławomir Biały (talk) 13:28, 14 May 2013 (UTC)

By good fortune I still have a reprint of the SG paper (Savitzky, A.; Golay, M.J.E. (1964). "Smoothing and Differentiation of Data by Simplified Least Squares Procedures". Analytical Chemistry. 36 (8): 1627–1639. doi:10.1021/ac60214a047.). The formula they give is

Y_{j}*={\frac {\sum _{i=-m}^{i=m}C_{i}Y_{j+i}}{N}}

Here, m=(M-1)/2. I wanted to avoid the plus sign (j+i) which makes it look as though it is cross-correlation (SG explicitly state that it is convolution) also to use normal vector indexing from 1 to M. My formula above is exacly equivalent, differing only in indexing. Also it makes the limits of applicability clearer. Put the SG formula in, with citation, if you prefer. Petergans (talk) 15:37, 14 May 2013 (UTC)

"Indexing" is of course quite relevant to the mathematical notion of convolution, as well as the present context of the article. I've already given my opinion of the suitability of the SG reference, but you didn't seem to be interested in discussing it then. In fact, you specifically withdrew from further discussion. So your enjoinder now to participate in "rational discussion" seems disingenuous. WP:STICK seems to be getting increasingly relevant. Sławomir Biały (talk) 16:57, 14 May 2013 (UTC)

It is not the convolution. It would only be the convolution for symmetric vector C. The problem here is that you are suggesting that a very niche application of convolution should be given far more weight in the article than other applications, so much so in fact that you are insisting that the very definition must be made to conform to this very uncommon one that doesn't happen to agree with anyone else's. See WP:WEIGHT for why this is not consistent with our policies. Sławomir Biały (talk) 12:47, 15 May 2013 (UTC)

Once again my contribution has been reverted. This is appalling.

The process is convolution. This clearly stated in the introduction of Savitzky and Golay's paper
The vector C need not be symmetric. Unsymmetrical examples can be seen at Savitzky–Golay smoothing filter, Table of convolution coefficients for 1st derivative
The term "niche" is a point of view, not supported by the fact that "Savitzky and Golay's paper is one of the most widely cited papers in the journal Analytical Chemistry"
The formula is properly sourced in the scientici literature

Petergans (talk) 14:39, 15 May 2013 (UTC)

Peter, see WP:BRD. You were bold, but then were reverted. Now you must discuss and persuade others. It is not appropriate for you to continue inserting contentious material against consensus. Sławomir Biały (talk) 15:32, 15 May 2013 (UTC)

In order to cool down the debate, I propose the following free-access reference for study to the debaters

http://www-inst.eecs.berkeley.edu/~ee123/fa12/docs/SGFilter.pdf

I don't have time to elaborate on it right now, but I will be back. Just two remarks: the interest of the SG filter has little to do with the fact that one can, or cannot, write it FORMALLY EXACTLY as f*g. Second, the SG paper is somewhat known in the strict math. literature: around 6 occurrences in references of papers listed in Math. Reviews.

Please have a look to the above link, I think it is informative, reasonable and looks mathematically correct. Bdmy (talk) 07:24, 16 May 2013 (UTC) (Bdmy (talk) 07:33, 16 May 2013 (UTC))

Thank you for this reference. It certainly confirms that SG-filtering is a convolution process. Most of the material in the pdf is covered, with detailed examples, in my book, "Data Fitting in the Chemical Sciences", though I only illustrated frequency response with a single example. I also created the article Numerical smoothing and differentiation, which has lots of detail. The use of a SG-filter for numerical differentiation is illustrated in another article that I created, Spectroscopic line shape.

The only question that remains is how best to illustrate it the mathematically. My last attempt used the formula published by SG because this can be directly applied to practical examples, whereas the formula given in the pdf is more abstract and does not give the limits of applicability, which are important in practical applications. If you agree with this, please restore my last edit. Petergans (talk) 09:28, 16 May 2013 (UTC)

Coming along to this as far as I can see what you are trying to stick in is in the plus form normally used for a cross-correlation rather than with a minus for a convolution. They do the same sorts of things but confusing the two in an article like this is not I feel in the least helpful. The paper by Savitzky and Golay seems to be an original practical paper for chemists where they implemented an algorithm in FORTRAN and what they did was convolution okay. The basic idea is a good one, however the way they wrote it down does not correspond with usage nowadays in mathematics computer science or electronics. The only real question I can see is whether the way round they put things has enough weight to be mentioned here. Personally I don't see that it does except perhaps as a warning note about the confusion in some areas. Dmcq (talk) 10:01, 16 May 2013 (UTC)

It is certainly relevant to point out that the article presently already contains precisely the formula of the SG filter as stated on the second page of Bdmy's reference. The only issue is the applicable bounds, which depend on the specific application and so are not appropriate for a general purpose article on convolution (but would be appropriate for the main article on the SG filter). The present formula in the article was already arrived at as a compromise with User:Petergans, who had added a formula together with a reference that actually didn't support the formula as written. This was then corrected by Arthur Rubin, who made the unfortunate edit summary "statement, as written, is wrong, and I don't want to repair it." Peter Gans latched onto this summary, saying "If it's wrong, correct it. And, don't remove citations". So I came along and corrected it, from the very source that Peter had used to support the statement in question. This compromise, however, did not seem to satisfy Peter, since the formula in our article no longer agreed exactly with the way convolution is used in numerical smoothing and differentiation (see discussion above why of course bounds are relevant in ad hoc applications, but that doesn't mean that the mathematical definition should dwell on things like this). So Peter added at various points to the section this rather questionable formula. Now he adds the SG filter, which is the cross-correlation rather than the convolution, and really doesn't fit at all with the article. Even if, as Dmcq says, it is possible to coax this thing into a convolution, it really doesn't belong in a general article on convolution. In fact, the article that Bdmy links clearly conveys that this application of convolution is just that: an application of convolution (one that is not even all that well known to experts in the subject). Specializing a general article on one particular application of something is not appropriate, for reasons that I have already said. Please, if you want the article to cover this application, then write a paragraph in the applications sections that links to the respective articles on numerical smoothing and the SG filter. To me, that would be an acceptable way to deal with this disagreement. Sławomir Biały (talk) 12:11, 16 May 2013 (UTC)

I was editing at the same time as User:Sławomir Biały, what follows does not take his above contribution into account.

I continue with two remarks and a proposition:

When the reference above, that I Googled at random, mentions "discrete convolution", it writes a formula identical to that of User:Sławomir Biały.
Why insist on putting a convolution sign " * " in the equation

(f*g)_{n}=\sum _{m=-(M-1)/2}^{(M-1)/2}f_{n+m}g_{m}\qquad {\frac {M+1}{2}}\leq n\leq N-{\frac {M-1}{2}}

contrary to the ubiquitous mathematical usage, and where the coefficients g(j) are unknown, so, they do not give (cannot give/should not give, in this general mathematical article) a valuable account of what S-G is really about?

I propose to elaborate on the following scheme:

The Savitzky-Golay algorithm^[1] is important^[2] for smooting data. It is based on discrete convolution and polynomial approximation. It is mainly used in the fields of...

[1]
S-G...
[2]
According to... it is the xth most viewed... also appears in mathematical articles...

with NO (in my opinion) useless and (obviously) controversial displayed equation.

Bdmy (talk) 12:31, 16 May 2013 (UTC) Bdmy (talk) 13:31, 16 May 2013 (UTC)

Discrete convolution(2)

I propose the following insertion. It answers all the concerns expressed above and is verifiable.

For vectors y of length N and C of length M (odd), the following summation is used, for example, in smoothing and differentiation of digital data:^[1]

(C*y)_{n}=Y_{n}=\sum _{m=-(M-1)/2}^{(M-1)/2}C_{m}y_{n+m}\qquad {\frac {M+1}{2}}\leq n\leq N-{\frac {M-1}{2}}

For illustration, with M = 5,N = 7 the formula gives (using matrix notation)

{\begin{pmatrix}{Y_{3}}\\{Y_{4}}\\{Y_{5}}\\\end{pmatrix}}={\begin{pmatrix}C_{-2}&C_{-1}&C_{0}&C_{1}&C_{2}&&\\&C_{-2}&C_{-1}&C_{0}&C_{1}&C_{2}\\&&C_{-2}&C_{-1}&C_{0}&C_{1}&C_{2}\\\end{pmatrix}}{\begin{pmatrix}{y_{1}}\\{y_{2}}\\{y_{3}}\\{y_{4}}\\{y_{5}}\\{y_{6}}\\{y_{7}}\\\end{pmatrix}}.

[1]
Savitzky, A.; Golay, M.J.E. (1964). "Smoothing and Differentiation of Data by Simplified Least Squares Procedures". Analytical Chemistry. 36 (8): 1627–1639. doi:10.1021/ac60214a047.

Petergans (talk) 07:19, 17 May 2013 (UTC)

No, this insertion does not answer the concerns. It uses without a warning the same convolution sign " * " used everywhere else in this article with a different meaning. Also, you did not answer my question: WHY INSIST SO MUCH AND SO LONG to have this very notation here, conflicting with the rest of the article? This concern has been also expressed by User:Dmcq.

Bdmy (talk) 07:46, 17 May 2013 (UTC) Bdmy (talk) 08:48, 17 May 2013 (UTC)

And for a discrete convolution in the usual form elsewhere you'd need to swap C_i with C_−i and those index bounds are silly because it is perfectly okay for M to be an even number. There is nothing stopping people smoothing by taking the average of two adjacent points giving a point which appears half way between them for instance. You're just talking about implementation details in a persons computer program, and they were just trying to do something practical rather than interested in convolution as such. Dmcq (talk) 08:35, 17 May 2013 (UTC)

One can actually see the implementation creeping out in that

\operatorname {min} (n+m)={\frac {M+1}{2}}+\left(-{\frac {M-1}{2}}\right)=1

, the default lower bound in FORTRAN. Dmcq (talk) 09:38, 17 May 2013 (UTC)

This is truly a convolution. Don't just take my word for it. It's in the SG paper. The purpose of the illustration is to show how the convoluting function C "slides" through the data vector y, just as it should do in a convolution process. The indexing may seem peculiar, but it's convenient and is the indexing used in the source, the SG paper, so its verifiable. It is indeed perfectly OK for M to be an even number. The reason for preferring M odd is that then Y_n can replace y_n, which is convenient in practice (otherwise the Y points would be between the y points on the abscissa) . Your point about

\operatorname {min} (n+m)={\frac {M+1}{2}}+\left(-{\frac {M-1}{2}}\right)=1

is also a good one. In an earlier version I changed the summation indexing to m= 1,..,M, but that was reverted.

This is a Wikipedia issue, not a maths issue. I insist in order to make links from other Wikipedia articles more meaningful. Have you seen how many articles link to this one?

Let's have no more negative criticism. Either come up with something that is more acceptable, or accept the present proposal. Petergans (talk) 10:19, 17 May 2013 (UTC)

Your conclusion is extraordinary: nobody agrees with you, so we should accept this insertion. I am ready to believe that no "rationale debate" is possible with you.

Bdmy (talk) 10:48, 17 May 2013 (UTC)

You should document in the smoothing and differentiation article that the mathematical convention for indices when talking about convolution is the opposite of the one used by Abraham Savitzky and Marcel J. E. Golay.. The convention there has too little WP:WEIGHT in this context. You really should not be pushing some fifty year old implementation in FORTRAN in a concept article. Dmcq (talk) 11:17, 17 May 2013 (UTC)

I believe that I've already indicated what would be acceptable: a paragraph in the Applications section that links to the articles on the SG filter and numerical smoothing and differentiation. Implementation details should be left out of this paragraph, and instead contained in the main articles where it is relevant. Sławomir Biały (talk) 11:20, 17 May 2013 (UTC)

Have it your way. The section is incomplete because it lacks a formula for the convolution of two vectors. Petergans (talk) 13:10, 17 May 2013 (UTC)

You do realize there are a lot of other smoothing filters besides the Savitzky–Golay one?Dmcq (talk) 14:14, 17 May 2013 (UTC)

I am curious to see a relevant mathematical source that defines convolution of VECTORS in say, Rⁿ. I believe more in a source like Tichmarsch than Savitzky-Golay, when it is about writing a general article about the mathematical notion of convolution. I am really amazed that Petergans seems unable to get this point. For me, if the section is incomplete, it is because it does not mention Zⁿ for example and other discrete groups. I do not see what benefit for this article in adjoining to this section material that does not add any mathematical content to the formula already given in the case where one sequence is finitely supported. Bdmy (talk) 14:39, 17 May 2013 (UTC)

A last try before I give up. Peter, is it possible that you do not see that you are trying to put an incredible emphasis on a formula which is worth nothing, not just in mathematical terms, if it is not supported by the much more important part of the S-G algorithm that is to follow, and that does not fit here? If Wikipedia in general is concerned, what benefit can a general reader get from knowing that you define, as you do, new coefficients

(C*y)_{n}

, where the

C_{j}

are unknown coefficients? What difference with just having the usual formula for convolution, where he/she has just to change the unknown coefficients

C_{j}

into the just as unknown coefficients

C_{-j}

? Will you go on for ever writing:

but it is written in S-G!!! but it is written in S-G!!! ...

Bdmy (talk) 17:33, 17 May 2013 (UTC)

Maybe convolution with vectors is not discussed in some mathematical texts. It is, nevertheless, frequently used in that context in the scientific literature. It's not that the SG formula is important in itself - originally I only cited it as an example. Actually, I believe that smoothing is largely a cosmetric operation; least-squares procedures are generally better for dealing with noisy data. For me the real value of SG filters is that they provide a simple method for doing numerical differentiation, so open a convenient pathway into derivative spectroscopy. Other areas of application of numerical derivatives of experimental data, extensively used, are automated peak finding (zeros in odd derivatives) and end-point determination (location of inflection points), mentioned in numerical smoothing and differentiation#applications. The theory behind these application should be outlined in a maths article and on that basis the section on discrete convolution is incomplete. Petergans (talk) 19:39, 17 May 2013 (UTC)

As I asked before, what is, in the literature, the difference between convolution of vectors and convolution of function on Z with finite support? If there is no essential difference, then the existing "Discrete convolution" section needs no further comment. — Arthur Rubin (talk) 20:26, 17 May 2013 (UTC)

One just has to choose whether to embed the vector into the group algebra of Z or some Z_n. I agree that the section needs no further comment. Mct mht (talk) 21:04, 17 May 2013 (UTC)

I would dispute that the least squares algorithm with polynomials is the best way of smoothing. S-G have been quite careful to choose a degree and width so the coefficients go down the further away from the central point but that does not happen in general. Basically the problem is that it doesn't weight the centre more than the ends and polynomials are nasty at the ends. I would consider for instance a straightforward low pass filter far better in general. Notice the way it wiggles getting smaller and smaller at the ends. You can do differentiation with any of the methods without any bother. I am not totally impressed by you quoting articles you largely wrote. Dmcq (talk) 22:58, 17 May 2013 (UTC)

Domain of definition

This section does not cover discrete convolution. Petergans (talk) 07:35, 18 May 2013 (UTC)

I see Mark Viking has put in a link to a description of the method you are trying to push here. I've no problems with what they've done. Do you disagree with that paper? In particular equation (4)? Dmcq (talk) 10:05, 18 May 2013 (UTC)

There's a bit less to say about the domain of definition of the discrete convolution in Z. The typical application is for absolutely summable sequences, although it can be defined in other

\ell ^{p}

spaces. I've added some discussion of this to the section on the discrete convolution. Sławomir Biały (talk) 11:53, 18 May 2013 (UTC)

It looks a bit funny because practically the same condition is in there twice, under the discrete convolution for the sequences and once under Domain of definition for the integrable functions. The same thing happens with Young's inequality in there twice for measures. Dmcq (talk) 12:22, 18 May 2013 (UTC)

Yes, and it probably should appear yet again in the section on groups. In some sense, this is in increasing level of mathematical sophistication. It could probably be made more harmonious though. I've removed it for now. It's probably best not to dwell on these things. Sławomir Biały (talk) 13:06, 18 May 2013 (UTC)

Definition

Domain of definition

Circular discrete convolution

Circular convolution

Discrete convolution

Time for a change?

Related Articles