# Fast projection onto semidefinite cone

Lots of algorithms for semidefinite programming make use of the Frobenius projection onto the cone of semidefinite matrices: $$\mathcal{P}(A) = \min_{X\succeq0} \|A-X\|_{\mathrm{Fro}}^2.$$ Let's assume $A$ is symmetric.

The standard trick for this projection is to compute the eigendecomposition of $A$ as $A=X\Lambda X^\top$, where $\Lambda$ contains eigenvalues of $A$ and $X$ is an orthogonal set of eigenvectors. Then, $\mathcal P(A)=X\max(\Lambda,0)X^\top.$ But, requires a full eigen-decomposition, which can be slow!

This post recommends computing the projection as $\mathcal{P}(A)=\frac{1}{2}(A+\sqrt{A^\top A})$, where $\sqrt{\cdot}$ denotes the matrix square root. Disappointly, Matlab's sqrtm() is slower than eig() in my tests.

What other algorithms could be used for this task?

Stochastic and deterministic techniques are both OK, so long as they have some convergence guarantee (with high probability?).

• Can you check out how matlab is computing sqrtm with edit sqrtm? My matlab is going through the complex Schur decomposition (schur), which is only slightly easier than a full eigendecomposition (which might use the Schur decomposition as well), which might explain why the sqrtm formula is not faster. There are other matrix-square-root algorithms that can be tried too. – Kirill Sep 8 '15 at 0:27
• My sqrtm references the following papers: - N. J. Higham, Computing real square roots of a real matrix, Linear Algebra and Appl., 88/89 (1987), pp. 405-430. - A. Bjorck and S. Hammarling, A Schur method for the square root of a matrix, Linear Algebra and Appl., 52/53 (1983), pp. 127-140. I tried implementing some other iterative methods from Higham's "Matrix Functions" book with no luck speed-wise. It appears eig() is hard to beat! – Justin Solomon Sep 8 '15 at 12:00
• The documentation for sqrtm() says that it's using a block Schur decomposition and references the papers that Justin mentioned above. – Brian Borchers Sep 8 '15 at 13:13