optimization problem

Ravi Varadhan <rvaradhan <at> jhmi.edu> writes:

Dear Hans,

I agree with your comments.  My intuition was that the quadratic
form would be better behaved  than the radical form (less
nonlinear!?).  So, I was "hoping" to see a change in behavior when
the cost function was altered from a radical (i.e. sqrt) form to
quadratic, but I was still surprised to actually see it.  I don't
have a good explanation for this.  

I came up with the idea of solving Klaus' problem as an LSAP
problem.  I did not know that the LSAP approach to this and
similar problems has already been considered by Nick Higham.
I asked Nick last night about this problem thinking that he might
know of more direct solutions to this problem (e.g. some kind of
SVD or related factorizations). He said that I should take a look
at the PhD thesis of one of his students.

Thanks for pointing out the thesis. As I understand, the (one-sided)
Procrustes problem is finding an orthogonal matrix minimizing

    min! || A R - B || , t(R) R = I , ||.|| the Frobenius norm

and that there is an substantial theory behind in numerical linear
algebra. The basic literature appears to be

    Gower, J.C; Dijksterhuis, G.B., Procrustes Problems, Oxford
    Statistical Science Series, Oxford University Press, 2004

The thesis itself will lead us astray as it treats the two-sided
Procrustes Problem, which is not our main concern.
The request on R-help only asked for permutation matrices P (from
left or right) minimizing

    min! || P A - B ||

so I still think that a direct approach as you have suggested is
possible given this apparently much simpler problem.

Take your definition of D with quadratic terms:
The LSAP approach will find a permutations of the rows of B, say Bp,
such that the (linear!) sum over D_{ip(i)} is minimal, that is

    sum over rows {sum d(Bp - A)^2} = sum over all {(Bp - A)^2}

which is exactly square of the Frobenius norm.
If you instead apply your first definition with square roots, it is

    sum over rows {sum sqrt(d(Bp - A)^2)}

and this cannot be expanded to the sum of the Frobenius norm.
Therefore, the quadratic approach is indeed correct and will lead
to a true optimum, while the first variant will not.

Hans Werner

Take a look at Section 3.5 of the PhD thesis

Parallel Solution of SVD-Related Problems, With Applications
http://www.maths.manchester.ac.uk/~higham/misc/past-students.php

This thesis proposed algorithms for the current problem and
different versions of it under the heading of "Procrustes-type"
problems.  I have to read this and get a better handle on it.  
I would not be able to get to this for another two weeks. If you
have any insights from this, in the meanwhile, do share with us.

Best regards,
Ravi.

____________________________________________________________________

Ravi Varadhan, Ph.D.
Assistant Professor,
Division of Geriatric Medicine and Gerontology
School of Medicine
Johns Hopkins University

Ph. (410) 502-2619
email: rvaradhan <at> jhmi.edu