Guys: I'm brushing up the mathematical side of my DSP brain. It's a bit dusty having spent the last few years doing implementation and device control without regard for the underlying math. I'm trying to satisfy myself that vectors are a group under convolution. I've determined that there's an identity element: For any vector V, V*[1] = V (where * is convolution rather than multiplication) As well as closure and associativity (the underlying operations are associative and closed). Mathworld is helpful in showing that it's commutative, associative, and distributive, so if it's a group, it's also abelian and a field with addition. What about the inverse? For a vector V, is there a unique vector V^-1 such that: V*(V^-1) - [1] My mental model is that it cannot possibly exist for finite length vectors, as the length of the output is necessarily the summed length of V and V^-1. But given a function f, there may well be a function f^-1 such that {1 if x = 0 f*(f^-1) = | {0 elsewhere (or do I mean +Infinity if x = 0?)
Do the mathematical inverse and identity elements exist for convolution?
Started by ●April 23, 2005
Reply by ●April 23, 20052005-04-23
Charles Krug <cdkrug@worldnet.att.net> writes:> Guys: > > I'm brushing up the mathematical side of my DSP brain. It's a bit dusty > having spent the last few years doing implementation and device control > without regard for the underlying math. > > I'm trying to satisfy myself that vectors are a group under convolution. > > I've determined that there's an identity element: > > For any vector V, V*[1] = V (where * is convolution rather than > multiplication) > > As well as closure and associativity (the underlying operations are > associative and closed). > > Mathworld is helpful in showing that it's commutative, associative, and > distributive, so if it's a group, it's also abelian and a field with > addition. > > What about the inverse? > > For a vector V, is there a unique vector V^-1 such that: > > V*(V^-1) - [1] > > My mental model is that it cannot possibly exist for finite length > vectors, as the length of the output is necessarily the summed length of > V and V^-1.I agree. I'm assuming your candidate group set S is the set of all finite-lengthed vectors? So it is not a group due to the lack of inverses. -- % Randy Yates % "Ticket to the moon, flight leaves here today %% Fuquay-Varina, NC % from Satellite 2" %%% 919-577-9882 % 'Ticket To The Moon' %%%% <yates@ieee.org> % *Time*, Electric Light Orchestra http://home.earthlink.net/~yatescr
Reply by ●April 23, 20052005-04-23
Charles Krug wrote:> Guys: > > I'm brushing up the mathematical side of my DSP brain. It's a bit dusty > having spent the last few years doing implementation and device control > without regard for the underlying math. > > I'm trying to satisfy myself that vectors are a group under convolution. > > I've determined that there's an identity element: > > For any vector V, V*[1] = V (where * is convolution rather than > multiplication) > > As well as closure and associativity (the underlying operations are > associative and closed). > > Mathworld is helpful in showing that it's commutative, associative, and > distributive, so if it's a group, it's also abelian and a field with > addition. > > What about the inverse? > > For a vector V, is there a unique vector V^-1 such that: > > V*(V^-1) - [1] > > My mental model is that it cannot possibly exist for finite length > vectors, as the length of the output is necessarily the summed length of > V and V^-1. > > But given a function f, there may well be a function f^-1 such that > > {1 if x = 0 > f*(f^-1) = | > {0 elsewhere > > (or do I mean +Infinity if x = 0?) >Convolution becomes pointwise multiplication under Fourier transforms. So you would need an inverse for multiplying by zero. Deblurring is the art of making point sources have more compact support. Your heuristic misses the notion that the output of a convolution may be numerically zero even if it has more algebraic terms. Zeros in the transform is one of the reasons why deblurring can fail.
Reply by ●April 23, 20052005-04-23
in article R3vae.105239$cg1.65671@bgtnsc04-news.ops.worldnet.att.net, Charles Krug at cdkrug@worldnet.att.net wrote on 04/23/2005 12:53:> I'm brushing up the mathematical side of my DSP brain. It's a bit dusty > having spent the last few years doing implementation and device control > without regard for the underlying math. > > I'm trying to satisfy myself that vectors are a group under convolution.what *kind* of convolution? linear or circular? (is there any other kind?)> I've determined that there's an identity element: > > For any vector V, V*[1] = V (where * is convolution rather than > multiplication) > > As well as closure and associativity (the underlying operations are > associative and closed). > > Mathworld is helpful in showing that it's commutative, associative, and > distributive, so if it's a group, it's also abelian and a field with > addition. > > What about the inverse? > > For a vector V, is there a unique vector V^-1 such that: > > V*(V^-1) - [1] > > My mental model is that it cannot possibly exist for finite length > vectors, as the length of the output is necessarily the summed length of > V and V^-1. > > But given a function f, there may well be a function f^-1 such that > > {1 if x = 0 > f*(f^-1) = | > {0 elsewhere > > (or do I mean +Infinity if x = 0?)i think you'll be able to do this for circular convolution as long as the DFT of the vector is non-zero for every discrete element, as Gordon has pointed out. for finite length vectors, i am not sure how one would define linear convolution with appending zeros on one end or the other. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●April 23, 20052005-04-23
"Charles Krug" <cdkrug@worldnet.att.net> wrote in message news:R3vae.105239$cg1.65671@bgtnsc04-news.ops.worldnet.att.net...> I'm trying to satisfy myself that vectors are a group under convolution.No.> I've determined that there's an identity element: >Yes.> What about the inverse?Firstly, as you note, vectors have this property of "length" that messes things up. In DSP, we consider discrete signals, which are of infinite duration, but may have compact support, which is pretty much what you were getting to at the end of your post. So, are discrete signals a group under convolution? No. Convolution is pointwise multiplication in the frequency domain, so convolution with a signal that has a frequency domain zero can destroy information just like multiplication by zero does. Discrete signals with no frequency domain zeros, however, ARE a group under convolution, like the non-zero elements of a field. How about discrete signals with compact support? Again, no. If a discrete signal has compact support longer than 1 sample, and has an inverse under convolution, then that inverse has infinite support. Interestingly, however, it IS possible to undo any convolution by a signal with compact support, but the procedure to do so may be numerically unstable and can't always be expressed as a convolution. -- Matt
Reply by ●April 24, 20052005-04-24
"Matt Timmermans" <mt0000@sympatico.nospam-remove.ca> writes:> [...] > Discrete signals with no frequency domain zeros, however, ARE a group under > convolution, like the non-zero elements of a field.No, they aren't Matt. NO vector of length 2 or greater, regardless of its frequency-domain characteristics, will have an inverse. This is due, as Charles already pointed out, to the length problem - "[1] is the identity element under convolution and no element of length 2 or more will result in a length 1 element. -- % Randy Yates % "Ticket to the moon, flight leaves here today %% Fuquay-Varina, NC % from Satellite 2" %%% 919-577-9882 % 'Ticket To The Moon' %%%% <yates@ieee.org> % *Time*, Electric Light Orchestra http://home.earthlink.net/~yatescr
Reply by ●April 24, 20052005-04-24
"Randy Yates" <yates@ieee.org> wrote in message news:8y37kip0.fsf@ieee.org...> "Matt Timmermans" <mt0000@sympatico.nospam-remove.ca> writes: >> [...] >> Discrete signals with no frequency domain zeros, however, ARE a group >> under >> convolution, like the non-zero elements of a field. > > No, they aren't Matt. NO vector of length 2 or greater [...]Discrete signals aren't vectors, and don't need "lengths". -- Matt
Reply by ●April 24, 20052005-04-24
"Randy Yates" <yates@ieee.org> wrote in message news:8y37kip0.fsf@ieee.org...> No, they aren't Matt. NO vector of length 2 or greater, regardless of > its frequency-domain characteristics, will have an inverse. This is > due, as Charles already pointed out, to the length problem - "[1] is > the identity element under convolution and no element of length 2 or > more will result in a length 1 element.Are you guys talking about some other kinda convolution than the one I know of? In my universe, the identity element for convolution is delta[0], the vector that is unity for the first (index zero) element and zero for all subsequent elements. Its DFT is a vector of all ones. -- write(*,*) transfer((/17.392111325966148d0,6.5794487871554595D-85, & 6.0134700243160014d-154/),(/'x'/)); end
Reply by ●April 24, 20052005-04-24
"James Van Buskirk" <not_valid@comcast.net> wrote in message news:T9OdnZxFPtTwjfHfRVn-gQ@comcast.com...> delta[0]Oops. I meant delta[n-0]. -- write(*,*) transfer((/17.392111325966148d0,6.5794487871554595D-85, & 6.0134700243160014d-154/),(/'x'/)); end
Reply by ●April 24, 20052005-04-24
"Matt Timmermans" <mt0000@sympatico.nospam-remove.ca> writes:> "Randy Yates" <yates@ieee.org> wrote in message > news:8y37kip0.fsf@ieee.org... >> "Matt Timmermans" <mt0000@sympatico.nospam-remove.ca> writes: >>> [...] >>> Discrete signals with no frequency domain zeros, however, ARE a group >>> under >>> convolution, like the non-zero elements of a field. >> >> No, they aren't Matt. NO vector of length 2 or greater [...] > > Discrete signals aren't vectors, and don't need "lengths".Then you're not discussing the same thing Charles is. From Charles' original post: I'm trying to satisfy myself that vectors are a group under convolution. --RY -- % Randy Yates % "Maybe one day I'll feel her cold embrace, %% Fuquay-Varina, NC % and kiss her interface, %%% 919-577-9882 % til then, I'll leave her alone." %%%% <yates@ieee.org> % 'Yours Truly, 2095', *Time*, ELO http://home.earthlink.net/~yatescr