Positive Definitness

[clarazen]

Hello Boris,

Does the approximation of a kernel matrix with hss guarantee to preserve positive definiteness? If yes, how does it achieve that?

Thank you!

[mvsoom]

I would also like to know :)

[bonevbs]

Hi - sorry for the silence! Somehow, I overlooked this completely.

As it stands, there is no guarantee - unless I overlook something. A fundamental problem is that both compression algorithms decouple the block-diagonal part from the off-diagonal. Only the off-diagonal part is compressed and even if some properties are conserved on this part, there is no guarantee that the overall matrix remain positive definite.

That being said, the truncation of the off-diagonal part can be treated as a perturbation, whose error is bounded by the compression tolerance). This can help to bound the error in the eigenvalues which, depending on the size of the eigenvalues, might be sufficient for you to guarantee definiteness. (See Chapter 7.2.2, Eigenvalue Sensitivity, Golub and van Loan - Matrix Computations)

[mvsoom]

OK, thank you very much for your answer.

Since the block diagonal is conserved, I assume the rank of the matrix is expected to be conserved too?

[bonevbs]

No, imagine you have a matrix with all entries equal to one. If you set all the off-diagonal blocks to 0, your rank will have increased from one to something higher.