Closest matrix that achieves positive semidefinite condition

Question

Suppose we have two symmetric positive semidefinite $n$ dimensional matrices $A$ and $B$. We use the notation $X\leq Y$ means that $Y-X$ is positive semidefinite.

Suppose $A \not\leq B$ i.e. $B-A$ has at least one negative eigenvalue. We are interested in perturbing $A$ to some positive semidefinite $\tilde{A}$ such that $\tilde{A} \leq B$ while minimizing $|A-\tilde{A}|_1$ where $|\cdot|_1$ is the nuclear norm and defined by

$$|X|_1 := \text{Tr} \left( \sqrt{X^\dagger X} \right)$$

and $X^\dagger$ is the transpose conjugate of $X$.

To make things simpler, I will now consider the case where $A$ is a rank-$1$ matrix. Is it true that

$$\tilde{A} = \lambda A$$

for some $\lambda < 1$? An immediate corollary is that $\tilde{A}\leq A$.

---

EDIT: After a bit of searching, I found a result for the same question but where the norm considered is the induced 2-norm (spectral norm) or the Frobenius norm.

For the induced 2-norm (spectral norm), it holds that $\tilde{A} = A - \lambda I$ where $\lambda$ is the smallest positive number such that $\tilde{A}\leq B$ is true. So for this case, my conjecture that $\tilde{A} = \lambda A$ is false but the statement $\tilde{A}\leq A$ is true.

For the Frobenius norm case, we first write the polar decomposition of $B-A = UH$. Then $B -\tilde{A} = \frac{1}{2}(B - A + H)$ is the solution. Since $H= ((B-A)^\dagger(B-A))^{1/2}\geq B-A$, one can again conclude that $\tilde{A}\leq A$

I do not know what happens for the 1-norm though.

---

EDIT 2: Here is another look at the problem that almost works. Suppose the solution $\tilde{A}\not\leq A$. We prove that there exists some $A'$ such that $A'\leq B, A'\leq A$ and $|A'-A|_1\leq|\tilde{A}-A|_1$.

Let us diagonalize $\tilde{A}-A = ZDZ^\dagger = ZD^{+}Z^\dagger + ZD^{-}Z^\dagger$ where $D$ is diagonal, $D^{\pm}$ is also diagonal and includes the nonnegative and negative eigenvalues respectively. By assumption $\tilde{A}\leq B \implies A + ZD^{+}Z^\dagger + ZD^{-}Z^\dagger \leq B$. Define $A':= A + ZD^{-}Z^\dagger$.

Since $ZD^{+}Z^\dagger$ is positive semidefinite, it holds that $A' = A + ZD^{-}Z^\dagger \leq B$.

Since $ZD^{-}Z^\dagger$ is negative definite, it follows that $A'\leq A$.

Finally, $|A' - A|_1 = |ZD^{-}Z^\dagger|_1 = |D^{-}|_1 \leq |D^{+}+D^{-}|_1 = |Z(D^{+}+D^{-})Z^\dagger|_1 = |\tilde{A} - A|_1$

EDIT 3 Unfortunately, the $A'$ constructed is not positive semidefinite in general.

Answer 1

Some thoughts on the problem:

As a further simplification, I suggest that we say that $\tilde A$ does not only satisfy $\tilde A \leq B$, but also has a rank of $1$. If your hypothesis is correct, then this assumption should not change our answer. Write $$ A = \alpha xx^T, \quad \tilde A = \beta yy^T $$ for some scalars $\alpha, \beta > 0$ and unit vectors $x,y$. The minimization problem now becomes $$ \min_{y \in \Bbb R^n, \beta > 0} |\alpha xx^T - \beta yy^T|_1 \quad \text{s.t.} \quad \beta yy^T \leq B. $$ Now, I make several claims:

1. $yy^T \leq B \iff \beta \leq [y^TB^+y]^{-1}$ where $B^+$ denotes the Moore-Penrose pseudoinverse of $B$. I give some proofs of this here.

2. $\alpha xx^T - \beta yy^T$ has the same nuclear norm as that of the $2 \times 2$ matrix $\pmatrix{\alpha & \alpha (x^Ty)\\ -\beta (x^Ty) & -\beta}$. (explanation below).

3. The nuclear norm turns out to be $|M|_1 = \sqrt{(\beta - \alpha)^2 + 4(1 - (x^Ty)^2)}$.

My first approach would be to, by considering the nuclear norm as a function of $\beta$, maximize the nuclear norm given a particular choice of $y$.

---

The nuclear norm of a symmetric matrix is the sum of the absolute values of its eigenvalues. With that said, we want the eigenvalues of $M = \alpha xx^T - \beta yy^T$.

$$ M = \pmatrix{x & y} \pmatrix{\alpha & 0 \\ 0 & -\beta} \pmatrix{x & y}^T. $$ Because $AB,BA$ have the same non-zero eigenvalues, $M$ will have the same non-zero eigenvalues as the $2 \times 2$ matrix $$ N = \pmatrix{\alpha & 0 \\ 0 & -\beta} \pmatrix{x & y}^T\pmatrix{x & y} = \pmatrix{\alpha x^Tx & \alpha x^Ty\\ -\beta x^Ty & -\beta y^Ty}. $$

Point 3: $$ \lambda^2 + (\beta - \alpha) \lambda + ((x^Ty)^2 - 1)\alpha\beta \implies\\ \lambda = \frac{\alpha - \beta \pm \sqrt{(\beta - \alpha)^2 + 4(1 - (x^Ty)^2)}}{2} $$