# Eigen value minimization-Proof

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.

-

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.
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