Closest matrix that achieves positive semidefinite condition

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.

• You might be able to formulate the problem as a semidefinite program – Ben Grossmann Jun 27 '20 at 23:25
• @Omnomnomnom I edited the question with an attempted proof. If you could have a look, I'd be very grateful! – user1936752 Jul 1 '20 at 14:37
• I don't see any issues with your proof, it seems as though you're right! – Ben Grossmann Jul 1 '20 at 15:13
• Thank you very much! – user1936752 Jul 1 '20 at 15:17

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}$$

• Great answer, thank you! It seems you've solved the problem, unless I am missing something? We want to minimize $|M|_1$ and regardless of $\alpha$ or $\beta$, this holds when $x^Ty$ is maximized. $x = y$ is therefore true. – user1936752 Jun 27 '20 at 21:42
• @user1936752 It's not that simple. Note that how large we can make $\beta$ without failing the $\tilde A \leq B$ condition depends on our particular choice of $y$. – Ben Grossmann Jun 27 '20 at 21:44
• @user1936752 So it could be that the $\tilde A \leq B$ condition forces $(\beta - \alpha)^2$ to be large in the case that $y = x$. – Ben Grossmann Jun 27 '20 at 21:48
• I see your point. But it's a very elegant perspective on the problem - thank you for this! – user1936752 Jun 27 '20 at 21:48