FFT & averaging

"Andor" <an2or@mailcircuit.com> wrote in message
news:1116087851.369053.99840@g43g2000cwa.googlegroups.com...

> I just wished you stop posting code and start talking a language I
> understand (= maths). I have to invest a large amount of time just to
> decipher you indices, never mind the rest of the code. Can't you
> describe the general idea which makes your convolution (or FFT) faster
> than everybody else's? Then we can discuss the (non-) unitarity of
> these transforms.

I'm so sick of trying to explain this.  I even sat down with
my best friend and wrote a paper about it, but the writing of it
was such a horrible task that I don't relly have any friends any
more.  You will just have to take my word for it, or look it up
in Nussbaumer as I suggested.  It doesn't look like the paper is
going to get published, so maybe I'll put it on my website if my
former friend can ever manage to send it to me in one piece, that
is if he will ever return my calls...

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

Andor wrote:
>  So
> there you have it, U is unitary. This implies again, for example, that
> U maps sets of orthonormal vectors to orthonormal vectors (ie. the
> angle between the vectors is also invariant under U) 

Thanks!  I've been trying, from context, to figure out what 
"unitary" means to no avail for some time.  :-)


Bob
-- 

"Things should be described as simply as possible, but no 
simpler."

                                              A. Einstein

Steven wrote:
> Andor wrote:
> > Unitarity is necessary. Correlation is the inner product between
two
> > vectors. Unitarity implies that the inner product is invariant
under
> > the transform -- that is why you can compute the inner product
> > between two vectors in both time and frequency domain and get
> > the same result.
>
> Andor, I think you've made a fundamental mistake here (besides the
fact
> that correlation is more than just a single inner product). In order
> for a fast convolution (or correlation) algorithm to work, you just
> have to get the correct answer in time domain.  You do *not* have to
> get the same answer in frequency domain (or whatever "domain" your
> intermediate results correspond to, if anything), and thus unitarity
> (or similar) is unnecessary.

Ok Steven, let's review some definitions:

If V is a N-dimensional complex vector space, then the following
defines an inner product: For x=(x_0, x_1, ..., x_{N-1}) and
y=(y_0,y_1,...,y_{N-1}) in V, define

(x,y) := x^H y = sum_{k=0}^{N-1} x_k* y_k

(x^H is the adjoint of x, a row vector with conjugate complex
coordinates). For further notation, I will be using S to denote the
cyclic left-shift operator, ie.

S x = (x_1, x_2, ... , x_{N-1}, x_0),

and d_S to denote the diagonalization of S, ie.

d_S = diag(1, w, w^2, ..., w^{N-1} ),

where w := e^{i 2 pi /N}. F denotes the DFT matrix (scaled such that
F^H F = 1). Now we can derive the fundamental equations that drives
fast convolution and fast correlation.

The correlation rxy between x and y is another element of V defined by

rxy_k = (S^k x,y),      k=0,1,...,N-1.

The k-th coordinate is the inner product between x shifted k times to
the left, and y. Write X = F x, Y = F y and define v = F^H (X* Y) as
the inverse Fourier transform of the point-wise product of the two
vectors X* (conjugate of X) and Y. Now use the unitarity of the DFT:

(S^k x, y) = (F S^k x, F y)                    (1)

We know that F S^k = d_S^k F (the columns of F are the eigenvectors of
S), therefore we can write

(F S^k x, F y) = (d_S^k X, Y)                  (2)

If you look at the right hand side of (2), you'll notice that this is,
by definition, v_k. Add (1) and (2) together to get

rxy_k = v_k.                                   (3)

(3) is the equation that is the basis for fast correlation (and
similarly, fast convolution). Of course, you can define the DFT with
another scale factor, and include that in the above equations. However,
any derivation of equation (3) uses the unitarity of F (as I have
defined it), or something equivalent. Without unitarity, no fast
correlation.


> Trivial counter-example: the unitary FFT would have a 1/sqrt(N) scale
> factor, but this is actually the *wrong* normalization for a fast
> convolution/correlation algorithm...

Whatever scale factor you choose doesn't change the fact that F is
unitary, and that this is a necessary requirement to derive equation
(3).


> (There are a very large number of fast convolution algorithms out
> there...I haven't checked this explicitly, but I suspect that many of
> them, not just James', correspond to non-unitary transforms.)

Again, that is totally irrelevant. One can scale the convolution or
correlation arbitrarily.

> 
> Cordially,
> Steven G. Johnson

Regards,
Andor

1) Your derivation is incorrect because  (d_S^k X, Y) is not the same
thing as v_k -- it is v_k times sqrt(N).  Thus, as I said, you get an
extra factor of sqrt(N) if you use the unitary definition of the DFT
for convolution/correlation.

2) Showing that the DFT's properties give the convolution theorem is
obvious (or at least, well known) and besides the point.  The converse
does not follow - it does not prove that any O(N log N) convolution
algorithm requires a unitary transform.

3) A unitary matrix multiplied by a scale factor is not unitary.
Please notice that I was not claiming that this is necessarily the
*only* counter-example, just the simplest one.

Steven

stev...@alum.mit.edu wrote:
> 1) Your derivation is incorrect because  (d_S^k X, Y) is not the same
> thing as v_k -- it is v_k times sqrt(N).

You are right. Furthermore, for my derivation to hold, one has to
change the defintion of the inner product by swapping the role of the
two vectors. It was late yesterday evening.

> Thus, as I said, you get an
> extra factor of sqrt(N) if you use the unitary definition of the DFT
> for convolution/correlation.

As I said, the final scaling is irrelevant.
>
> 2) Showing that the DFT's properties give the convolution theorem is
> obvious (or at least, well known) and besides the point.  The
converse
> does not follow - it does not prove that any O(N log N) convolution
> algorithm requires a unitary transform.

Show me a O(N log N) correlation / convolution algorithm that does not
make use of my equation (3), or something equivalent, then I'll retract
my claim. Until then, unitarity of the matrix F is essential to show
that the fast algorithms work.

>
> 3) A unitary matrix multiplied by a scale factor is not unitary.
> Please notice that I was not claiming that this is necessarily the
> *only* counter-example, just the simplest one.

Again, you can scale the results of convolution and correlation, as
well as the matrix F, all you want. It doesn't affect my claim.

>
> Steven

What happened to the cordially - you're not getting angry at me, are
you :-)?

Regards,
Andor

Andor,

Let me step back a bit and ask you to clarify what, precisely you are
claiming.

If you were claiming that every O(N log N) convolution algorithm is
*exactly* a transform that computes a unitary matrix, pointwise
multiplication, and the inverse transform, then this claim is disproved
by the ability (indeed, the requirement) to scale the transform.  If
you allow this to be modified by any multiplications by a diagonal
matrix (e.g. a scale factor), then I believe I can still give a trivial
counter-example.

If you say merely that it has to be "related" or "equivalent" to a
unitary transformation, then it's impossible to disprove because you
haven't specified what "related" means.  Everything in mathematics is
related in *some* way, and everything that computes a convolution is
equivalent in the sense that it is computing the same end result.

Steven

PS. It's kind of odd to make a claim without proof or reference and
then demand that others disprove it.

PPS. I tend to use a formal signature only on the first message in a
thread or in response to someone I haven't corresponded with
previously; don't think anything of the change.

Steven wrote:
...
> PS. It's kind of odd to make a claim without proof or reference and
> then demand that others disprove it.

Funny that you should mention that. After all, the only one who did any
proving after being challenged to his statement was I.

Regards,
Andor

"Andor" <an2or@mailcircuit.com> wrote in message
news:1116405891.146469.325640@o13g2000cwo.googlegroups.com...

> Funny that you should mention that. After all, the only one who did any
> proving after being challenged to his statement was I.

Being the original challenger and having offered proof and
reference to proofs that you have refused to read, I demand
that you retract the above statement.

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

Um, except the thing that you proved (that the properties of the DFT
give the convolution theorem) wasn't what you claimed (the converse,
that any O(N log N) convolution algorithm employs a unitary
transformation, for some unspecified definition of "employs").

If you look at what started the argument, I claimed that

"
Unitarity is necessary [for fast correlation to work]. Correlation is
the inner product between two
vectors. Unitarity implies that the inner product is invariant under
the transform -- that is why you can compute the inner product between
two vectors in both time and frequency domain and get the same result
"

In the same post (in a part that you snipped), I described that the
correlation of two vectors is another vector that results from taking
the inner product of the two vectors, where one gets cyclically shifted
for each new coordinate.

I went on to show that to derive the convolution theorem one requires
the unitarity of F (the DFT matrix), and how the convolution theorem is
actually just about taking inner products in both domains und using the
unitarity to see that they are equal.  This is what I mean when I say
that unitarity (of F) is necessary for fast convolution / correlation
to work.

Clearly, you can set G = 1/sqrt(N) F, and write down the same proof,
using the appropriate factors everywhere, and so derive the convolution
theorem with G and say that unitarity is not necessary for fast
convolution / correlation. Now instead of needing F unitary, you need
the fact that G scales the norm by a constant factor. I don't know any
short name for such a matrix, it seems simpler to just use F and using
its unitarity to describe the maths behind fast convolution.

When I say that every O(N log N) algorithm is based on the unitarity of
F, I meant that the unitarity of F is necessary to derive the
convolution theorem which is what fast convolution / correlation
algorithms are based on. As above, set G = 1/sqrt(N) F, call G the
Fourier Transform, and go ahead and say that fast convolution /
correlation does not require unitarity, just norm-invariance. I don't
care about that, as any norm-invariant matrix G can be made unitary (by
multiplication with a factor). This is why I say that multplication
with a factor doesn't change the fact that unitarity is needed.

I don't think I can express my views any clearer than this.

Regards,
Andor