计算科学 - 快速投影到半定锥上 - 吾爱随笔录

许多半定规划算法利用 Frobenius 投影到半定矩阵的圆锥上：

P (A) = min_{X ⪰ 0} ‖ A - X ‖_{F r o}^{2} .

$\mathcal{P}(A) = \min_{X\succeq0} \|A-X\|_{\mathrm{Fro}}^2.$ 让我们假设

A

$A$ 是对称的。

这个投影的标准技巧是计算特征分解 $A$ 作为 $A=X\Lambda X^\top$ ，在哪里 $\Lambda$ 包含的特征值 $A$ 和 $X$ 是一组正交的特征向量。然后， $\mathcal P(A)=X\max(\Lambda,0)X^\top.$ 但是，需要完整的特征分解，这可能很慢！

这篇文章建议将投影计算为 $\mathcal{P}(A)=\frac{1}{2}(A+\sqrt{A^\top A})$ ，在哪里 $\sqrt{\cdot}$ 表示矩阵的平方根。令人失望的是，Matlab 的sqrtm()速度比eig()我的测试要慢。

还有哪些其他算法可用于此任务？

随机和确定性技术都可以，只要它们有一些收敛保证（很有可能？）。