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.
2
-
1$\begingroup$ Can you apply the same reordering to the original matrix and then use a norm? $\endgroup$– nicoguaro ♦Jan 24, 2017 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 BangerthJan 25, 2017 at 4:29
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
answered Jan 24, 2017 at 21:01
$\begingroup$
$\endgroup$
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.
