11
$\begingroup$

I am interested in effective and computations for finding approximate spectral decompositions in some suitable format.

Namely, let $A: H \rightarrow H$ be a Hermitian operator on an $n-$dimensional Hilbert space $H$ with the spectrum $\{\lambda_1, \ldots \lambda_m\}, m \leq n$. Then, $A$ can be decomposed as:

$$ A = \sum_{i=1}^{m}\lambda_i P_i,$$

where $P_i, i=1,\ldots m$ are orthogonal projections with $P_i, P_j = 0, i \neq j$ onto the eigenspaces $H_i = \ker \{ \lambda_i I - A \}$ such that:

$$ H= \displaystyle \underset{i=1}{\overset{m}{\oplus}} H_i.$$

In an approximate format, the theorem can be stated as follows (p. 380):

for any $\varepsilon > 0$, there exist projections $P_i, i=1, \ldots n$ with $P_i, P_j = 0, i \neq j$, and real numbers $\alpha_1, \ldots \alpha_n$ such that $\big|\big| A - \displaystyle \sum_{i=1}^{n} \alpha_i P_i \big|\big| \leq \varepsilon$.

What about the approximate eigenspaces?

A particular example is this article, but it addresses exact spectral decomposition at the cost of additional input (cardinality of spectrum).

$\endgroup$
4
  • 4
    $\begingroup$ Please, post only one question in one post. Posting several questions in the same post is discouraged and such questions may be put on hold, see meta. $\endgroup$ – Shahab Apr 20 '16 at 12:43
  • 1
    $\begingroup$ The trace of an orthogonal projection is the dimension of the range. So the trace of the integral projection is the total of the dimensions of the eigenspaces associated with the eigenvalues inside the contour. $\endgroup$ – Disintegrating By Parts May 8 '16 at 18:00
  • 1
    $\begingroup$ @ValerySaharov : An orthogonal projection is unitarily equivalent to a diagonal matrix with 1's and 0's on the diagonal; so the trace is the dimension of the range. The orthogonal projection you get out of the integral is the sum of the mutually disjoint orthogonal projections onto the eigenvalues inside the contour. $\endgroup$ – Disintegrating By Parts May 8 '16 at 19:34
  • 1
    $\begingroup$ @ValerySaharov : When you have 1's and 0's down the diagonal and 0's elsewhere, you know that the dimension of the range is the number of 1's on the diagonal, which is the trace. $\endgroup$ – Disintegrating By Parts May 9 '16 at 0:04
2
+50
$\begingroup$

This is not an answer, and don't take it as such. From a theoretical point of view, you have $A=\sum_{k=1}^{n}\lambda_k P_k$ where the $P_k$ are orthogonal projections. If you start iterating in $A$, or perform various functions of $A$, the problem is that $f(A)=\sum_{k=1}^{n}f(\lambda_k)P_k$. You can get down below the level of a projection. You can form functions of $A$ in such that way that $f_k(A)=P_k$, but that's the smallest granularity. Anything else starts with a vector and, even then, the best you can do is $P_kv$ for some vector $v$.

If you know where an eigenvalue is located, then you can use Complex Analysis to assert that $$ P_{k} = \frac{1}{2\pi i}\oint_{|\lambda-\lambda_k|=\delta}(\lambda I-A)^{-1}d\lambda. $$ where the circular contour is positively oriented, centered at $\lambda_k$ and of radius $\delta > 0$ chosen small enough that there are no other eigenvalues on or inside the circle of radius $\delta$ centered at $\lambda_k$. What's nice about such a representation is this: if you perturb $A$ so that the eigenvalues don't change by much, even if there are bifurcations in the eigenvalues, so long as the eigenvalues do not cross the boundary of your circle of integration, then $P_k$ remains a projection--it is the projection onto the direct sum of the eigenspaces associated with all eigenvalues in the circle. This tells you something about what happens under perturbations. What's nice about this is that you don't really care whether the eigenvalues are very close or whether they're exactly on top of each other--this integral will give you the sum of all the projections associated with eigenvalues in the circle. And the sum of all such projections is an orthogonal projection. I suspect from your point of view of computability, this may be interesting, but I don't know.

If you know the positions of eigenvalues to a certain accuracy, then you could theoretically perform several such integrations in order to obtain $\lambda_1,\cdots,\lambda_k$ and contour-integration-derived projections $P_l$ such that $\|\sum_{l=1} \lambda_l P_l-A\| < \epsilon$. The projection $P_l$ would be the sum of all the orthogonal projections for eigenvalues within a certain tolerance of $\lambda_l$. This approximation would in the operator norm, with the exact difference being $$ \sum_{l}\sum_{\{m : |\lambda_m-\lambda_l| < \epsilon\}}\lambda_m Q_m -\sum_{l}\sum_{\{ m : |\lambda_m-\lambda_l| < \epsilon\} }\lambda_l Q_m \\ = \sum_{l}\sum_{\{m : |\lambda_m-\lambda_l|\}}(\lambda_m-\lambda_l)Q_m $$ The projection $P_l$ is then given by $$ P_l = \sum_{\{ m : |\lambda_m-\lambda_l| \}}Q_m. $$ These are orthogonal projections, and $P_l P_l' = 0$ if $l\ne l'$.

$\endgroup$
6
  • $\begingroup$ @ValerySaharov : You can see the projectors are what you want by considering $(\lambda I-A)^{-1}=\sum_{n} \frac{1}{\lambda-\lambda_k}P_k$, and applying standard Complex Analysis: If you integrate around a simple closed positively-oriented contour that does not pass through any eigenvalue, then the resulting integral gives you the sum of the $P_k$ for those $\lambda_k$ inside the contour. This sum of orthogonal projections is an orthogonal projection, and you want an orthonormal basis of the range of this projection. $\endgroup$ – Disintegrating By Parts Apr 30 '16 at 9:44
  • $\begingroup$ @ValerySaharov : But the projection as a matrix is the integral I gave you. We use different language concerning computable. Also, please note the first sentence of my post. I'm not trying to convince you I have a solution in your language. I'm trying to explain the more abstract point of view, and show you how the approximation you stated can be derived. $\endgroup$ – Disintegrating By Parts Apr 30 '16 at 14:35
  • 2
    $\begingroup$ @ValerySaharov : You can directly demonstrate that the integral around any simple closed path not passing through eigenvalues is an orthogonal projection if $A$ is selfadjoint. And you can show that if the path encloses only one eigenvalue, then the projection is the projection onto the eigenspace associated with that eigenvalue. Once you obtain that matrix, the column space is the eigenspace. $\endgroup$ – Disintegrating By Parts Apr 30 '16 at 15:14
  • 2
    $\begingroup$ @ValerySaharov : Computationally, distinct and degenerate don't matter when you cannot distinguish. All of the columns are computationally eigenvectors with the same fuzzy eigenvalue. $\endgroup$ – Disintegrating By Parts Apr 30 '16 at 15:31
  • 2
    $\begingroup$ @ValerySaharov : $P$ has two eigenvalues : 0 and 1. $P=P^2=P^*$. $\endgroup$ – Disintegrating By Parts Apr 30 '16 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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