1
$\begingroup$

I have a large dense matrix $A$. For simplicity in simulation purposes and application demand, I induced sparsity by replacing lower/insignificant values by zero and reordering it in block diagonal form e.g $\hat{A}$. How can I measure how much information I lost in this process? What property of matrix represents it's index of information. (It can not be distance as I reorder the elements ) Thank you very much in advance.

$\endgroup$
  • 1
    $\begingroup$ Can you apply the same reordering to the original matrix and then use a norm? $\endgroup$ – nicoguaro Jan 24 '17 at 19:38
  • 3
    $\begingroup$ What is it you want to do with either the original or the sparsified matrix? One can come up with a great many ways of expression by how much the two differ, but ultimately which measure is useful depends on what you want to do with the matrix. $\endgroup$ – Wolfgang Bangerth Jan 25 '17 at 4:29
1
$\begingroup$

There are multiple ways to judge the information lost. The easiest way would be to calculate Frobenius norm of the, so called, sparsified matrix $\hat A$ and an original dense matrix.

$||A||_F=\sqrt{\sum\limits_{i}\sum\limits_{j}|a_{ij}|^2}$

The relative error in the Frobenius norm can tell you something about how much you have dropped relatively:

$\text{Error}_F=\frac{||A-\hat A||_F}{||A||_F}$

Also, Frobenius norm has nice connection to the spectral properties of the matrix which might be useful: $||A||_2\leq||A||_F$.

However, judging just "element-wise" is not very good, as well as just simply zeroing out allegedly small and insignificant blocks. I would start from plotting the singular values of the original matrix and compared them to the ones of the approximated one. That would allow you to judge how did you change the spectrum properties.

In the conclusion, I would suggest you take a look into various techniques that allow for fast matrix algebra for similar approximations, like $\mathcal H$-matrices (http://www.hmatrix.org/), HSS (hierarchical semi-separable), and others, rather than just dropping the matrix entries below a certain threshold. However, for your application your approach might be accurate enough.

$\endgroup$
0
$\begingroup$

You are perturbing the initial system. If you wish to solve the system $Au=f$

By perturbing the system you solve

$(A+\Delta A)(u+\Delta u)=f$

Hence,

$\Delta A \Delta u= f$

$\Delta u= \Delta A^{-1} f$

For a submultiplicative norm $||$ $||$

$|| \Delta u||=||\Delta A^{-1} f||$

$||\Delta u||<||\Delta A^{-1}||$ $|| f||$

The norm can gives the upper limit of the effect of the perturbation.

$\endgroup$

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.