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

Answer

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.