Preserving positive-definiteness after “contaminating” a matrix with noise.

Let $\Sigma$ be a $n\times n$ symmetric positive definite matrix, i.e., $\Sigma\in\mathbb{S}_{++}^n$. For instance, let $\Sigma$ be the covariance matrix of a $n$-dimensional normal distribution. It is desired to contaminate $\Sigma$ with some "noise", such that the positive definiteness condition is preserved.

As a first approach, credited to @Giannis, we take the Singular Value Decomposition (SVD) of $\Sigma$, $$\Sigma=VDV^T,$$ where $D=\operatorname{diag}\{\lambda_1,\cdots,\lambda_n\}$ is the diagonal (positive) eigenvalues of $\Sigma$, and $V$ is an orthogonal matrix. We may contaminate the eigenvalues of $\Sigma$ with some uniform noise as follows $$\lambda_i'=\lambda_i+r_i,$$ where $r_i$ is a random non-negative real number drawn uniformly from the interval $[0,a_i]$, where $a_i\in\mathbb{R}_+$, $i=1,\cdots,n$. Then, the diagonal matrix $D'$ is composed with the above (noisy) eigenvalues, $\lambda_i'$. That is, $$D'=\operatorname{diag}\{\lambda_1',\cdots,\lambda_n'\}.$$ Using the same orthogonal matrix computed by SVD on $\Sigma$, $V$, we construct a new matrix $\Sigma'$, such that $$\Sigma'=VD'V^T,$$ which preserves positive-definiteness and symmetry.

How does it seem to you? Is it correct? If so, is there any other way to contaminate a symmetric positive definite matrix with noise without violating the above conditions?

It would be nice if @user1551 could extend his/her thoughts on Gershgorin circle theorem.

• I don't have enough reputation to comment, so I'll just say that rho of a matrix in the context of user1551's answer is the spectral radius = largest eigenvalue. – mshaughnessy Jun 19 '15 at 21:12

Why don't you make $\Delta$ also positive definite, in addition to its symmetry property? Use $\Sigma ' = \Sigma +\Delta^T \Delta$, where $\Delta$ has been replaced by $\Delta^T\Delta$.

I am not sure, however, whether the new matrix $\Delta^T\Delta$ retains the initial by construction properties. Is this a problem for you?

• Thanks @Giannis, your solution seems more suitable for me, although user1551's approach seems more challenging in understanding and applying... Have you taken a look at? – nullgeppetto May 7 '14 at 7:43

Suppose $\Sigma' = \Sigma + \Delta$ for some real symmetric matrix $\Delta$.

One sufficient condition for $\Sigma'\succ0$ is that $\rho(\Delta)<\lambda_\min(\Sigma)$. And one sufficient for $\rho(\Delta)<\lambda_\min(\Sigma)$ is that $\|\Delta\|_\infty<\lambda_\min(\Sigma)$ (Gershgorin disc theorem). So, you may try to control the sum of moduli of $\Delta$'s entries for each row.

• I think you typo'd moduli! – BananaCats Category Theory App May 6 '14 at 23:24
• @user1551, could you be a bit more specific about that? First, what $\rho$ stands for? Where exaclty (in what step) does the Gersgorin theorem participates? Finally, why the moduli? Sorry for being ignorant... Thanks again! – nullgeppetto May 7 '14 at 8:15
• @user1551, I've made some edits on my original post. If you'd like, take a look! – nullgeppetto May 7 '14 at 10:48