Positive semidefinite ordering of matrices after small perturbations We use the notation $A\leq B$ to denote that $B-A$ is positive semidefinite. The notation $|\cdot |_1$ denotes the nuclear norm i.e. $|X|_1 = \operatorname{Tr}\sqrt{X^*X}$, where $X^*$ is the transpose conjugate of $X$.
Let $\rho$ and $\sigma$ be positive semidefinite matrices such that $\rho \leq \sigma$. Consider some positive semidefinite matrix $\omega$ which is close to $\sigma$ in nuclear norm i.e. $|\omega - \sigma|_1 \leq \varepsilon$. Does there always exist a positive semidefinite matrix $\tau$ such that
$$|\tau - \rho|_1 \leq \varepsilon \quad \text{and} \quad \tau \leq \omega$$
Note that the problem is quite easy if $\tau$ is not required to be positive semidefinite.
 A: No. Here is a counterexample. Let $\epsilon\in(0,1)$ be sufficiently small and
\begin{aligned}
A&=\pmatrix{2&1\\ 1&1},
\ B=\pmatrix{1&1\\ 1&1},\\
X&=\pmatrix{2&1\\ 1&1-\epsilon}.
\end{aligned}
Then $A\ge B\ge0,\,X\ge0$ and $|X-A|_1=\epsilon$. However, if $X\ge Y\ge0$, we must have
$$
1-\epsilon=x_{22}\ge y_{22}\ge0.\tag{1}
$$
It follows that
$$
|Y-B|_1\ge\sigma_1(Y-B)\ge|e_2^\ast(Y-B)e_2|=|y_{22}-b_{22}|=|y_{22}-1|\ge\epsilon.\tag{2}
$$
So, if $|Y-B|_1\le\epsilon$, ties must occur in all three inequalities in $(2)$. The tie in the first inequality implies that the rank of $Y-B$ is at most one. The tie in the second inequality implies that $e_2$ is both a left and a right singular vector corresponding to the largest singular value of $Y-B$. Hence $Y-B=(y_{22}-b_{22})e_2e_2^T$, i.e.
$$
Y=\pmatrix{b_{11}&b_{12}\\ b_{21}&y_{22}}=\pmatrix{1&1\\ 1&y_{22}}
$$
But the tie in the third inequality in $(2)$ also implies that $|y_{22}-1|=\epsilon$. By $(1)$, this means $y_{22}=1-\epsilon$. Hence $Y$ is not PSD, which is a contradiction.
