Global minimizer and maximizer for $f(x):=\|A-xx^T\|^2_F$ Consider $f(x):=\|A-xx^T\|^2_F$, where $A \in \mathbb{R}^{n \times n}$ a symmetric matrix and positive eigenvalues $\lambda_1>\lambda_2>\cdots>\lambda_n>0$ with corresponding eigenvectors $u_1,u_2,\ldots,u_n$
I want to compute gradient and Hessian of $f(x)$, find all stationary points, and find the global minimizer and maximizer, and finally show that other stationary points have the Hessian that is neither PSD nor NSD.
So far, I did:
$$f(x)=\|A-xx^T\|^2_F = \|A\|^2_F -2\operatorname{tr}(x^TAx) + \operatorname{tr}(xx^Txx^T),$$
thus,
$$\nabla f(x) = 4(xx^T-A)x$$
Setting equal to 0, all the stationary points are $x$ such that
$$(xx^T-A)x = O_{n \times n}$$
Then the Hessian $\nabla^2 f(x) = 4(x^Tx) + 4(xx^T-A) = 8xx^T-4A$
I am stuck at this point. From here, how do I find which stationary point is the global minimizer and maximizer?
I think it has something to do with Hessian, but how do I do it? Also, how do I show that every other stationary points have Hessian that is neither PSD nor NSD?
 A: The Hessian of your matrix is
$$
\nabla^2 f(x) = 4\big[2xx^T + x^Tx\cdot I - A\big].
$$
Let's insert the stationary points $x_k = \pm\sqrt{\lambda_k}u_k$. I assume that the eigenvectors $u_k$ are normalized. You have
\begin{align*}
\tfrac 14\nabla^2 f(x_k)
&= 2\lambda_k u_ku_k^T + \lambda_k \cdot I - A\\
&= 2\lambda_k u_ku_k^T + \lambda_k\sum_ju_ju_j^T - \sum_j\lambda_j u_ju_j^T\\
&= \sum_{j\neq k}(\lambda_k - \lambda_j)u_ju_j^T + 2\lambda_k u_ku_k^T.
\end{align*}
Now, the matrix $\sum_j\alpha_j u_ju_j^T$ is positive (negative) definite if and only if $\alpha_j>0$ ($\alpha_j < 0$) for all $j$ and indefinite if and only if there are $\alpha_j < 0$ and $\alpha_k>0$. Looking at the above expression, we see that $\nabla^2 f(x_k)$ is always indefinite unless $k = 1$ (the index of the largest eigenvalue), for which it is positive definite. Hence, the points $\pm\sqrt{\lambda_1}u_1$ are local minima of $f$. But as
$$
f(x) = \|A\|_F^2 - 2\langle Ax,x\rangle + \|x\|^4\ge \|A\|_F^2 - 2\lambda_n\|x\|^2 + \|x\|^4
$$
tends to $\infty$ as $\|x\|\to\infty$, your minima are global. The minimal function value is
$$
f(x_k) = \|A\|_F^2 - 2\lambda_1\langle Au_1,u_1\rangle + \|\sqrt{\lambda_1} u_1\|^4 = \sum_j\lambda_j^2 - 2\lambda_1^2 + \lambda_1^2 = \sum_{j=2}^n\lambda_j^2.
$$
