15
$\begingroup$

Let us have a symmetric matrix $C \in \mathbb{R}^{n\times n}$ having non-negative values. Suppose that we have the eigenvalue decomposition for this particular matrix such that

$$C e_i = \lambda_i e_i$$

where $e_i$ are the eigenvectors and $\lambda_i \geq 0$ are the corresponding eigenvalues. In matrix form,

$$CE = ES$$ where $E$ is the matrix involving eigenvectors as columns and $S$ is the diagonal matrix involving eigenvalues on the diagonal entries.

Now, we delete $k^\text{th}$ row and column of the matrix and form a new matrix $\tilde{C} \in \mathbb{R}^{(n-1) \times (n-1)}$ and we want to find its eigenvalues and eigenvectors such that

$$\tilde{C} \tilde{E} = \tilde{E} \tilde{S}$$

Instead of computing them from scratch, I wonder if there exists an analytical way to find the eigenvectors and eigenvalues iteratively using $E$ and $S$. In other words, is there a link between $E$, $S$ and $\tilde{E}$, $\tilde{S}$?

For example, for a 3-by-3 matrix $C$ where

$$C = \left[\begin{array}{ccc}a & b & c \\\\ b & d & e \\\\ c & e & f\end{array}\right]$$

if I delete the third row and column, then I get

$$C = \left[\begin{array}{cc}a & b \\\\ b & d \end{array}\right]$$

I know that the number of dimensions of the eigenvectors are one less and we have one less eigenvalues but may there be a projection of the others onto some bases?

P.S.(1) I've read the answers to the question "How does eigenvalues and eigenvectors change if the original matrix changes slightly", but I couldn't find a connection with this question. Sorry if I couldn't get a point and created a duplicate question.

P.S.(2) If you wonder why I'm asking this question, here it is: I'm computing the eigenvalues and eigenvectors of the covariance matrix of some samples. Let each sample have 3 dimensions and let $D \in \mathbb{R}^{k\times n}$ be the data matrix where each row is a sample and we have $k$ samples. Then the covariance matrix is $C = D^T D$. If we have 3 dimensions and the columns of $D$ are $d_1$, $d_2$ and $d_3$, then we have

$$ C = \left[\begin{array}{ccc}d_1^T d_1 & d_1^T d_2 & d_1^T d_3 \\\\ d_2^T d_1 & d_2^T d_2 & d_2^T d_3 \\\\ d_3^T d_1 & d_3^T d_2 & d_3^T d_3\end{array}\right]$$

I'm interested in the decomposition when we have some dimensions missing in the data. If, as in the example, the third dimension is missing, then we have

$$ \tilde{C} = \left[\begin{array}{cc}d_1^T d_1 & d_1^T d_2 \\\\ d_2^T d_1 & d_2^T d_2 \end{array}\right]$$

I wondered whether there's a way to compute the eigenvectors and eigenvalues of the missing data's covariance matrix using the ones that we computed from the full data in an iterative manner instead of computing it from scratch.

Kind regards and thanks for any ideas.

$\endgroup$

4 Answers 4

20
$\begingroup$

Let $A$ be a symmetric matrix, with eigenvalues $\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$. Let $B$ be the matrix obtained by deleting the $k$-th row and column from $A$, with eigenvalues $\mu_1 \leq \mu_2 \leq \cdots \leq \mu_{n-1}$. Then $$\lambda_1 \leq \mu_1 \leq \lambda_2 \leq \mu_2 \leq \lambda_3 \leq \cdots \leq \lambda_{n-1} \leq \mu_{n-1} \leq \lambda_{n}.$$ This is a special case of Cauchy's interlacing theorem. The operator $P$ in the wikipedia article should be taken to be the projection on the coordinate vectors other than the $k$-th one.

$\endgroup$
6
$\begingroup$

The word you're looking for is downdating, and I cannot do better than to point out these two survey papers, and this article. I will also have to make the reminder that it makes better numerical sense to compute the singular values of $\mathbf{D}$ rather than the eigenvalues of $\mathbf{D}^T \mathbf{D}$.

$\endgroup$
1
$\begingroup$

Removing a paired row/column from a symmetric matrix is kind of like setting the corresponding entries to zero. This reformulation would allow you to consider a perturbed matrix of the same dimensions.

$\endgroup$
0
$\begingroup$

For people who search an algorithm to find the updated eigenvalues, a new article gives a result for the case of a symmetric matrix like the one in the question : https://www.sciencedirect.com/science/article/pii/S2215016118300062

H. Oh, Z. Hu, Multiple-rank modification of symmetric eigenvalue problem, MethodsX 5, 103 (2018). DOI: 10.1016/j.mex.2018.01.001.

$\endgroup$

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.