For math challenged - what is the Walsh-Hadamard transform?

Wikipedia states the Walsh-Hadamard transform is an example of a 
generalized class of Fourier transforms. Loosely paraphrased it also 
seems to say the Fourier transform is a/(any???) linear operator which 
maps functions to other functions (a basis set???).

The picture at Wikipedia's entry for Walsh functions is intriguing but 
not illuminating.

College physics led to understanding previous semester's calculus, not 
vice versa as intended.

Pointers please ;)

On Sep 14, 7:54 am, Richard Owlett <rowl...@atlascomm.net> wrote:
> Wikipedia states the Walsh-Hadamard transform is an example of a
> generalized class of Fourier transforms. Loosely paraphrased it also
> seems to say the Fourier transform is a/(any???) linear operator which
> maps functions to other functions (a basis set???).
>
> The picture at Wikipedia's entry for Walsh functions is intriguing but
> not illuminating.
>
> College physics led to understanding previous semester's calculus, not
> vice versa as intended.
>
> Pointers please ;)

By a "generalized class of Fourier transforms," I think they are just
referring to the fact that the transform is an orthogonal
decomposition. In that, it is similar to the DFT, except its set of
basis functions is different. Instead of sinusoidal basis functions of
varying frequency, the Hadamard transform uses mutually orthogonal
trains of +1/-1 values. The Wikipedia article also points out that the
transform is equivalent to a combination of size-2 DFTs, so I suppose
you could combine the results FFT-style to get the full DFT of your
signal, but I doubt that would be useful for anyone.

The "function-to-function mapping" refers to the fact that the input
to the transform is a function (i.e. in the time domain), and the
output is another function (in another domain). The output function is
composed of coefficients that can be used to linearly combine the
basis functions to get the original function back, just like in a
Fourier transform or any other orthogonal decomposition.

Jason

On 2007-09-14 08:54:11 -0300, Richard Owlett <rowlett@atlascomm.net> said:

> Wikipedia states the Walsh-Hadamard transform is an example of a 
> generalized class of Fourier transforms. Loosely paraphrased it also 
> seems to say the Fourier transform is a/(any???) linear operator which 
> maps functions to other functions (a basis set???).
> 
> The picture at Wikipedia's entry for Walsh functions is intriguing but 
> not illuminating.
> 
> College physics led to understanding previous semester's calculus, not 
> vice versa as intended.
> 
> Pointers please ;)

It is a Fourier Transform but the index group (the time) is not the one
you are used to. It is for n-dimensional space where each dimension is
of extent 2. So the addition for time is by what is commonly called
logical exclusive or. The convolution that results from that form of
addition of time is not the usual one either. No surprise there.

The usual Fourier transforms that you may be used to have time that is either
continuous or discrete and may either be unbounded or periodic. So there
are four of them. Continuous time matches with unbounded frequencies and
discrete time matches with periodic frequencies. Unbounded time matches with
continuous frequencies and periodic time matches with discrete frequencies.
There is a convenient operational calculus which ties the four together.
Start with the continuous unbounded time case which is commonly taught.
You can now either multiply by, convolve with or both multiply and convolve
with an infinite comb of delta functions to get the others. It is easy to
make a fool of oneself if you forget that the word was operational calculus
which means that you get a very good hint as to what the answer is but you
still need to do the proofs to verify the results. There is a correct
rigourous theory of distrubutions but you loose the forest for the details
of the viruses of the fungus on the scale on the leaves of the trees. But
that never stopped anyone on the internet.

cincydsp@gmail.com wrote:
> On Sep 14, 7:54 am, Richard Owlett <rowl...@atlascomm.net> wrote:
>> Wikipedia states the Walsh-Hadamard transform is an example of a
>> generalized class of Fourier transforms. Loosely paraphrased it also
>> seems to say the Fourier transform is a/(any???) linear operator which
>> maps functions to other functions (a basis set???).
>>
>> The picture at Wikipedia's entry for Walsh functions is intriguing but
>> not illuminating.
>>
>> College physics led to understanding previous semester's calculus, not
>> vice versa as intended.
>>
>> Pointers please ;)
> 
> By a "generalized class of Fourier transforms," I think they are just
> referring to the fact that the transform is an orthogonal
> decomposition. In that, it is similar to the DFT, except its set of
> basis functions is different. Instead of sinusoidal basis functions of
> varying frequency, the Hadamard transform uses mutually orthogonal
> trains of +1/-1 values. The Wikipedia article also points out that the
> transform is equivalent to a combination of size-2 DFTs, so I suppose
> you could combine the results FFT-style to get the full DFT of your
> signal, but I doubt that would be useful for anyone.
> 
> The "function-to-function mapping" refers to the fact that the input
> to the transform is a function (i.e. in the time domain), and the
> output is another function (in another domain). The output function is
> composed of coefficients that can be used to linearly combine the
> basis functions to get the original function back, just like in a
> Fourier transform or any other orthogonal decomposition.
> 
> Jason
> 
This is my understanding.  I want to add that there is an infinite 
number of such orthogonal decomposition schemes, the first element of 
which can be arbitrarily chosen -- it just constrains the rest of the 
elements*.  The Fourier transform is a useful decomposition because it 
has a definite relationship to the real world -- linear systems can be 
easily and completely characterized by their response to an ensemble of 
sinusoidal signals.  Thus, the Fourier transform is the best known one 
by far.

* See Van Trees, "Detection, Estimation and Modulation Theory", part I.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Do you need to implement control loops in software?
"Applied Control Theory for Embedded Systems" gives you just what it says.
See details at http://www.wescottdesign.com/actfes/actfes.html

Gordon Sande wrote:


>                              ...    you loose the forest for the details
> of the viruses of the fungus on the scale on the leaves of the trees. But
> that never stopped anyone on the internet.

That's precious!

Jerry
-- 
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

Gordon Sande wrote:
> On 2007-09-14 08:54:11 -0300, Richard Owlett <rowlett@atlascomm.net> said:
> 
>> Wikipedia states the Walsh-Hadamard transform is an example of a 
>> generalized class of Fourier transforms. Loosely paraphrased it also 
>> seems to say the Fourier transform is a/(any???) linear operator which 
>> maps functions to other functions (a basis set???).
>>
>> The picture at Wikipedia's entry for Walsh functions is intriguing but 
>> not illuminating.
>>
>> College physics led to understanding previous semester's calculus, not 
>> vice versa as intended.
>>
>> Pointers please ;)
> 
> 
> It is a Fourier Transform but the index group (the time) is not the one
> you are used to. It is for n-dimensional space where each dimension is
> of extent 2. So the addition for time is by what is commonly called
> logical exclusive or. The convolution that results from that form of
> addition of time is not the usual one either. No surprise there.
> 
> The usual Fourier transforms that you may be used to have time that is 
> either
> continuous or discrete and may either be unbounded or periodic. So there
> are four of them. Continuous time matches with unbounded frequencies and
> discrete time matches with periodic frequencies. Unbounded time matches 
> with
> continuous frequencies and periodic time matches with discrete frequencies.
> There is a convenient operational calculus which ties the four together.
> Start with the continuous unbounded time case which is commonly taught.
> You can now either multiply by, convolve with or both multiply and convolve
> with an infinite comb of delta functions to get the others. It is easy to
> make a fool of oneself if you forget that the word was operational calculus
> which means that you get a very good hint as to what the answer is but you
> still need to do the proofs to verify the results. There is a correct
> rigourous theory of distrubutions but you loose the forest for the details
> of the viruses of the fungus on the scale on the leaves of the trees. But
> that never stopped anyone on the internet.
> 

Is it fair to say that a mathematician would see similarities between 
Fourier and Walsh-Hadamard transforms because they follow similar rules?

Are there physical systems that are naturally described by 
Walsh-Hadamard transforms [as a Fourier transform relates an impulse 
response to a transfer function]?

> Are there physical systems that are naturally described by
> Walsh-Hadamard transforms ... ?

Unlikely.
Rader put it nicely in his bookreview ( IEEE ASP August 1984 )
on the book by Elliott, Rao " Fast Transforms ..." Academic Press 1982: 

"With the next chapter begins the description of the more exotic 
species of transform. The first of these is the Walsh transform. 
As with real biological species it is well to beware. 
New species are often named by biologists, unaware that they have 
renamed existing species. Thus we have the Walsh transform, the 
Hadamard transform and the BIFORE transform which are all identical. 
This reviewer prefers to think of all these transforms as a special 
case of the multidimensional DFT. With log2N dimensions and two points 
per dimension the DFT is a Walsh transform. With four points per 
dimension we find the generalized transforms of the following chapter. 
The authors prefer to introduce all these transforms as discretized 
versions of continous transforms using some rather contrived basic 
functions. The principal deficiency of all these transforms has been 
their poor fit to the real-world application areas. All the 
transforms avoid multiplications but the price paid is that such 
natural waveform properties as bandwidth, time invariance and 
frequency are replaced by analogous but unnatural properties 
appropriate to the contrived basis functions. 
In spite of the dearth of ready applications the books extensive 
bibliographie should permit the reader to locate Walsh transform 
applications in his own interest area." 

MfG  JRD

Jerry Avins wrote:

> Gordon Sande wrote:
> 
> 
>>                              ...    you loose the forest for the details
>> of the viruses of the fungus on the scale on the leaves of the trees. But
>> that never stopped anyone on the internet.
> 
> 
> That's precious!
> 
> Jerry

I like the intended metaphor.

But it may also be true in another way. Might you not be able to infer 
some characteristics of the forest from looking at the viruses. A 
certain virus would affect only a certain fungus which requires certain 
temperature and moisture to thrive and only grows on certain scales 
which requires certain conditions and certain trees which usually 
do/don't grow with specie such and such.

On 2007-09-15 07:43:08 -0300, Richard Owlett <rowlett@atlascomm.net> said:

> Gordon Sande wrote:
>> On 2007-09-14 08:54:11 -0300, Richard Owlett <rowlett@atlascomm.net> said:
>> 
>>> Wikipedia states the Walsh-Hadamard transform is an example of a 
>>> generalized class of Fourier transforms. Loosely paraphrased it also 
>>> seems to say the Fourier transform is a/(any???) linear operator which 
>>> maps functions to other functions (a basis set???).
>>> 
>>> The picture at Wikipedia's entry for Walsh functions is intriguing but 
>>> not illuminating.
>>> 
>>> College physics led to understanding previous semester's calculus, not 
>>> vice versa as intended.
>>> 
>>> Pointers please ;)
>> 
>> 
>> It is a Fourier Transform but the index group (the time) is not the one
>> you are used to. It is for n-dimensional space where each dimension is
>> of extent 2. So the addition for time is by what is commonly called
>> logical exclusive or. The convolution that results from that form of
>> addition of time is not the usual one either. No surprise there.
>> 
>> The usual Fourier transforms that you may be used to have time that is either
>> continuous or discrete and may either be unbounded or periodic. So there
>> are four of them. Continuous time matches with unbounded frequencies and
>> discrete time matches with periodic frequencies. Unbounded time matches with
>> continuous frequencies and periodic time matches with discrete frequencies.
>> There is a convenient operational calculus which ties the four together.
>> Start with the continuous unbounded time case which is commonly taught.
>> You can now either multiply by, convolve with or both multiply and convolve
>> with an infinite comb of delta functions to get the others. It is easy to
>> make a fool of oneself if you forget that the word was operational calculus
>> which means that you get a very good hint as to what the answer is but you
>> still need to do the proofs to verify the results. There is a correct
>> rigourous theory of distrubutions but you loose the forest for the details
>> of the viruses of the fungus on the scale on the leaves of the trees. But
>> that never stopped anyone on the internet.
>> 
> 
> Is it fair to say that a mathematician would see similarities between 
> Fourier and Walsh-Hadamard transforms because they follow similar rules?

Walsh-Hadamard is just the common name for the Fourier transform on a 
particular
group (that many do do usually think of as a group).

> Are there physical systems that are naturally described by 
> Walsh-Hadamard transforms [as a Fourier transform relates an impulse 
> response to a transfer function]?

There are but the structure of the time is so different you would probably
say it is only in the wildest dreams of crazy mathematicians. They go under
quite different names. If I understand the technology I bellieve it is
called Code Division in communications. The systems concerned are not
"physical" in some common usages but are only "logical" in a more specialized
sense. The fact that the methods are useful is well indicated by their having
been "discovered" from first principles long ago and given common names by
folks who did not know that it was just a rather technical special case of
even older mathematics.

Richard Owlett <rowlett@atlascomm.net> writes:
> [...]

Richard,

Take what you read in this thread with a grain of salt. You
are treading on ivory-tower feet. 

Everything that's being said can be broken down into common
sense, but I see few people here doing so. Granted, it may
take a bit of explaining as well.
-- 
%  Randy Yates                  % "...the answer lies within your soul
%% Fuquay-Varina, NC            %       'cause no one knows which side
%%% 919-577-9882                %                   the coin will fall."
%%%% <yates@ieee.org>           %  'Big Wheels', *Out of the Blue*, ELO
http://home.earthlink.net/~yatescr