Suppose I have some positive semidefinite matrix $A$ with rank $r$. I would like to write down a positive semidefnite matrix $B$ of rank $(r-1)$ such that $|A - B|_1$ is minimal where $|X|_1 = Tr[(X^\star X)^{1/2}]$ and $X^ \star$ is the tranpose conjugate of $X$.
Obviously, one way to achieve this is to diagonalize $A$ and then simply replace its smallest eigenvalue, $\lambda_{\min}$, with zero. Call this matrix $B$. This reduces the rank by 1 and $|A - B|_1 = \lambda_{\min}$.
Is it possible to show that this is $B$ is indeed the optimal matrix that decreases the rank while minimizing $|A - B|_1$? In particular, this shows that $A$ and $B$ share a common eigenbasis.
Yes, this is possible. Keep in mind that you should not replace the minimum eigenvalue but rather the one which is smallest in absolute value. That this is the best rank $r-1$ approximation to your matrix $A$ can be proved by using the singular value decomposition of $A$. See the section on low-rank matrix approximation using the SVD on Wikipedia.