4
$\begingroup$

Consider $\mathbb{S}^n$, the set of all $n\times n$ real symmetric matrices. Let $A\in \mathbb{S}^n$ and $A=U\Lambda U^{\top}$ be its spectral decomposition. I want to know how to prove that $\Pi_{\Bbb S_+^n}(A)=U\Lambda ^+U^{\top}$, where $\Lambda^+$ is the $n\times n$ diagonal matrix given by $\Lambda_{ii}^+=\max\{\Lambda_{ii}, 0\}$, for $i=1,...,n$;$\Pi_{S}(x)=\arg\min_{z\in S}\|x-z\|^2_2$.

This projection means that we can project any symmetric matrix on $\mathbb{S}_+^n$ and get the closest positive semi-definite matrix, but how can we prove that it is the closest one?

$\endgroup$
2
  • $\begingroup$ Show that $\Pi_S(U A U^T) = U \Pi_S(A) U^T$ (as long as $USU^T = S$). Solving the problem for diagonal $A$ should be straightforward. $\endgroup$ – copper.hat Sep 19 '17 at 14:44
  • $\begingroup$ Also think carefully about what norm you're using for "closest." $\endgroup$ – Brian Borchers Sep 19 '17 at 14:53
1
$\begingroup$

$\Pi_{\mathbb{S}_+^n}(A)=\arg\min_{X \in \mathbb{S}_+^n}\|X-A\|^2_F=\arg\min_{X \in \mathbb{S}_+^n}\|\Lambda_X -V^{\top}A V\|^2_F$

$X = V \Lambda_X V^{\top}$ (as $X\in \mathbb{S}^n_+$, so it is diagolalizable), $B=V^{\top}A V$

$\|\Lambda_X -V^{\top}A V\|^2_F = \sum_{i \neq j}b_{ij}^2+\sum_i (\Lambda_{X_{ii}}-b_{ii})^2$

Minimum occurs when $b_{ij}=0$, and $\Lambda_{X_{ii}}=b_{ii}$. Note that $\Lambda_{X_{ii}} \geq 0$, so $\Lambda_{X_{ii}}=\max\{0,b_{ii}\}.$ $B$ is a diagonal matrix. So, $V=U$.

$\endgroup$
1
$\begingroup$

There is a subtle point missing in Rajat's answer, so I will repeat the proof:

Let $A = U\Lambda U^\top$ be the eigenvalue decomposition of $A$. Then we have $$ \min_{X\succeq 0} \|X-A\|_F^2 = \min_{X\succeq 0} \|X-U\Lambda U^\top\|_F^2=\min_{X\succeq 0} \|U^\top X U-\Lambda\|_F^2. $$

Now here is the subtle point: The matrix $B\equiv U^\top X U$ must be diagonal. Why?

First, whenever $\lambda_{ii}\geq 0$ we can set $b_{ii}=\lambda_{ii}$ to get zero error for those elements. Regarding the terms where $\lambda_{ii}< 0$, since $B$ is also psd it must have non-negative diagonal, so the best we can do is put $b_{ii}=0$. One might think that it's possible to put there a negative value which will decrease the error, and somehow take care of the psd constraint by carefully distributing the off-diagonal elements, but negative diagonal elements would violate the constraint. As for the off-diagonal elements - anything diffeent than $0$ would increase the error.

The solution is then given by $X = U \left(\max\left(\Lambda,0\right)\right) U^\top$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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