Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The two minimization problems below are equivalent:

$\min\{\mathrm{trace}(AX^TBX): XX^T=I_n\}=\min\{\mathrm{trace}(AQ^T\tilde{B}Q): QQ^T=I_m\}$, where $A,\tilde{B}$ and $Q$ are square matrices of the same size, $A,B$ are also p.s.d and $X$ is a $m \times n, (m >n) $ rectangular matrix.

The solution to this latter minimization problem is well known: the extrema of the trace are the extrema of $\{\sum_{i=1}^m\lambda_i(A)\lambda_{\sigma(i)}(\tilde{B}): \sigma\in S_m\}$, where $\lambda_i(M)$ denotes the $i$-th eigenvalue of a real symmetric matrix $M$ and $S_m$ is the symmetric group of order $m$.

Suppose $A$ and $\tilde{B}$ are orthogonally diagonalized as $A=U\Lambda U^T$ and $\tilde{B}=V\Sigma V^T$, where $\Lambda = \mathrm{diag}(\lambda_1(A), \lambda_2(A), \ldots, \lambda_m(A))$ contains the eigenvalues of $A$ arranged in ascending order and $\Sigma$ is analogously defined, but the eigenvalues are arranged in descending order. That is, if $\lambda_1(B),\ldots,\lambda_n(B)$ are arranged in ascending order, and for $\Sigma=\mathrm{diag}\left(\lambda_n(B),\ldots,\lambda_1(B),0,\ldots,0\right)$

Then am looking for a 'detailed proof' that the minima is reached at an $X^*$ given by:

\begin{align} X^* &= VU^T \begin{bmatrix}I_n\\ 0_{(m-n)\times n}\end{bmatrix}. \end{align}

for my better understanding.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

It is a bit easy to show for the square case. For the rectangular case, it becomes cumbersome due to heavy notational stuff. You need to have the following inequality for the positive (semi) definite matrices

\begin{align}trace(AB)\geq\sum_{i=1}^{N}\alpha_i \beta_{N-i+1}\end{align}

where $\alpha_ 1\geq\alpha_ 2...\geq\alpha_ N$ are the eigenvalues of $A$ and $\beta_ 1\geq\beta_ 2...\geq\beta_ N$ are eigenvalues of $B$. The lower bound is achieved when $A$ and $B$ commute and the corresponding eigenvalues are in order (ie ascending for $A$ and descending for $B$).

Now $X$ is orthogonal, Define $\hat{B}=X^{H}BX$. Note that $B$ and $\hat{B}$ will have same eigenvalues. This implies $trace(A\hat{B})\geq \sum_{i=1}^{N}\alpha_i \beta_{N-i+1}$. Thus it is enough to design $X$ such that we can attain the (universal) lower bound for every $X$. This is possible only if $X=VU^{H}P$. Here $U$ and $V$ comes from eigen decomposition of $A$ and $B$. $P$ is a suitable permutation (which is orthogonal) matrix which rearranges the eigenvalues. Since you have already assumed the required order, it should be identity.

share|improve this answer
    
also- any views on if the objective function considered in this question is Convex-as in is this solution a point where a global minima is reached? –  qlinck Nov 21 '12 at 18:25
    
Note that $trace(AX^{T}BX)=vec(X)^{T}(A\otimes B)vec(X)$. Since $A$ and $B$ are positive (semi)definite, this implies the objective function is a convex quadratic. But note that this doesn't imply the optimization is itself convex as the orthogonality constraint is not convex. But in this case, due to the constraint, whatever $X$ you come up with (which obeys the constraint), the inequality always holds. For any other $X$ (which obeys the constraint), you can't reduce the objective value than the lower bound. Hence, it should be the solution –  dineshdileep Nov 22 '12 at 3:01
add comment

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.