3
$\begingroup$

Is it possible to approximate an inverse of a sparse matrix with a sparse matrix? The problem comes up in numerical non-linear quasi-Newton optimization: given a sparse Hessian a good starting point for L-BFGS would be a sparse approximation of the Hessian's inverse, with the emphasis on sparsity of the matrix rather than the accuracy of approximation.

EDIT 1: Given Noam's counterexample, an approximation doesn't seem possible. However, the end practical purpose of an approximate sparse inverse is not as much its sparsity as the ability to represent the inverse matrix in a compact manner that won't require N^2 elements. There are matrices other than sparse ones that have this property: for example, Toeplitz matrices are representable with O(N) elements. Thus the follow-up question: is it generally possible to find an approximation of a sparse matrix that would also be presentable by O(N) elements?

EDIT 2: The problem should have been stated for symmetric matrices: it appeared from an attempt to invert a sparse Hessian, and Hessian is symmetric. Moreover, in many applied problems with a proper choice of coordinates the magnitude of mixed derivatives is known never to exceed the magnitude of the 2nd derivatives over the same variable. Thus the question should be augmented with these restrictions on the input matrix:

  1. Aij = Aji

  2. For any i,j |Aij| <= |Aii|

EDIT 3: Forgetting about the 2nd condition in EDIT 2, it is too specialized to the particular problem, and doesn't belong her. Let me rephrase based only on the 1st condition, that the matrix is symmetric (which is enough to disqualify the wonderful non-diagonal JNF example by Noam).

Given that the matrix is symmetric it could be diagonalized by applying orthogonal transformations. Diagonal form is, of course, invertible in O(N) into another diagonal matrix. In order to get to the original basis we would need to inverse the diagonalization transformation by applying the transition of the matrix that performed the diagonalization of the original matrix. Intuitively, the inverse orthogonal transformation would then spread the inverse diagonal matrix over the same positions where the non-zeros of the original matrix came from when it was being diagonalized. Since the original matrix was sparse it would seem that the inverse one would too.

What's wrong with this argument?

$\endgroup$
7
  • $\begingroup$ Regarding EDIT1, why isn't the formula "$A^{-1}$" a sparse presentation of $A^{-1}$? $\endgroup$ Aug 19, 2013 at 18:08
  • 2
    $\begingroup$ A key practical reason for interest in sparse matrices $A$ is that $Ax$ can be computed in much less than the $n^2$ multiplies that it takes to apply a general $n \times n$ matrix. The presentation $A^{-1}$ doesn't have this property because we don't know how to solve $Ax=b$ in less than $n^2$ steps even when $A$ is sparse. (For the elementary example I gave, $A^{-1}$ can be applied quickly because the entries of $A^{-1}b$ are partial sums of the entries of $b$; but that's a very special case.) $\endgroup$ Aug 19, 2013 at 18:20
  • 3
    $\begingroup$ Re EDIT2, if $A$ is the symmetric tridiagonal matrix with $(i,j)$ entry $1$ if $\left|i-j\right| \leq 1$ and $0$ otherwise then $A^{-1}$ is still a $0,\pm 1$ matrix with a positive density of nonzero entries. $\endgroup$ Aug 19, 2013 at 18:34
  • 1
    $\begingroup$ I don't know much about it, but I've listened to a couple of talks on a technique called "sparse approximate inverse" (SPAI) which tries to do what the name says. You may want to google that. $\endgroup$ Aug 19, 2013 at 19:12
  • 4
    $\begingroup$ As of Edit 3, I think this question is starting to drift, and MO is not really a good platform for conversations and modifications of questions. Perhaps there is a focused different question that could be asked in a new post? $\endgroup$
    – Yemon Choi
    Aug 19, 2013 at 19:43

2 Answers 2

11
$\begingroup$

Not in general. An explicit and elementary counterexample is the sparse triangular matrix with $1$'s on the diagonal and $-1$'s just above it: the inverse is the triangular matrix with every entry on or above the diagonal equal $1$.

$\endgroup$
4
$\begingroup$

$\newcommand{\Ag}{\mathcal{A}_\gamma}$ Not a full answer, put probably a fruitful pointer:

In the discretization of infinite dimensional problems one faces (bi-)infinite matrices. There, the Jaffard algebra $\Ag$ of bi-infinte matrices (for some $\gamma>1$) is $$ \Ag = \{A \ : \ |a_{k,l}|\lesssim (1+ |k-l|)^\gamma\}. $$ It can be shown that the Jaffard algebra is inverse closed, i.e. if $A\in \Ag$ is invertible, then $A^{-1}\in\Ag$ ("Optimal Adaptive Computations in the Jaffard Algebra and Localized Frames" by Dahlke et al. gives Gröchenig's "Localization of frames, Banach frames, and the invertibility of the frame operator" as a reference). In other words: a certain "off-diagonal decay" is preserved under inversion.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.