Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Does $(\mathbf A+\epsilon \mathbf I)^{-1}$ always exist, given that $\mathbf A$ is a square and positive (and possibly singular) matrix and $\epsilon$ is a small positive number? I want to use this to regularize a sample covariance matrix ($\mathbf A = \Sigma$) in practice, so that I can compute the inverse, which I need to calculate a Mahalanobis distance between two samples. In practice, my covariance matrix is often singular. I know the term $(\mathbf A+\epsilon \mathbf I)^{-1}$ often appears in the context of least squares problems involving Tikhonov regularization (ridge regression). However, I've never seen a statement, proof, or reference which says that the expression is always invertible.

Can any of you help me with a proof or reference?

share|improve this question
    
$\operatorname{det}(A+\epsilon X) = \operatorname{det}(A)+\operatorname{det}(A)\operatorname{tr}(A^{-1}X)\epsilon + O(\epsilon^2)$ –  tatterdemalion Sep 1 '12 at 20:18
1  
@Joe: While true, that doesn't help: it tells us $\det(A + \epsilon X) \in O(\epsilon^2)$ which doesn't rule out $0$. –  Hurkyl Sep 1 '12 at 20:24
    
It should be noted that the positivity of $\mathbf A$ is irrelevant to the question at hand. Also, the opening sentence of the question could mislead: The statement is indeed true for all sufficiently small $\epsilon>0$, but how small depends on $\mathbf A$. (I got tricked into thinking the questioner really meant “positive definite”, so I posted an answer based on that assumption. I have deleted it after @TonyK pointed out my mistake.) For the record, “positive” usually means all the matrix entries are positive. It can be seen from the answers that this does not enter into the argument. –  Harald Hanche-Olsen Sep 2 '12 at 6:41

5 Answers 5

up vote 9 down vote accepted

Recall that $\det(A-t I)=p_A(t)$ is the characteristic polynomial of $A$, which is a degree $N$ polynomial in $t$, where $N$ is the number of rows of $A$. Hence, it is a continuous function in $t$, and has at most $N$ roots, so there is some largest negative root $t_0$, or possibly no negative roots at all (in that case, choose $t_0=-1$ just for completeness). For all $0 < \epsilon < - t_0$, $p_A(-\epsilon)$ is nonzero, meaning that $\det(A+ \epsilon I) \ne 0$, so $A+\epsilon I$ is invertible.

EDIT: Corrected signs to agree with the question

share|improve this answer
    
Hey Logan, thanks for your answer and sorry for my late answer :) So, is it true that the proposed regularization method fails if $-\epsilon$ is equal (or close) to one of the eigenvalues of $\mathbf A$? –  benni Sep 3 '12 at 17:23
    
$A+ \epsilon I$ is invertible iff $-\epsilon$ is not an eigenvalue of $A$. In my above answer, $t_0$ is the largest (closest to 0) negative eigenvalue of $A$. So yes, you will have issues if $\epsilon$ is one of the eigenvalues (and potentially if they are close, though how close is hard to say). –  Logan Maingi Sep 3 '12 at 22:15
    
But in this question, $A$ is positive semidefinite (in fact $A$ is a sample covariance matrix), so we can make a stronger statement: $A + \epsilon I$ is positive definite (hence invertible) for all $\epsilon > 0$. –  littleO Nov 23 '12 at 15:42

To put it simple:

the set of invertible matrices is open in the normed space of all matrices.

Therefore if $A$ is invertible then $A+\epsilon I$ will also be invertible for small $\epsilon$.

share|improve this answer
    
And also if $\mathbf A$ is not invertible (for strictly positive $\epsilon$). –  TonyK Sep 1 '12 at 19:03
2  
I don't think just being open is enough. It means you can perturb an invertible matrix and if the perturbation is small enough, what you get is still invertible. But I think the question is: can even singular matrices be perturbed in the direction of the identity matrix, yielding an invertible matrix? –  Michael Hardy Sep 1 '12 at 22:09

Yes, if $\mathbf A$ is any $n \times n$ matrix, then $\mathbf A+\epsilon \mathbf I$ is invertible for sufficiently small $\epsilon > 0$. This is because $\det (\mathbf A + \epsilon \mathbf I)$ is a polynomial in $\epsilon$ of degree $n$, and so it has a finite number of zeroes.

share|improve this answer

Because the determinant function is continuous, and because $A$ is invertible if and only if $\det A \neq 0$, we have that $\det(A)\neq 0 \Rightarrow \det(A+\epsilon B)\neq 0$ for sufficiently small $\epsilon$, regardless of what $B$ is.

If $A$ is singular, then we note that the characteristic polynomial of $A$, given by $\operatorname{ch}_A(t)=\det(A-tI)$ is a polynomial in $t$, and therefore has finitely many roots. Then, whenever $\epsilon$ has absolute value less than the size of the smallest nonzero root $\det(A+\epsilon I)\neq 0$.

share|improve this answer

If $A$ is symmetric positive semidefinite, and $\epsilon > 0$, then $A + \epsilon I$ is symmetric positive definite (and hence invertible).

To see this, note that if $x \neq 0$ then \begin{align} x^T(A + \epsilon I) x &= x^T A x + \epsilon x^T x \\ &= x^T A x + \epsilon \|x\|^2 \\ & > 0. \end{align}

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.