I have a large matrix $A \in \mathbb{R}^{n \times m}$ and would like to subtract a sparse matrix $B \in \mathbb{R}^{n \times m}$ with less than $c (n+m)$ non-zero entries, where $c > 0$ is a constant one is free to choose, such that the singular values of $A-B$ decay as quickly as possible.
I have no idea how to approach this problem. Any thoughts?
Maximizing the "decay" of the singular values could be thought of as minimizing the (numerical) rank. Hence, I believe that the original problem could be rephrased as follows:
Given $\mathrm A \in \mathbb R^{m \times n}$, find a sparse matrix $\mathrm X \in \mathbb R^{m \times n}$ such that $\mbox{rank} (\mathrm X - \mathrm A)$ is minimized.
which is hard. Convex proxies$^\dagger$ for sparsity and rank are the entry-wise 1-norm and the nuclear norm, respectively. Hence, relaxing the original problem, we obtain the following convex program
$$\begin{array}{ll} \underset{\mathrm X \in \mathbb R^{m \times n}}{\text{minimize}} & \| \mathrm X \|_1 + \gamma \| \mathrm X - \mathrm A \|_*\\ \end{array}$$
where $\gamma > 0$. Varying parameter $\gamma$, if we find a matrix $\rm X$ that is sufficiently sparse, we are done.
$\dagger$ Maryam Fazel, Recovering simultaneously structured objects, Simons Institute, September 2014.
