MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## For an approach to the Hadamard-matrix-problem: is there a proof, that the iterative plane-wise orthogonal rotations (Quartimax/Varimax) converge to global maximum?

I've asked this question at stat-exchange and at the "Semnet"-mailing list of professionals in statistics. The reference to some articles in Psychometrica (for instance ten Berge 1995, Jennrich 2001) were insofar helpful, that I saw, that reasons for nonsuccessful rotation were handled - but the explicite statement, whether the iteration with plane-wise rotations using the Varimax- or Quartimax-criterion is always converging /can always be made converging was not made/referred to. (This is different for instance for the case of using the principal components-criterion, for which I think I've come across an explicite proof ~20 years ago).

The reason to ask this is an approach to the Hadamard-matrix-problem: the Hadamard-matrix is defined to consist of entries +1 and -1 only and being orthogonal.
Being orthogonal means to have the form of a rotation-matrix, simply scaled by one scalar factor such that all entries have the desired value -1 or +1. That means, the variance of the squared entries is zero. So if I begin with any initial rotation-matrix, and rotate to minimal (instead of maximal) variance using the inverse of the "varimax" or of the "quartimax"-criterion, say "varimin" or "quartimin", I should arrive at a proper Hadamard-matrix, scalar scaled by the reciprocal of the square of the number of rows/columns.

Indeed this works for small sizes (up to n=20, so nxn=20x20) and "sometimes" for n=24, but then the Hadamard-form is found extremely seldom.
Ten Berge (1995) gave insight in the rotation procedure, noting, that sometimes convergence is not reached because of systematic missing of optimization of some planes in the iterative process, but which might be overcome by some workaround. The global convergence question however was not explicitely mentioned as solved.

Question: is a proof for the convergence to the global optimum by the iterative, plane-wise rotation using the quartimax/varimax-rotation known? Or is it known, that it does not always converge?) (If it is simple enough it might be done here, or else a reference were good. I've it -surprisingly- not seen in the monographies on factor analysis of for instance S.Mulaik(74) or K.Überla(68) .

(This "varimin"-rotation-approach to the Hadamard-matrix problem has its further charme, because it is also applicable to matrices which have other dimensions than n=4*m, and is thus some more general formulation/notion for that problem: "the lower bound for the variance of the squared entries of orthogonal matrices of size nxn where n=4m is zero" )

Examples

//commands in "Matmate" to reproduce the approach
n=8
A = gettrans(randomu(n,n),"drei")  // creates a random rotation-matrix in A
A = sqrt(n) * A                    // rescales it with the scalar  sqrt(n)
T = gettrans(A,"-varimax")         // gets the rotationmatrix T which rotates A
//     using the optimization criterion "Varimin"
H = A * T                          // gets the Hadamardmatrix of size 8x8
//     by column-rotation


$\qquad \small \text{ A =} \begin{array} {rrrrrrrr} 0.95& 0.24& 1.32& 0.34& -0.87& -1.08& 1.54& -0.94\\ 1.45& 0.06& -1.03& -0.57& 1.71& -0.41& 0.05& -1.19\\ 1.29& -0.91& -0.50& 1.41& -0.98& 1.29& -0.54& -0.59\\ 1.02& 1.14& -1.36& 0.36& -0.67& -0.75& 0.35& 1.60\\ 0.53& -0.28& 1.21& 1.36& 1.14& -0.97& -1.14& 0.86\\ 0.20& 1.76& 0.72& 0.57& 0.87& 1.69& 0.62& 0.13\\ 0.64& 1.26& 0.62& -1.03& -0.92& -0.11& -1.84& -0.57\\ 1.26& -1.03& 0.85& -1.48& 0.08& 0.78& 0.36& 1.31 \end{array}$

$\qquad \small \text{ H =} \begin{array} {rrrrrrrr} -1.00& -1.00& 1.00& 1.00& -1.00& -1.00& 1.00& -1.00\\ 1.00& -1.00& -1.00& -1.00& 1.00& -1.00& 1.00& -1.00\\ 1.00& -1.00& -1.00& 1.00& -1.00& 1.00& -1.00& -1.00\\ 1.00& 1.00& -1.00& 1.00& -1.00& -1.00& 1.00& 1.00\\ 1.00& -1.00& 1.00& 1.00& 1.00& -1.00& -1.00& 1.00\\ 1.00& 1.00& 1.00& 1.00& 1.00& 1.00& 1.00& -1.00\\ 1.00& 1.00& 1.00& -1.00& -1.00& -1.00& -1.00& -1.00\\ 1.00& -1.00& 1.00& -1.00& -1.00& 1.00& 1.00& 1.00 \end{array}$

For a dimension not a multiple of 4 we do not get the variance of the squares of the matrix-entries to equal zero but I think, we get the solution of minimal variance, and the squares of the entries are not 1.
Example n=6:

$\qquad \small \text{ A =} \begin{array} {rrrrrr} 1.00& 1.29& 1.32& -1.10& 0.33& 0.52\\ 0.48& 0.23& 1.14& 1.56& -1.39& -0.22\\ 1.51& -1.51& -0.08& 0.09& 0.12& 1.18\\ 1.38& 0.62& -1.39& -0.40& -0.85& -0.94\\ 0.74& -0.32& 0.49& 0.63& 1.55& -1.52\\ 0.21& 1.22& -0.88& 1.34& 0.89& 1.04 \end{array}$
and
$\qquad \small \text{ H =} \begin{array} {rrrrrr} 0.00& 1.10& 1.10& -1.10& 1.10& 1.10\\ 1.10& 1.10& 1.10& 1.10& -1.10& 0.00\\ 1.10& -1.10& -0.00& -1.10& -1.10& 1.10\\ 1.10& 1.10& -1.10& -1.10& 0.00& -1.10\\ 1.10& -1.10& 1.10& 0.00& 1.10& -1.10\\ 1.10& -0.00& -1.10& 1.10& 1.10& 1.10 \end{array}$

where the nonzero entries are exactly $\small \pm \sqrt{6 / 5}$

[update] For the n=6-case I've got one alternate solution, which is not optimal but which is stationary under the varimin/quartimin-criterion. This is
$\qquad \small \text{ H =} \begin{array} {rrrrrr} 0.75580438&0.75580439&1.32408152&1.12540822&-1.12540822&-0.75580438\\ 1.32408152&-1.12540822&-0.75580438&0.75580439&-0.75580438&1.12540822\\ 1.12540822&-1.32408152&0.75580439&-0.75580438&0.75580438&-1.12540822\\ 1.12540822&1.12540822&0.75580438&-0.75580438&0.75580439&1.32408152\\ 0.75580439&0.75580438&-1.12540822&-1.32408152&-1.12540822&-0.75580438\\ 0.75580438&0.75580438&-1.12540822&1.12540822&1.32408152&-0.75580439 \end{array}$
This is just plain vanilla-"varimin", I did not yet include the ten Berge-workaround here.

-
 isn't the "success" of the algorithm also conditioned on the assumption that there is a Hadamard solution? – suVRit Mar 8 2012 at 17:11 @suvrit: after I've investigated this that bit, it seems to me as if these matrices are the ultimate stress-test for the varimax/varimin-rotation. Surely - one problem includes the other, so a proof for the existence of the varimin-rotation to the global optimum may allow to proceed to prove that the variance is zero for the n=4m-case and so to fill the gap for the Hadamard-problem (whether it is effectively computable this way or not) – Gottfried Helms Mar 8 2012 at 17:25 You might say efficiently computable instead. I know an effectively computable algorithm that determines the status of the Hadamard Matrix Conjecture for all 4n < 1000000; I just have not found time to run it. Gerhard "Way Too Many Small Steps" Paseman, 2012.03.08 – Gerhard Paseman Mar 8 2012 at 18:33 @Gerhard: well, existence-proofs (a: varimin by enhanced iterated plane-rotations can be made to converge, b: for 4n columns the variance of the squared entries is zero) would be enough to settle the question of existence of 4n-Hadamard-matrices. But if the answer of the convergence of varimin/varimax is not yet settled - how can we use the varimax-rotation as a standard procedure for factor analysis for more than 60 years research in psychology and social sciences? In the beginning of my enquiry I firmly expected, there were some (simple) reference to some literature, say Kaiser or Bargman... – Gottfried Helms Mar 9 2012 at 12:17 ... but now I'm really surprised that this does not seem to be the case. Alternatively I hoped, a proof for the convergence might be not too difficult - so it might be inexistent because of "triviality" (The related proof for convergence of the (near related) principal components rotation seems to be existent, though, if I recall my older literature right) – Gottfried Helms Mar 9 2012 at 12:20

While waiting for Will Orrick to weigh in, I have an unprofessional opinion which says that this approach is unlikely to be more productive than many combinatorial approaches for finding D-optimal binary matrices.

There may be some interesting techniques used that will avoid local minima, but the problem smells to me like finding optimal minima of a function for which it can be proven that such minima are found at integral values of the arguments, but that only 1 out of every 2^(n log n) such is an actual optimal minimum. Your function has provably many global minima, and very likely exponentially more local minima. Unless you have a technique for smelling deep gopher holes ins field, you are going to end up checking a lot of shallow gopher holes. And this is for dimensions as small as n=8, where we know ahead of time what all the global minima will look like and where they will be found. If the algorithm does no better than, say, 50% success for this dimension, I expect its chances of success to be superexponentially decreasing as the dimension grows by 4.

On the plus side, I don't know about this algorithm, so there may indeed be a different smell to a deep gopher hole that this algorithm has.

Gerhard "We Need Bill Murray Now" Paseman, 2012.03.08

-
 I just now noticed you wrote varimin rather than vermin or varmint or vermin. Sorry for dragging Bill Murray into this. Gerhard "We Miss You, Emily Litella" Paseman, 2012.03.08 – Gerhard Paseman Mar 8 2012 at 19:33