6
$\begingroup$

It is well known that estimating the covariance matrix by the ML estimator (sample covariance) can be very numerically unstable (in high dimensions), which is why it is preferable to do PCA with the SVD, for example. But I haven't been able to find an intuitive explanation of why this is the case.

For matrix inversions it is clearer where the numerical instability arises, but a covariance matrix for (centered and standardized data) is just the seemingly innocuous product: XX'

EDIT: here is a reference: Regularized estimation of large covariance matrices

$\endgroup$
4
  • 1
    $\begingroup$ Is the answer by user11852 below what you were looking for? I'm curious. As far as I'm aware, just estimating the covariance by sample covariance is stable. Can you post a reference to the claim that it isn't? $\endgroup$
    – Yair Daon
    Commented Nov 14, 2016 at 1:32
  • 1
    $\begingroup$ While I think the question is really interesting I find the title a bit misleading. Something like: "Intuition as to why estimates of a covariance matrix are numerically unstable" would reflect more properly what you as in the body of the question as well as what is the problem the linked paper is concerned with. (Obviously I +1ed the question.) $\endgroup$
    – usεr11852
    Commented Nov 14, 2016 at 21:05
  • 1
    $\begingroup$ @usεr11852 thank you, I updated the title with your suggestion $\endgroup$
    – luffe
    Commented Nov 15, 2016 at 11:49
  • $\begingroup$ @luffe: Good move! $\endgroup$
    – usεr11852
    Commented Nov 15, 2016 at 20:30

1 Answer 1

6
$\begingroup$

The reason that the SVD of the original matrix $X$ is preferred instead of the eigen-decomposition of the covariance matrix $C$ when doing PCA is that that the solution of the eigenvalue problem presented in the covariance matrix $C$ (where $C = \frac{1}{N-1}X_0^T X_0$, $X_0$ being the zero-centred version of the original matrix $X$) has a higher condition number than the corresponding problem presented by the original data matrix $X$. In short, the condition number of a matrix quantifies the sensitivity of the solution of a system of linear equations defined by that matrix to errors in the original data. The condition number strongly suggests (but does not fully determine) the quality of the system of linear equations' solution.

In particular as the covariance matrix $C$ is calculated by the cross-product of $X_0$ with itself, the ratio of the largest singular value of $X_0$ to the smallest singular value of $X_0$ is squared. That ratio is the condition number; values that are close to unity or generally below a few hundreds suggest a rather stable system. This is easy to see as follows:

Assume that $X_0 = USV^T$ where $U$ are the right singular vectors, $V$ are the left singular vectors and $S$ is the diagonal matrix holding the singular values of $X_0$, as $C = \frac{1}{N-1}X_0^TX_0$ then we can write: $C = \frac{1}{N-1} VS^TU^T USV^T = \frac{1}{N-1} V S^T S V^T = \frac{1}{N-1} V \Sigma V^T$. (Remember that the matrix $U$ is orthonormal so $U^TU = I$). ie. the singular values of $X_0^TX_0$ represented in $\Sigma$ are the square of the singular values of $X_0$ represented in $S$.

As you see while seemingly innocuous the cross-product $X_0^TX_0$ squares the condition number of the system you try to solve and thus makes the resulting system of equations (more) prone to numerical instability issues.

Some additional clarification particular to the paper linked: the estimate of the covariance matrix $C$ is immediately rank-degenerate in cases where $N < p $ which are the main focus of that paper; that's why the authors initially draw attention of the Marcenko–Pastur law about the distribution of singular values) and regularisation and banding techniques. Without such notions, working with $C$ or the inverse of $C$ (in the form of Cholesky factor of the inverse of $C$ as the authors do) is numerically unstable. The rationale as to why these covariance matrices are degenerate is exactly the same as above in the case of very large matrices: the condition number is squared. This is even more prominent in the $N < p$ case: an $N\times p$ matrix $X$ has at most $N$ non-zero singular values, the crossproduct of it with itself can also have at most $N$ non-zero singular values leading to rank-degeneracy (and therefore a "infinite" condition number). The paper presents a way to band the estimated covariance matrix given some particular conditions (the estimated $C$ has a Toepliz structure, the oracle $k$ representing the banding parameter can properly estimated, etc.) such as it is numerically stable.

$\endgroup$
5
  • $\begingroup$ I don't think this answers op's question. They asked why estimating the covariance is unstable. You refer to solving a linear equation with the covariance. $\endgroup$
    – Yair Daon
    Commented Nov 13, 2016 at 21:57
  • 1
    $\begingroup$ @YairDaon: I thought the same initially but then I looked more carefully at the body of the question where it specifically asks about the use of the covariance (which relates directly to condition numbers and numerical instability). I was actually thinking of commenting that the body and the title of the question appear slightly incompatible. Feel free to add your answer though! $\endgroup$
    – usεr11852
    Commented Nov 13, 2016 at 22:06
  • $\begingroup$ @IHaveNoIdeaHowToWriteYourUsername Maybe my understanding is wrong, but OP say it is not difficult to understand for matrix inversions. I might be missing something... As far as I know, just estimating the covariance is pretty stable (at least if you exclude fat tailed distributions). $\endgroup$
    – Yair Daon
    Commented Nov 14, 2016 at 1:29
  • $\begingroup$ @YairDaon this answer is certainly very helpful to understanding why the SVD is preferred in the PCA (thanks user11852). But the general question (I should have been more clear) was also why the sample covariance estimation can be unstable (in high dimensions), as described in this paper: Annals of Statistics paper (Regularized estimation of large covariance matrices) stat.berkeley.edu/~bickel/BL2008-banding.pdf $\endgroup$
    – luffe
    Commented Nov 14, 2016 at 8:19
  • 1
    $\begingroup$ Cool, thank you for this additional information; it clarifies the issue raised by Yair. I will update my answer accordingly later tonight; just got home. The gist/general principles will be the same just the focus will be slightly shifted. (For what's worth looking at the paper briefly I still think the question's title is still a bit misleading! :) ) $\endgroup$
    – usεr11852
    Commented Nov 14, 2016 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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