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.
 A: 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:

*

*$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.


*$\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).


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