2

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?

Michael Hardy
  • 1
Jayden Rice
  • 303
  • Do you really need to compute the Hessian? It is an easy optimization if you use that the Frobenius norm is unitary invariant and consider the unitary diagonalization of $A$. – A.Γ. Jul 29 '21 at 22:57
  • In any case, solving for stationary points will give $x$ is the zero vector or $\det(A-xx^T)=0$. For the later, use e.g. Sylvester determinant theorem. – A.Γ. Jul 29 '21 at 23:08
  • $\nabla f(x) =0$ implies $Ax = (x^Tx)x$. Thus, $x^Tx = \lambda_k$ and $x = \mu u_k$ with some scalar $\mu$. If the $u_k$'s are normalized, this further leads to $x = \sqrt{\lambda_k}u_k$. These are your stationary points. – Friedrich Philipp Jul 30 '21 at 00:16
  • @FriedrichPhilipp Then what is the global maximizer? is it $x = \sqrt{\lambda_1}u_1$? And the global minimizer is $x = \sqrt{\lambda_n}u_n$? – Jayden Rice Jul 30 '21 at 00:24
  • Sorry. Your stationary points are $\pm\sqrt{\lambda_k}u_k$. And I get the Hessian $f''(x) = 4(3xx^T-A)$. – Friedrich Philipp Jul 30 '21 at 00:30
  • @FriedrichPhilipp I see. Then the global maximizer is $x=\sqrt{\lambda_1}u_1$ and global minimizer is $x=-\sqrt{\lambda_1}u_1$ ? – Jayden Rice Jul 30 '21 at 00:33
  • @JaydenRice Why? The Hessian is indefinite for every stationary point. – Friedrich Philipp Jul 30 '21 at 00:36
  • @FriedrichPhilipp Then how would I find global maximizer and global minimizer? If Hessian is indefinite, doesn't that mean that it is neither PSD nor NSD, thus neither global maximizer nor global minimizer? – Jayden Rice Jul 30 '21 at 00:41
  • @JaydenRice Exactly. Unless $n=1$, in which case you have global minima at $x=\pm\sqrt A$. – Friedrich Philipp Jul 30 '21 at 00:45
  • There won't be a global maximizer, since you can take $x$ with arbitrarily large [Euclidean] norm to make $f$ large. – angryavian Jul 30 '21 at 00:47
  • @FriedrichPhilipp Oh I see. One more question, sorry. How did you get the Hessian $4(3xx^T-A)$? – Jayden Rice Jul 30 '21 at 00:49
  • @JaydenRice Take $n=1$. Then $f(x) = (x^2-a)^2$, so $f'(x) = 4(x^3-ax)$ and $f''(x) = 4(3x^2-a)$. – Friedrich Philipp Jul 30 '21 at 00:53
  • @FriedrichPhilipp (1) I don't think the $3x^2$ generalizes to higher dimensions that directly. I'm getting $\text{diag}(x)^2 + 2 xx^\top$ in lieu of $3x^2$ since since $\frac{\partial}{\partial x_j} ((x^\top x) x_i) = \begin{cases} 3x_i^2 & j=i \ 2 x_i x_j& j \ne i\end{cases}$, although I may be mistaken. (2) If there is no global minimizer, isn't there a sequence approaching $\inf_x f(x) \ge 0$? Isn't this a special case of a low rank approximation problem, for which the solution is $\sqrt{\lambda_1} ; u_1$? – angryavian Jul 30 '21 at 00:55
  • @angryavian You are right. I was too fast. But your representation is not correct either. The correct Hessian is $\nabla^2 f(x) = 4\big[2xx^T + x^Tx\cdot I - A\big]$. – Friedrich Philipp Jul 31 '21 at 16:43
  • @FriedrichPhilipp You're right, thanks for catching my mistake in the Hessian computation. – angryavian Jul 31 '21 at 20:52

1 Answers1

2

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. $$

Friedrich Philipp
  • 4,051