Matrix optimization problem for sparseness and closeness.

Question

If I have a matrix $${\bf M}= \left[\begin{array}{l}{\bf M_k+\epsilon}\\{\bf M_u}\end{array}\right], \cases{{\bf M_k} \text{ known}\\{\bf M_u} \text{ unknown}}$$

How can I then find $\bf \epsilon$ (matrix) which is minimal (or regularized) in some norm and that $\bf M_u$ and $\bf M_k+\epsilon$ is sparse, ${\bf M}^{-1}$ exists and is also sparse?

Answer 1

There's a body of research on finding a sparse matrix that is an approximate inverse for a given matrix. This is used to find an approximate inverse for a sample covariance matrix which typically isn't of full rank and thus doesn't have an exact inverse.

See for example:

Sun, Tingni, and Cun-Hui Zhang. "Sparse matrix inversion with scaled lasso." The Journal of Machine Learning Research 14.1 (2013): 3385-3418.

Let

$U=\left[ \begin{array}{c} M_{k} \\ 0 \end{array} \right] $

Then find a sparse matrix $V$ such that

$UV \approx I$.

Here "approximately" is measured by the spectral norm, $\| UV - I \|$. The $V$ matrix would then be your $M^{-1}$.

Note that although $UV$ is approximately $I$, this doesn't mean that $V^{-1}$ will be very close to $U$ or that $V^{-1}=M$ would necessarily be sparse.