Solution to an apparently simple Optimization Problem

Question

I'm stuck at a proof of a property that is stated in a paper. Imagine we have a diagonal matrix $$\Sigma=\begin{pmatrix}\lambda_1& &0\\ &\ddots&\\0&&\lambda_n\end{pmatrix}$$ with $\lambda_i\in\mathbb{R}_{\geq 0}$. Consider the following optimization problem for $n\geq k$ \begin{align*} \min_{A\in\mathbb{R}^{k\times n}}& tr(A\Sigma A^T)\\ s.t.\quad& AA^T = I_k \end{align*} The solution should be to choose the $k$ smallest values of $\lambda_i$ by orthonormal vectors in the matrix $A$ such that $tr(A\Sigma A^T)=\sum_{i=1}^k\lambda_i$ if $\lambda_1\leq\ldots\leq \lambda_n$, but I don't know how to derive it.. it seems like a well known, simple problem, maybe there's a common trick to solve it?

Answer 1

Almost got it: Assume w.l.o.g. that $\lambda_1\leq \ldots\leq \lambda_n$ \begin{align*} tr(A\Sigma A^T)=tr((A\Sigma)^TA) =tr(\Sigma A^TA) \end{align*} The rank of $A^TA$ is exactly $k$, since $rank(A^TA)=rank(AA^T)=rank(I_k)$ and $A^TA$ is idempotent. Thus, there exist orthonormal basis transformation matrices (eigenvectors to the eigenvalues 1 and 0 form an orthonormal basis) $B\in\mathbb{R}^n$, such that $$ B^T A^TA B= \begin{pmatrix} I_k&0\\ 0&0 \end{pmatrix}, $$ and therefore it holds that $$tr(\Sigma A^TA)=tr(\Sigma B^TA^TAB)=\lambda_1+\ldots+\lambda_k$$ But I'm not so sure about $tr(\Sigma A^TA)=tr(\Sigma B^TA^TAB)$, does anybody know why it holds?