Why does adding a value to the diagonal of the matrix stabilise it? Why not add the value to all elements?
So, before I use Cholesky to find the x in Ax=b, I was told to add a regularisation paramter to the diagonal of my A.
Asked
Active
Viewed 2,121 times
2 Answers
2
Adding a positive constant $c$ to the diagonal entries of matrix $A$ amounts to replacing $A$ with $A+cI$. The effect on characteristic polynomial is the shift: $p$ becomes $p(\lambda-c)$. Hence, all eigenvalues are shifted to the right by $c$. In particular, a positive semidefinite matrix becomes positive definite.
Adding a positive constant $c$ to all entries has a complicated effect on the characteristic polynomial. The eigenvalues do not necessarily move to the right. In particular, a positive semidefinite matrix does not necessarily become positive definite. Example: $$\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} + \begin{pmatrix} c & c \\ c & c \end{pmatrix} = \begin{pmatrix} 1+c & 1+c \\ 1+c & 1+c \end{pmatrix}$$
Post No Bulls
- 9,056
-
Thanks a lot. That makes some sense, just need to keep reading :) – user1876942 Dec 10 '13 at 09:06
0
If I correctly understand, you want to solve the equation $Ax=b$ where $A> 0$ but has a very small eigenvalue. In such a case, the Cholesky method is unstable. If you change $A$ with $B=A+\lambda I$ with $\lambda >0$, then you can numerically solve $Bx=b$. Firstly $\lambda$ cannot be very small, otherwise the Cholesky method works badly. Secondly, what do you do with your approximation ?
A better way is using this robust Cholesky method http://math.berkeley.edu/~cinnawu/hss.pdf
-
I am doing some DSP. Once I have x, I used it to update some FIR taps so that the signal is transformed. – user1876942 Dec 10 '13 at 09:08