Hadamard-Matrices

[Annette.Warlich at t-online.de]

Am 29.03.05 02:21 schrieb Paul C. Leopardi:
> Hi all,
> At the risk of making a fool of myself, I'll try answering this, below.
> Best regards

Hi, that's nice. Thanks!

>>
>>Since Hadamard-Matrices H are orthogonal they can be rotated to a
>>n * I -matrix by
>>
>>    H * T = n*I
>>
>>so must a n*I-matrix be rotatable to H by
>>
>>    H = n*I * T'
> 
> 
> I don't know what definition of Hadamard matrix you are using, but using
> http://mathworld.wolfram.com/HadamardMatrix.html
> we have the definition that a Hadamard matrix is a (-1,1) matrix with 
> H * H' = n * I.
> Therefore Hadamard matrices are NOT orthogonal, they are sqrt(n) times an 
> orthogonal matrix.

Yes - I used that definition. I'm further used to the distinction

 orthonormal - H*H' = I
 orthogonal  - H*H' = n*I

The term "orthogonal" was used in some web-pages focusing Hadamard-matrices,
so I took that use myself. I should have mentioned that difference, sorry.
But anyway- this difference has no consequence for the underlying problem.


> 
> The Mathworld web page says that you can obtain a 2^n * 2^n Hadamard matrix by 
> using a complete set of Walsh functions, and you can use the Kronecker 
> product to get large Hadamard matrices from small ones.
> 
Yes, simply concat

    [ H4  H4 ]   = H8
    [ H4 -H4 ]

and iterate.


> 
>>From  factor-analysis the "quartimax"- and "varimax" rotation are known,
>>which maximize the variance of the squares of the entries of the columns.
>>
>>One form some other descriptions of Hadamard-matrix besides the
>>maximum-determinant criterion is, that the variance of the squares
>>is zero.
> 
> 
> Presumably this is because each entry is +/- 1, so each square is always 1.
> 
Yes. That is the argument I wanted to exploit.


> 
>>(With n=16 a certain precondition helped improving convergence.)
>>
>>In fact, I just find the n=4,N=8,n=12 and n=16 - solutions by
>>using that criterion.
>>I was not able to detect such of higher order - already with the
>>n=16 case the convergence indicated the possibility of ending
>>in local minima.
> 
> 
> I am not familiar with this, and so cannot answer, except to ask, how do you 
> know that the problem does not have local minima? Is there a theorem which 
> says that any local minimum must be a global minimum? Or a counterexample?
> 
Yes- I would like to understand the case more deeply, *how* there can
be a local minimum in that. The formulae, with which I derived the
Quartimax- and the varimax-criterion don't look too difficult, and
besides the understanding, that polynomial formulae of higher degree than 2
generally can have local minima/maxima, I've difficulties to *locate*
that in the mathematical process of quartimax/varimax-iteration: it's
just lack of imagination.


> 
>>I would like to understand this problem better - mainly: how can
>>the iterative process terminate without reaching its minimum.
>>I just tried it with higher numeric precision (up to 512 bits), but
>>it doesnt seem, that this is the problem.
> 
> 
> What is the iterative process? Can you spell it out? Is it a nonlinear 
> optimization algorithm? Can you supply it with a Jacobian?

It's pairwise column-rotation, where the rotation angle is determined
with a maximizing-function.
All pairs of columns are taken as a plane and rotated with their
individual pairwise rotation angle, and if all pairs are done,
then it is supposed to have a better solution.
Then this is iterated until acceptable convergence.

The criterion for quartimax is possibly best explained geometrically

Assume the selected pair of colums represent with its rows a number
of vectors pointing from (0,0) to their resp. x/y - coordinates.

The rotate this system of vectors such that all vectors are
nearest to one of the axes.
For instance:if there would be only one single vector, then it
is rotated either to the x- or the y-axis. One coordinate 0, one coordinate
maximum. If there are two or more, then this is approximated by a
least-squares-criterion.

In a plane you can get it further with the idea, that you
multiply each vector's angle by 4, find the centroid of that,
divide the centroids angle by 4 and have the angle, with
which you have to rotate the vectorsystem in the current plane,
fitting the coordinates best to one of the axes.
It's the same as with finding the principal axes, only that
with princ. axes you multiply the angles only by two, that means
to fit the coordinates to only one axis, namely the x-axis.


The formula is (if the x/y-coordinates of the i'th vector are xi and yi)

                          sum ( fy4(xi,yi))
     phi = 0.25 * arctan( -------------------
                          sum ( fx4(xi,yi))

and
      fx4(x,y) =     fx2(x,y)^2 - fy2(x,y)^2
      fy4(x,y) = 2 * fx2(x,y)   * fy2(x,y)

    and

      fx2(x,y) =    x^2 - y^2
      fy2(x,y) = 2 * x * y

just analoguos to the trigonometric function of doubling an angle.

Well - this criterion rotates the coordinates to the axes as near
as possible. If you have an orthogonal matrix, then quartimax
rotates that into diagonal form.

If you change this criterion to *minimizing* then this rotates
the coordinates to the 45 deg-line, and this is also the resulting
pattern of a (-1,1) Hadamard-matrix.

Now the quartimax- and varimax-critrion is heavily used in
factor analysis and as I read it, it is also proven to converge
this means: actually find the position of the maximum possible
variance.
(Maybe the current problem with the finding of the Hadamard-matrix
of order>16 is a hint, that the convergence-proof is not 100%
valid, or it may be that the mentioned convergence proof is related
to only correlation matrices: symmetric and diagonal-dominant)


Well - the idea was to use one of the obvious properties of
the hadamard-matrix, for instance the aspect of the variance
being 0 with a (+1/-1)-Hadamard-matrix, and null or only
marginal changings to the given maximizing-criteria in canned
rotation-procedures.

---

One more surprising fact is, that the

  H4-matrix is just one 6'th root of the 2*I-Matrix.

That means, not only

   H4*H4' = I4 ,

but also

   H4^6 = I4

which possibly allows some construction process for higher
orders. I'll see.
Unfortunately I could not find such an expression for H8 or H12.

----

(and - thanks for the input!)

Gottfried Helms