4
$\begingroup$

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?).

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Kirill Sep 8 '15 at 0:27
  • $\begingroup$ 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! $\endgroup$ – Justin Solomon Sep 8 '15 at 12:00
  • $\begingroup$ The documentation for sqrtm() says that it's using a block Schur decomposition and references the papers that Justin mentioned above. $\endgroup$ – Brian Borchers Sep 8 '15 at 13:13
1
$\begingroup$

You can potentially save some effort in the eigenvalue decomposition by finding only those eigenvalues (and the corresponding eigenvectors) that are greater than 0. If most eigenvalues are non-negative, then you can find the negative eigenvalues and subtract off that part of the eigenvalue decomposition to compute the projection. The LAPACK routine DSYEVR can be helpful.

I haven't found a faster way to do this computation yet, but I'd be interested in a faster approach to the projection that worked by way of the matrix square root or some other approach.

$\endgroup$
  • $\begingroup$ Thanks! This definitely shaves off time in many cases, especially if we have some estimate of the spectrum a priori. But somehow this projection seems like an "easier" problem than computing eigenvalues! Maybe this intuition is wrong, though :-) $\endgroup$ – Justin Solomon Sep 8 '15 at 12:02

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.