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 > ______________________________________________ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.