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?



Maximise singular value decay by sparse matrix approximation
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](https://youtu.be/LUcg-ohZo6w), Simons Institute, September 2014.


