[R] optimization problem

[Hans W. Borchers]

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
>