Optimal symmetric rank-1 approximation

Question

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.

Answer 1

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}

Answer 2

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.

Answer 3

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.