I want to find $\mathbf{x}$ that minimizes $\|A-\mathbf{x}\mathbf{x}'\|^2$ where $\|\cdot\|$ is Frobenius norm. Differentiating with respect to $\mathbf{x}$ and setting to $\mathbf{0}$, I get

$$\mathbf{x}\mathbf{x}'\mathbf{x}=A \mathbf{x}$$

Any idea how to proceed further?

(Per request, here's how I did the derivative) Let $J=\|A-\mathbf{x}\mathbf{x}'\|^2=\text{tr}(Y'Y)$ where $Y=A-\mathbf{x}\mathbf{x}'$

To compute derivative use technique of differentials as in Magnus,Neudecker and here $$dY(\mathbf{x})=-2\mathbf{x} \mathbf{dx}'$$ $$dJ(Y)=\text{tr}(2Y'dY)$$ substitute definition of $dY$ and $Y$ into above, simplify to get $$dJ(\mathbf{x})=-4 \text{tr}((A-\mathbf{x}\mathbf{x}')'\mathbf{x}\mathbf{dx}')=4\mathbf{x}'(\mathbf{x}\mathbf{x}'-A)'\mathbf{dx}$$ The last expression is a canonical form from which the derivative can be identified as the expression before $\mathbf{dx}$, doing transpose and setting to $\mathbf{0}$ gives the equation above.

  • $\begingroup$ Would you mind showing your work differentiating? The reason I ask is because I wonder why your result should favor a form with only right multiplication. The problem is a symmetric equation (with respect to $\mathbf{x}$). $\endgroup$ – adam W Jan 7 '13 at 5:13
  • 2
    $\begingroup$ what's the definition of the matrix norm? $\endgroup$ – chaohuang Jan 7 '13 at 5:14
  • $\begingroup$ Is $A$ a symmetric matrix? $\endgroup$ – user17762 Jan 7 '13 at 6:08
  • $\begingroup$ Added clarifications. Marvis -- I'm interested in both symmetric and general cases $\endgroup$ – Yaroslav Bulatov Jan 7 '13 at 8:10
  • $\begingroup$ I have happened upon your question again. I can say that the definitive answer for the specific and the general case (general rank one approximation) is this: the pair of "largest" singular vectors obtained from the SVD, the Singular Value Decomposition. "Largest" meaning the vectors associated with the largest singular value. This should be standard knowledge--a fact that should be a part of the repertoire of anyone that deals with matrix algebra. $\endgroup$ – adam W Mar 24 '13 at 14:45

Your calculations do not seem quite right. As $Y=A-xx'$, $dY=-dxx'-xdx'$. Therefore \begin{align*} dJ&=\operatorname{tr}\,(Y+dY)'(Y+dY)-\operatorname{tr}\,Y'Y\\ &=\operatorname{tr}\,(Y-dxx'-xdx')'(Y-dxx'-xdx')-\operatorname{tr}\,Y'Y\\ &=\operatorname{tr}\,(-Y'dxx' -Y'xdx' - xdx'Y - dxx'Y)\\ &=\operatorname{tr}\,(-x'Y'dx -x'Ydx - x'Y'dx - x'Ydx)\\ &=\operatorname{tr}\,\left\{-2x'(Y+Y')dx\right\}. \end{align*} Hence $J'(x) = -2x'(Y+Y') = -2x'(A+A'-2xx') = -2x'(A+A')+4\|x\|^2x'$. Actually, the calculations can be made much easier if you rewrite $J(x)$ as \begin{align} J(x)&=\operatorname{tr}\{(A-xx')'(A-xx')\} =\operatorname{tr}(AA' -xx'A - A'xx' + xx'xx')\\ &=\|A\|^2 - 2\operatorname{tr}\left(x'\frac{A+A'}{2}x\right) + \|x\|^4\tag{1} \end{align} right at the beginning. From this reformulation it is immediate that $J'(x)$ and the extrema of $J$ depend only on the Hermitian part $H=\frac{(A+A')}{2}$ of $A$ but not $A$ itself.

To find the critical points of $J$, set $J'(x)=0$. Then we get $x'H=\|x\|^2x'$. In other words, $x=0$ or if $x\not=0$, $x$ is an eigenvector corresponding to a positive eigenvalue $\|x\|^2$ of $H$. So you may first find all eigenpairs $(\lambda,v)$ of $H$, ignore the nonpositive eigenvalues and then set $x=\frac{\pm\lambda^{1/2}}{\|v\|}v$ (the sign does not matter, as it will cancel out itself in the product $xx'$). The zero vector and these eigenvectors of $H$ are the critical points of $J$ modulo symmetry. Plug them into $(1)$, we see that the global minimum of $J$ is given by \begin{cases} \|A\|^2-\lambda_\max(H)^2 &\ \text{ if } \lambda_\max(H)>0,\\ \|A\|^2&\ \text{ otherwise}. \end{cases}

  • $\begingroup$ Presumably the largest eigenvalue has the smallest "leftover" $A-xx'$. $\endgroup$ – user856 Jan 7 '13 at 10:38
  • $\begingroup$ @RahulNarain Yes. You are right. $\endgroup$ – user1551 Jan 7 '13 at 11:23

This is a partial answer but completing it should be straight-forward.

Define the symmetric part of $A$ as $H=(A+A^T)/2$ and skew-symmetric part as $S=(A-A^T)/2$. Then for any symmetric matrix $X$, we have the identity \begin{align} ||A-X||_F^2=||H-X||_F^2+||S||_F^2 \end{align} To prove it, substitute $A=H+S$. Now, use the fact $||B||_F^2=trace(B^TB)$ for any matrix $B$ (take $B=A-X$), and also use $H=H^T$, $S=-S^T$.

Thus, finding the closest symmetric $X$ to $A$ is same as finding the closest $X$ to symmetric part $H$ of $A$. In your case, you have additional constraints on $X$. You need $X$ to be rank-one and positive-semidefinite which will then make $X=xx^T$ for some $x$. Please, read the following. The rest should be easy to figure out. I will be update it when I get time.

Best (not necessary symmetric) rank-one approximation

You are trying to find the best rank-one approximation of a given matrix $A$. If the SVD of $A=U\Sigma V^T$ is given, then $A_1=\sigma_1u_1v_1^T $, where $u_1$ and $v_1$ correspond to the left and right singular vectors corresponding to the largest singular value $\sigma_1$, is the best rank-one approximation. This is a standard thing and the proof can be found in any standard textbook explaining SVD. But if you are keen on finding the answer using differentiation, then I am not sure how I can help.

  • $\begingroup$ I wanted to fixed it, I didn't know there was a undelete option. Thanks for that!! :):) $\endgroup$ – dineshdileep Jan 7 '13 at 8:09
  • $\begingroup$ @adamW read the updated answer. You were right I guess $\endgroup$ – dineshdileep Jan 8 '13 at 3:57
  • $\begingroup$ Pretty much exactly what I was thinking. Thank you for typing it up. $\endgroup$ – adam W Jan 8 '13 at 4:27
  • $\begingroup$ +1 Although this is just a partial answer, I like the line that you split the Frobenius norm into a Hermitian part and a skew Hermitian part. $\endgroup$ – user1551 Jan 8 '13 at 10:25

I would like to show how the norm may be split as the sum of symmetric (Hermitian) and skew symmetric (skew Hermitian).

Let $A = H + S$ with $H = H^*$ and $S = -S^*$. Then \begin{align} \left(H+S\right)\left(H+S\right)^* &= HH^* + HS^* + SH^* + SS^* \\ &=HH^* -HS + SH + SS^*\\ \end{align} From the cyclic property of trace, $\operatorname{Trace}(HS) = \operatorname{Trace}(SH)$, and the middle terms cancel in the norm.

Thus we have $$\Vert A \Vert^2 = \Vert H+S \Vert^2 = \Vert H \Vert^2 + \Vert S \Vert^2$$

The addition of $\mathbf{x}\mathbf{x}'$ then affects only the symmetric portion since it is symmetric. Therefore, the original problem may be simplified using full symmetry, even if $A$ is not itself symmetric, as Dineshdileep noted.

  • $\begingroup$ +1 that was really nice! , you could have added that now one only needs the rank-one approximation of the symmetric part. :) $\endgroup$ – dineshdileep Jan 10 '13 at 3:28

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.