5
$\begingroup$

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.

$\endgroup$
5
  • $\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
    Commented Jan 7, 2013 at 5:13
  • 3
    $\begingroup$ what's the definition of the matrix norm? $\endgroup$
    – chaohuang
    Commented Jan 7, 2013 at 5:14
  • $\begingroup$ Is $A$ a symmetric matrix? $\endgroup$
    – user17762
    Commented Jan 7, 2013 at 6:08
  • $\begingroup$ Added clarifications. Marvis -- I'm interested in both symmetric and general cases $\endgroup$ Commented Jan 7, 2013 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
    Commented Mar 24, 2013 at 14:45

3 Answers 3

3
$\begingroup$

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}

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

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.

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

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .