Date: Nov 16, 2012 11:05 AM
Author: Kaba
Subject: Least-squares using polar decomposition
(I'm sending this again, since the last post did not appear on my news

server, nor in Google Groups)

Hi,

Let P, R in R^{d x n}, A, Q, S in R^{d x d} with Q^T Q = I and S^T = S.

The problem is to find A to minimize

|AP - R|,

where |.| is the Frobenius norm. It can be shown that the solution is

A = RP^T (PP^T)^{-1}.

I want to derive the result differently. First, notice that every A can

be decomposed as A = QS. For if A = UDV^T is the singular value

decomposition of A, then Q = UV^T and S = VDV^T is such a decomposition.

Now I want to solve a new problem, which is to find Q and S to minimize

|QSP - R|.

Clearly, I could just compute A and then decompose it as above. But I

don't want to do that. Instead, I want to derive the result by

optimizing Q and S.

If I vary Q (subject to it being orthogonal), I get

PP^T S + SPP^T = Q^T RP^T + PR^T Q.

If I vary S (subject to it being symmetric), I get

Q^T RP^T S = SPR^T Q.

But then I am stuck. In a previous post this week, concerning

least-squares scaling where Q = I, it was noticed that

PP^T S + SPP^T = RP^T + PR^T

is a Lyapunov equation, and can be solved as it is. Therefore, I would

except that the solution of this more general problem yields something

similar to a Lyapunov equation, perhaps a Sylvester equation (more

general), or an algebraic Riccatti equation (even more general):

http://en.wikipedia.org/wiki/Sylvester_equation

http://en.wikipedia.org/wiki/Algebraic_Riccati_equation

It seems to me that first I should be able give an implicit equation for

either S or Q alone. It probably is also the case that the QS

decomposition (polar decomposition) is not unique, and therefore an

additional condition would be needed to make the solution unique.

Ideas appreciated. The reason I am interested in this is that I suspect

there is a new technique (to me) underlying here.

--

http://kaba.hilvi.org