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?

  • 1
    $\begingroup$ 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$… $\endgroup$ – Dirk Jun 11 '18 at 19:04
  • $\begingroup$ 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 $\endgroup$ – user3095304 Jun 12 '18 at 10:13

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.