# Maximise singular value decay by sparse matrix approximation

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?

• How would you quantify "as quickly as possible"? The singular values are a just a finite tuple, so they are bounded by any $Ki^{-s}$ or $Kq^i$… – Dirk Jun 11 '18 at 19:04
• Good question: I think a reasonable choice would be to fix a number $r\leq \min\{m,n\}$ and try to minimize $\sum_{i=r+1}^{\min\{m,n\}} |\sigma_i|^2$, where $\sigma_i$ are the singular values of $A-B$ in decreasing order – user3095304 Jun 12 '18 at 10:13

## 1 Answer

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.