2
$\begingroup$

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<c<n$. 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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – user1551 Oct 18 '18 at 20:08
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.