# What matrix $X$ solves $\max_{X} \|AX\|_F$ s.t. $X^T X=I$?

Consider $$X^* = \arg\max_{X} \| A X \|_F^2$$ subject to $$X^T X=I$$. Here $$A$$ and $$X$$ are non-square matrices. Specifically $$A_{c \times n}$$ and $$X_{n \times k}$$ where $$k. What would be the solution $$X^*$$?

I guess $$X^*$$ would be related to the best rank-$$k$$ approximation of $$A$$, like filling columns of $$X$$ by top $$k$$ singular vectors of $$A$$, but I do not know how to go about proving it.

Any help is greatly appreciated.

Golabi

• Yes, $X$ is comprised of the first $k$ right singular vectors in the singular value decomposition of $A$. There is a proof in Horn and Johnson's Matrix Analysis (but I haven't the book at hand so that I cannot cite the page number), but you may see the idea in my answer to another question. – user1551 Oct 18 '18 at 20:08

Note that in this problem matrix $$X$$ has orthogonal columns. Hence, using this fact and the fact that Frobenius norm of a matrix is equal to sum of $$\ell_2$$ norm of its columns, this problem can equivalently be written as the following: $$\arg\max_{x_1,\dots,x_k} \sum_{i=1}^k x_i^\top A^\top A x_i$$ subject to $$x_i^\top x_i = 1 \quad \forall i\in[k], \qquad x_j^\top x_i = 0 \quad \forall i,j\in[k], i\neq j.$$
If $$k = 1$$, it was easy to see (e.g., by using the Lagrange multipliers) the solution to this problem is to take the largest eigenvector of $$A^\top A$$ (or equivalently, largest singular vector of $$A$$). Using Lagrange multipliers for the equivalent problem where $$k>1$$ shows that your conjecture is correct and the optimal value of $$X$$ is $$k$$ largest singualr vectors of $$A$$.