Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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}$). –  adam W Jan 7 '13 at 5:13
2  
what's the definition of the matrix norm? –  chaohuang Jan 7 '13 at 5:14
    
Is $A$ a symmetric matrix? –  user17762 Jan 7 '13 at 6:08
    
Added clarifications. Marvis -- I'm interested in both symmetric and general cases –  Yaroslav Bulatov Jan 7 '13 at 8:10
    
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. –  adam W Mar 24 '13 at 14:45

3 Answers 3

up vote 3 down vote accepted

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}

share|improve this answer
    
Presumably the largest eigenvalue has the smallest "leftover" $A-xx'$. –  Rahul Jan 7 '13 at 10:38
    
@RahulNarain Yes. You are right. –  user1551 Jan 7 '13 at 11:23

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.

share|improve this answer
    
+1 that was really nice! , you could have added that now one only needs the rank-one approximation of the symmetric part. :) –  dineshdileep Jan 10 '13 at 3:28

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.

share|improve this answer
    
I wanted to fixed it, I didn't know there was a undelete option. Thanks for that!! :):) –  dineshdileep Jan 7 '13 at 8:09
    
@adamW read the updated answer. You were right I guess –  dineshdileep Jan 8 '13 at 3:57
    
Pretty much exactly what I was thinking. Thank you for typing it up. –  adam W Jan 8 '13 at 4:27
    
+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. –  user1551 Jan 8 '13 at 10:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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