Do the mathematical inverse and identity elements exist for convolution?

in article T9OdnZxFPtTwjfHfRVn-gQ@comcast.com, James Van Buskirk at
not_valid@comcast.net wrote (corrected) on 04/24/2005 17:32:

> "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?

which kind is that?  circular convolution or linear convolution?  (we can
rule out continuous-time convolution, i think.)

>  In my universe, the identity element for
> convolution is delta[n], 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.

then you have to settle the issue of what kind of convolution.  at least to
determine if there is an inverse or not.  in both circular and linear
convolution, the kronecker delta is an identity element.  but for linear
convolution, there is no way to convolute anything against a non-trivial
input to get delta[n].

i think, for linear convolution, we need to define our vectors as having an
infinite number of elements (many of which may be zero), but then the DFT
isn't defined.  if DFT is an operation, then these vectors can be finite in
length (they're really a single period of a periodic sequence) but the
convolution operator is circular.  in that case, there is an inverse vector
as long as the input vector's DFT is non-zero for all elements.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

"James Van Buskirk" <not_valid@comcast.net> writes:

> "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.

Is [1 0 0 0] = [1 0 0 0 0 0 0 0]? In this mathematical system,
they're not. If they were, then we would not have a unique identity
element, and that ain't good.

So, yes, we're talking about "some other convolution," namely, one
in which the lengths of operand vectors and result vector matter.
-- 
%  Randy Yates                  % "Though you ride on the wheels of tomorrow,
%% Fuquay-Varina, NC            %  you still wander the fields of your
%%% 919-577-9882                %  sorrow."
%%%% <yates@ieee.org>           % '21st Century Man', *Time*, ELO
http://home.earthlink.net/~yatescr

"Randy Yates" <yates@ieee.org> wrote in message
news:wtqrhayp.fsf@ieee.org...

> Is [1 0 0 0] = [1 0 0 0 0 0 0 0]? In this mathematical system,
> they're not. If they were, then we would not have a unique identity
> element, and that ain't good.

> So, yes, we're talking about "some other convolution," namely, one
> in which the lengths of operand vectors and result vector matter.

Looking back at the original post, I see the comment:

> 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).

So it would seem that lengths don't matter, since closure under
convolution multiplication is assumed.  But further we see:

> 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.

So now length does seem to matter again.  Recall that the O.P.
did not claim to be a expert on the mathematics of DSP.  It
seems to me that signal processing books talk about four kinds
of situations: aperiodic continuous signals, periodic (or bounded
in time) continuous signals, aperiodic discrete signals, and
periodic (or bounded in time) discrete signals.  Probably the
O.P. has one of the above in mind but it seems that he is rusty
enough at this that he is not making precise which one.  I think
from rereading the original post that he was assuming aperiodic
discrete signals -- it's not 100% certain that this is the
case, but if it is, then x[n] = delta[n] would be the identity,
and to determine if a vector were a zero divisor, you would
take its DTFT and see whether there were any regions where
this is zero.  That would not in itself be sufficient to make
the original vector a zero divisor, but certainly it can be
seen at a moment's reflection there there are some zero
divisors as well as units in this vector space (exactly
what is meant by the vector space depends on precisely how
fast it is intended that x[n] -> 0 as n -> +- oo) or ring.

-- 
write(*,*) transfer((/17.392111325966148d0,6.5794487871554595D-85, &
6.0134700243160014d-154/),(/'x'/)); end

"James Van Buskirk" <not_valid@comcast.net> writes:

> "Randy Yates" <yates@ieee.org> wrote in message
> news:wtqrhayp.fsf@ieee.org...
> 
> > Is [1 0 0 0] = [1 0 0 0 0 0 0 0]? In this mathematical system,
> > they're not. If they were, then we would not have a unique identity
> > element, and that ain't good.
> 
> > So, yes, we're talking about "some other convolution," namely, one
> > in which the lengths of operand vectors and result vector matter.
> 
> Looking back at the original post, I see the comment:
> 
> > 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).
> 
> So it would seem that lengths don't matter, since closure under
> convolution multiplication is assumed.  


Lengths matter even there. Recall that the convolution of two sequences
of lengths N and M results in a sequence of length N + M - 1. Since
the length of [1] is 1, the convolution of it with any sequence of
length N results in a sequence of length N again. 

Now I don't know see how closure applies to this specific point. I had
asked Charles to clarify if his set S was the set of all
finite-lengthed vectors, and that is what I was assuming, so no matter
what length the result vector is, it should be back in S (i.e., the
operation of convolution of two finite-lengthed vectors should be closed).
It is just that in the particular case of the identity, we should have
the case that x*e = e*x = x.

> But further we see:
> 
> > 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.
> 
> So now length does seem to matter again.  

Well it does matter but Charles is just observing (correctly) that you
can never get a vector of length 2 or greater to result in a vector of
length 1 under the operation of convolution, and since [1] is the
identity, you don't have inverses in this mathematical system. At
least that's how I interpreted his point - Charles please correct me
if I'm wrong.

> Recall that the O.P.
> did not claim to be a expert on the mathematics of DSP.  It
> seems to me that signal processing books talk about four kinds
> of situations: aperiodic continuous signals, periodic (or bounded
> in time) continuous signals, aperiodic discrete signals, and
> periodic (or bounded in time) discrete signals.  Probably the
> O.P. has one of the above in mind but it seems that he is rusty
> enough at this that he is not making precise which one.  

I was assuming his set S in the candidate group (S,*), where "*"
is convolution, is the set of all finite-lengthed vectors. I could
have been wrong.
-- 
Randy Yates
Sony Ericsson Mobile Communications
Research Triangle Park, NC, USA
randy.yates@sonyericsson.com, 919-472-1124

On 25 Apr 2005 06:57:21 -0400, Randy Yates
<randy.yates@sonyericsson.com> wrote:
> "James Van Buskirk" <not_valid@comcast.net> writes:
> 
(snip)

> Lengths matter even there. Recall that the convolution of two sequences
> of lengths N and M results in a sequence of length N + M - 1. Since
> the length of [1] is 1, the convolution of it with any sequence of
> length N results in a sequence of length N again. 
> 
> Now I don't know see how closure applies to this specific point. I had
> asked Charles to clarify if his set S was the set of all
> finite-lengthed vectors, and that is what I was assuming, so no matter
> what length the result vector is, it should be back in S (i.e., the
> operation of convolution of two finite-lengthed vectors should be closed).
> It is just that in the particular case of the identity, we should have
> the case that x*e = e*x = x.
> 

Thanks for not trying to read my mind Randy, not like some Other folks.
:)

I'm using "vector" to mean "Ordered n-tuple of numbers" which is what we
deal with on physical computers.

I'm not referring to "n-element tensors of order 1" necessarily, nor to
CompSci "vectors" as intelligent 1-d arrays.

I'm borrowing Matlab's term in this case.

I'll have to think about James' "countably long" case.  You can't
easily convolve ( . . ., 0, 1, 0, . . , ) given finite memory, which I
suppose points out the difference between math and implementation.

I looked it up on Mathworld:

http://mathworld.wolfram.com/Convolution.html

where they define convolution in terms of an integral.  That makes me
think that, in general, no inverse element can exist.

I'll have to think about whether or not a subset of functions exists
which are a group under convolution, much as "The set of all matrices"
is not a group under matrix multiplication, BUT "for all natural numbers
n > 1, the set of invertable nxn matrices" is a group.

My "quick and dirty" thought about the countably long case is that it
has the same problem as the "all real values of t" case, but I'll need
to approach it with more rigor to satisfy myself that it's true.

On Mon, 25 Apr 2005 13:28:46 GMT, Charles Krug <cdkrug@worldnet.att.net>
wrote:
> 
> I'll have to think about whether or not a subset of functions exists
> which are a group under convolution, much as "The set of all matrices"
> is not a group under matrix multiplication, BUT "for all natural numbers
> n > 1, the set of invertable nxn matrices" is a group.
> 

Sorry, that should be "For each natural number n > 1 . . . " rather than
"for all"

in article zIOdnSILWryu8vHfRVn-ug@comcast.com, James Van Buskirk at
not_valid@comcast.net wrote on 04/25/2005 00:16:

> Recall that the O.P.
> did not claim to be a expert on the mathematics of DSP.

maybe he doesn't like bragging.  are you claiming to be an expert on either?

> It seems to me that signal processing books talk about four kinds
> of situations: aperiodic continuous signals,

Fourier or Laplace Transform

> periodic (or bounded in time) continuous signals,

Fourier Series

> aperiodic discrete signals,

Discrete-Time Fourier Transform or Z Transform

> and periodic (or bounded in time) discrete signals.

DFT (or if people object to me saying the DFT periodically extends your
data, then i'll say Discrete Fourier Series which is mathematically
identical to the DFT).


> Probably the
> O.P. has one of the above in mind but it seems that he is rusty
> enough at this that he is not making precise which one.

i'll agree he didn't make his question clear enough and would likely have
answered his own question had he made it specific.  the OP doesn't seem
rustier than most other posters to comp.dsp.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

"Randy Yates" <yates@ieee.org> wrote in message 
news:mzrnj0qm.fsf@ieee.org...
>> 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

Yes.  I mentioned that in the post you replied to. Sorry for being terse, 
but I find it a bit insulting that you corrected me without bothering to 
read it.

--
Matt 

"robert bristow-johnson" <rbj@audioimagination.com> wrote in message
news:BE927DF0.68B9%rbj@audioimagination.com...

> in article zIOdnSILWryu8vHfRVn-ug@comcast.com, James Van Buskirk at
> not_valid@comcast.net wrote on 04/25/2005 00:16:

> > Recall that the O.P.
> > did not claim to be a expert on the mathematics of DSP.

> maybe he doesn't like bragging.  are you claiming to be an expert on
either?

I don't think anyone can claim to be an expert on the mathematics
of DSP.  Consider the small branch that I take as a hobby: minimum
arithmetic operation count algorithms for DFT and cyclic convolution.
Clearly I can't be an expert because there are aspects of
interpolation algorithms that I just don't get: how do you know
the interpolation points chosen are going to lead to the best (I
assume fixed-point) algorithm, particularly if shifts as well as
additions are allowed in the final algorithm?  How, for that
matter, do you know that you want to do interpolation over the
field of rationals?  Lots of other related questions -- if someone
considered themselves an expert at this sub-branch of the
discipline they would likely be snickering away at my shortcomings
at this point.  But OTOH, they could look at:

http://home.comcast.net/~kmbtib/

and see whether they still considered themselves an expert.  So
I don't think an expert exists, at least in the way that the
pubic at large expects an 'expert opinion.'  But if you look at
the way the O.P. seems to munge together Kronecker and Dirac,
for e.g., it seems to me that he is in a learning phase here,
and is not shy about revealing any lacunae in his DSP knowledge
so that they might be gently filled in by the readership of
the current forum.

-- 
write(*,*) transfer((/17.392111325966148d0,6.5794487871554595D-85, &
6.0134700243160014d-154/),(/'x'/)); end

On Mon, 25 Apr 2005 14:13:58 GMT, Charles Krug <cdkrug@worldnet.att.net> wrote:
> On Mon, 25 Apr 2005 13:28:46 GMT, Charles Krug <cdkrug@worldnet.att.net>
> wrote:
>> 
>> I'll have to think about whether or not a subset of functions exists
>> which are a group under convolution, much as "The set of all matrices"
>> is not a group under matrix multiplication, BUT "for all natural numbers
>> n > 1, the set of invertable nxn matrices" is a group.
>> 
> 
> Sorry, that should be "For each natural number n > 1 . . . " rather than
> "for all"
> 

Hey!  No talking about me like I'm not here!!
:-)

As I said, I've been doing much more DSP implementation and device
control than theory.

OTOH, I was kinda expecting someone to ask just what the heck I meant by
a group . . .