Suppose I have a diagonal matrix $D$ with nonnegative entries on the diagonal $\lambda_i$. Let the rank of $D$ be $r$. I am promised that $1-\delta \leq \sum_i\lambda_i \leq 1$ for some $0\leq\delta< 1$.
I am allowed to create a new matrix $D'$ that satisfies the following properties
- $D'$ is obtained by setting some of the eigenvalues $\lambda_i$ to zero.
- $\|D' - D\|_1 \leq \varepsilon$
Is it possible to bound the rank of $D'$ in the following way (or something similar)?
$$\text{rank}(D') \leq f(\varepsilon, \delta)\left(\sum_i\lambda_i^{1/2}\right)^2,$$
where $f(\varepsilon, \delta)$ is some "reasonable" function e.g. $\frac{1}{\varepsilon}$ that doesn't depend on the rank itself. The summation on the right hand side above is over all the eigenvalues of $D$.
My attempted solution:
I decided to discard the smallest eigenvalues. If $\lambda_i\leq \frac{\varepsilon}{r}$, I will replace them with $0$. This ensures that $\|D' - D\|_1\leq \varepsilon$ and intuitively seems right since it lowers the rank as much as possible. However, I am struggling to lower bound $\left(\sum_i\lambda_i^{1/2}\right)^2$.