# Find the matrix projection of a symmetric matrix onto the set of symmetric positive semi definite (PSD) matrices

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?

• 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. Sep 19, 2017 at 14:44
• Also think carefully about what norm you're using for "closest." Sep 19, 2017 at 14:53

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

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