1
$\begingroup$

Given a real-valued, symmetric matrix $A \in \mathbb{R}^{n \times n}$, I'm interested in finding the closest positive semi-definite matrix $X^*\in \mathbb{R}^{n \times n}$:

$$ X^* = \mathop{\text{argmin}}_{X \succcurlyeq 0} \| X - A \|_F^2 $$

One way I can solve this is by exploiting the eigendecomposition of $A$:

$$V \Lambda V^T = A$$

where $\Lambda$ is a diagonal matrix of eigenvalues. Then we have

$$X^* = V \max\left( \Lambda, 0 \right) V^T$$

where we've reconstructed from the eigen decomposition but clamped all the negative eigenvalues to zero.

If $A$ is a dense matrix, manifesting the eigendecomposition could take $O(n^3)$. Could we compute $X^*$ somehow more directly in a faster way?

In particular, now assume that $A$ has $k$ negative eigen-values. Would it be possible to construct an algorithm that ran in something like $O(kn^2)$ operations?

This way if my matrix $A$ is already positive definite, I'm not doing many more operations than just reading it in?

I suppose a corollary question to this might be, can you verify that a matrix is positive semi-definite in $O(n^2)$ operations?

Improve this question
$\endgroup$
5
  • $\begingroup$ Sorry if I'm being dull - why is the "clamped matrix" $V\operatorname{max}(\Lambda,0)V^T$ the closest positive semidefinite matrix to $A$? $\endgroup$
    – Neal
    Commented May 5, 2023 at 14:40
  • 2
    $\begingroup$ Here's my proof ‖ X - A ‖_F^2 = ‖ Vᵀ X - Vᵀ A ‖_F^2 = ‖ Vᵀ X V - Vᵀ A V ‖_F^2 = ‖ Vᵀ X V - Vᵀ VΛVᵀ V ‖_F^2 = ‖ Vᵀ X V - Λ ‖_F^2. This implies that VᵀXV should be diagonal: X→VΩVᵀ with Ω diagonal and in turn X ≽ 0 implies Ω ≥ 0. So we have ‖ Vᵀ VΩVᵀ V - Λ ‖_F^2 = ‖ Ω - Λ ‖_F^2 which now has a simple minimizer: Ωᵢᵢ = max( Λᵢᵢ, 0) apologies for no newlines in this comment. $\endgroup$
    – Alec Jacobson
    Commented May 5, 2023 at 14:52
  • 1
    $\begingroup$ This also seems to appear in [Sheung Hun Cheng and Nicholas Higham, A Modified Cholesky Algorithm Based on a Symmetric Indefinite Factorization, SIAM J. Matrix Anal. Appl. 19(4), 1097–1110, 1998] perhaps with a more solid proof. $\endgroup$
    – Alec Jacobson
    Commented May 5, 2023 at 14:53
  • 1
    $\begingroup$ @AlecJacobson This is mentioned in section 8.1.1 (page 399) of Boyd & Vandenberghe's Convex Optimization. $\endgroup$
    – Rodrigo de Azevedo
    Commented May 5, 2023 at 15:51
  • $\begingroup$ nhigham.com/2021/01/26/… $\endgroup$
    – Steve Huntsman
    Commented May 5, 2023 at 18:49

0

Reset to default

You must log in to answer this question.