Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

For positive semi-definite symmetric matrices $A,B$, how can I find an $X$ that minimizes $\text{Trace}(AX^TBX$) under the constraint:

that $X$ is orthogonal.

All the matrices have real entries and $A,B$ are square while $X$ is rectangular. Thanks.

This is what I have:

Define $B=F^{T}F$. Define $Y=FX$. You get the above problem as \begin{align} \min_{Y}~ \text{trace}(AY^{T}Y) \end{align}

But now I want $X^*$ that minimizes the original problem. This is what is confusing me!

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

I guess that $A$ and $B$ are also assumed symmetric.

Your second optimization problem is not equivalent to the first, for two reasons:
(1) You forgot the constraint $YY^T=FF^T$, which corresponds to the old orthogonality constraints.
(2) $F$ may be singular, in which case you cannot reconstruct $X$ from $Y$.

As a result, your transformation gained nothing. Indeed, there doesn't seem to be a closed form solution.

However, you can simplify the problem by transforming $A$ and $B$ to diagonal form (spectral factorization), and transforming $X$ accordingly: Factor $A=QaQ^T$, $B=UbU^T$ with $a,b$ diagonal, $Q,U$ square orthogonal, and define $Z=U^TXQ$. Then $Z$ is orthogonal, $tr~AX^TbX=tr~ aZ^TbZ$, and $X$ can be recovered as $X=UZQ^T$. Thus this preserves the orthogonality constraint, and simplifies the objective function to $\sum_{i,k} a_ib_k Z_{ik}^2$.

Now you have two options:

(i) Pose the problem as a constrained optimization problem to a standfard constrained optimization problem solver such as IPOPT.

(ii) Parameterize $Z$ as a product of reflections or rotations. (This is the Householder or givens version of the QR factorization, applied to an orthogonal matrix $Z$. Use the reflection vectors respective rotation angles as new variables.) Then pose the problem of finding the optimal parameters as an unconstrained optimization problem.

Note that (i) is significantly simpler to prepare, as for high solution quality, one should provide the solver with explicit first derivative information.

share|improve this answer
    
can you put in a few steps to explain "However, you can simplify the problem by transforming A and B to diagonal form (spectral factorization), and transforming X accordingly. This preserves the orthogonality constraint, and simplifies the objective function to $\sum_{i,k}a_ib_kX_{ik}^2$? –  qlinck Nov 18 '12 at 17:51
    
done in the main answer. –  Arnold Neumaier Nov 18 '12 at 18:11
    
Thanks for the wonderful answer –  qlinck Nov 18 '12 at 18:23
    
Can you explain the approach "parameterize Z as a product of reflections or rotations, and pose the problem of finding the optimal parameters as an unconstrained optimization problem" in few steps?? I may need to look at an example to understand/learn about it at my level of maturity.. –  qlinck Nov 18 '12 at 19:25
    
done in the main answer. –  Arnold Neumaier Nov 18 '12 at 19:47
show 5 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.