Hey all, i am computing sample autocorrelation for some continouous valued data (using this: https://ccrma.stanford.edu/~jos/sasp/Sample_Autocorrelation.html) but the generated correlation matrix has negative eigenvalues. Is there a way to fix the autocorrelation matrix to have non-negative eigenvalues? I always thought that the sample correlation matrix should have been positive semidefinite. thanks.
sample autocorrelation matrix eigenvalues negative
Started by ●November 29, 2011
Reply by ●November 29, 20112011-11-29
On 29 Nov, 10:08, "doublehelics" <ozgun.harmanci@n_o_s_p_a_m.gmail.com> wrote:> Hey all, i am computing sample autocorrelation for some continouous valued > data (using this:https://ccrma.stanford.edu/~jos/sasp/Sample_Autocorrelation.html) but the > generated correlation matrix has negative eigenvalues. Is there a way to > fix the autocorrelation matrix to �have non-negative eigenvalues? I always > thought that the sample correlation matrix should have been positive > semidefinite. thanks.'Positive semidefinite' means that some eigenvalues might be 0. If so, there is a possibility that computational errors push some eigenvalues to the negative side, but with very small magnitudes. If you can reliably detect these cases, treat the eigenvalue as it is 0. If the negative eigenvalues have large magnitude compared to the numerical precision of the results, then something else is going on. Contact whoever set up the example you quote. Rune
Reply by ●November 29, 20112011-11-29
On 2011-11-29 06:03:41 -0400, Rune Allnor said:> On 29 Nov, 10:08, "doublehelics" > <ozgun.harmanci@n_o_s_p_a_m.gmail.com> wrote: >> Hey all, i am computing sample autocorrelation for some continouous valued >> data (using >> this:https://ccrma.stanford.edu/~jos/sasp/Sample_Autocorrelation.html) >> but the >> generated correlation matrix has negative eigenvalues. Is there a way to >> fix the autocorrelation matrix to �have non-negative eigenvalues? I always >> thought that the sample correlation matrix should have been positive >> semidefinite. thanks. > > 'Positive semidefinite' means that some eigenvalues > might be 0. If so, there is a possibility that > computational errors push some eigenvalues to the > negative side, but with very small magnitudes. > > If you can reliably detect these cases, treat the > eigenvalue as it is 0. > > If the negative eigenvalues have large magnitude > compared to the numerical precision of the results, > then something else is going on. Contact whoever > set up the example you quote. > > RuneThe problem with autocorrelations is that there are two common estimators in use. One is unbiased and the other is positive definite. The unbiased estimator is not positive definite and the positive definite estimator is not unbiased. Both are the same in the limit of large N so both are consistent estimators The unbiased estimator has the N-t divisor while the positive definite estimator has the N divisor. If you compute the autocorreleation by FFT-magnitude-inverse FFT you will get the positive definte estimator. The unbiased estimator is more common if you are summing lagged products where the divisor of N-t is more natural. The OP will have to specify which estimaor is in use. Negative eigenvalues can be expected from the unbiased estimator but are a numerical problem for the positive definite estimator. Nonzero means can cause numerical problems for variance estimators due to roundoff in cancellation.
Reply by ●December 2, 20112011-12-02
On Nov 29, 4:08�am, "doublehelics" <ozgun.harmanci@n_o_s_p_a_m.gmail.com> wrote:> Hey all, i am computing sample autocorrelation for some continouous valued > data (using this:https://ccrma.stanford.edu/~jos/sasp/Sample_Autocorrelation.html) but the > generated correlation matrix has negative eigenvalues. Is there a way to > fix the autocorrelation matrix to �have non-negative eigenvalues? I always > thought that the sample correlation matrix should have been positive > semidefinite. thanks.There are numerous fixes. I would first look at the SVD of your sample correlation estimate. If you see a negative singular value, something is wrong. The easiest solution is to diagonally load the matrix. That pushes the eigenvalues equally in the positive direction. You typically have to play with the data to figure out an appropriate loading scaler. For a problems assumed stationary, some people average over diagonals and force the matrix to be Toeplitz. This sort of works, sometimes. Again for problems assumed stationary, average the flip-up-down( flip- left-right) sample covariance with the sample covariance. I would recommend using a rank-1 update approach. Typically, a covariance matrix inverse is the desired entity down stream, so building a factorization from the data is usually best. It is also is more numerically stable. There are rank one update algorithms for Cholesky, QR, eigenvector, and I think even for an SVD. There are a lot of papers on covariance estimation. These are just a few tricks.