Projection onto a positive semidefinite trace ball (source code)

= Projection onto a positive semidefinite trace ball

Let $M$ be a real <symmetric matrix> with <eigenpairs> $(\mu_i,v_i)$, and take trace radius $s\ge0$. Its <Frobenius norm> projection onto the <positive semidefinite trace ball> is obtained by thresholding its <eigenvalues>. If $s=0$, the projection is zero. If $\sum_i(\mu_i)_+\le s$, it is $\sum_i(\mu_i)_+v_iv_i^T$. Otherwise $s>0$ and
$$
\Pi_{\mathcal S_s}(M)=\sum_i(\mu_i-\rho)_+v_iv_i^T,
\qquad\sum_i(\mu_i-\rho)_+=s.
$$
In this last case $\rho>0$ is unique: the left side is continuous, strictly decreasing while positive, starts above $s$ at zero and reaches zero at $\max_i\mu_i$.

To prove the reduction, use an <orthonormal eigenbasis> of $M$. Replacing a feasible matrix by its diagonal part in that basis preserves nonnegative diagonal entries and the trace, hence remains positive semidefinite, while deleting off-diagonal entries decreases the squared Frobenius distance. The problem becomes projection of $\mu$ onto $\{z\ge0:\sum_i z_i\le s\}$. Its multiplier equations give $z_i=(\mu_i-\rho)_+$ with the stated inactive-constraint case.

For $M=\operatorname{diag}(3,-1,2)$ and $s=2$, the threshold $\rho=3/2$ gives $\operatorname{diag}(3/2,0,1/2)$. At radius zero the threshold itself need not be unique, although the projected matrix is; this is why that case is stated separately.