Minimizing Frobenius norm for two variables

Question

I need to minimize squared Frobenius norm: $\|\mathbf{A} - \mathbf{x}\mathbf{y}^T\|_F^2$. Namely I need to prove that for this norm to reach minimum $\mathbf{x}$ should be eigenvector of $\mathbf{A}\mathbf{A}^T$ corresponding to the largest eigenvalue, and $\mathbf{y}$ should be the same for $\mathbf{A}^T\mathbf{A}$.

So I tried to represent norm in the form of $\sum\limits_i\sum\limits_j(a_{ij} - x_iy_j)^2$ and take partial derivatives both for $x_i$ and $y_j$. But I'm unable to find analytical solution for this. And I believe it would be difficult to prove relation to eigenvector of $\mathbf{A}\mathbf{A}^T$ in this kind of solution. I've tried to expand $(a_{ij} - x_iy_j)^2$ with same result.

Also this looks like something from SVD, because in SVD $\mathbf{U}$ diagonalizes $\mathbf{A}\mathbf{A}^T$ and $\mathbf{V}$ diagonalizes $\mathbf{A}^T\mathbf{A}$. But again I have no idea how to solve initial task with this knowledge.

Would be grateful for any suggestions.

Answer 1

You want to compute the low rank approximation of $A$, in particular, low equals one here. Following the linked description, take $x$ and $y$ such that $$xy^T=\sigma_1 u_1v_1^T,$$ where $\sigma_1$ is the maximal singular value of $A$ and $u_1$ and $v_1$ are respectively the corresponding left and right singular vectors from the SVD of $A$: $A=U\Sigma V^T$ with $U=[u_1,\ldots,u_m]$, $V=[v_1,\ldots,v_n]$, $\Sigma=\mathrm{diag}(\sigma_1,\ldots,\sigma_p)$, $p=\min\{m,n\}$. The optimal value of the squared norm is then given by the sum of squares of the remaining singular values (note that including their possible multiplicities): $$\|A-\sigma_1u_1v_1^T\|_F^2=\sum_{i=2}^p\sigma_i^2.$$

Answer 2

I'm unable to accept Pavel's answer, because of StackExchange not connecting my newly registered account with this question. But Pavel did answer my question. Little clarification:

• eigenvalues for $\mathbf{A}\mathbf{A}^T$ and $\mathbf{A}^T\mathbf{A}$ are equal and $\sigma_i$ is corresponding eigenvalue squared ($\lambda_i^2$)
• $u_1$ is eigenvector for $\mathbf{A}\mathbf{A}^T$
• $v_1$ is eigenvector for $\mathbf{A}^T\mathbf{A}$

All this could be find in the first section of Wikipedia article for SVD.