12
$\begingroup$

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?

  • 0
    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.2012-09-02

5 Answers 5

13

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

  • 0
    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.2012-11-23
7

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.

  • 1
    @becko: I don't think that's possible. If $\mathbf A$ is singular, $\det ((\mathbf A + \epsilon \mathbf I)^{-1})$ will tend to infinity as $\epsilon \rightarrow 0$.2018-09-21
5

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}

2

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$.

  • 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?2012-09-01
2

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$.