I need a good reference on approximate operator decomposition, in particular spectral decomposition.
Are there effective algorithms that compute approximate spectrum, eigenvectors, projections and eigenspaces with computable bounds on number of iterations / residual?
It is known that degenerate matrices lead to troubles. But what if we approximate the spectrum with numbers that are all mutually distinct?
>>8010866
why do you need a reference?
you should be able to define your own objective function, your own constraints and derive an algorithm (or ask for help to find one) to match your project.
This is how we engineers do, as opposed to mathematicians who only rely on others.
>>8010884
Accepting your premises,
why do you ask why he needs a reference, if from what you say you'd infer he's a mathematician?
>>8010884
You engineers don't even know what an EFFECTIVE algorithm means. I'm not interested in stone hammer methods and complexity. I'm interested in computability. But that's beyond your understanding.
>>8010891
no. What's beyond my understanding is why you expect to find a reference for an ill defined problem.
>>8010893
>an ill defined problem.
Elaborate your statement
>>8010896
OP asks for "approximating the spectum of degenerate matrices with numbers that are all mutually distinct".
Knowing that if a matrix has an eigenvalue x twice, you could just replace that with x and x+epsilon, or x-epsilon and x+epsilon or whatever.
But how do you choose epsilon? That's what OP needs to worry about. He has to define his objective function in order to find a relevant process.
Does he want to minimize error on the unit sphere using norm 2? Does he want something else?
That's how you'll find epsilon (in my example).
>>8010904
Well, it's straightforward to figure out the metric. You might take the maximum absolute residual of eigenvalues, for instance. Regarding eigenvectors, you may take [math]|| A v_i - \alpha_i v_i || \leq \varepsilon[/math] etc. It's not hard to figure out. In a reference, they might define the metrics differently. It doesn't matter. What matters is an effective algorithm that finds the said objects up to predictable error.
There is a least an approximation in the following sense:
[math] \big|\big| A - \displaystyle \sum_{i=1}^{n} \alpha_i P_i \big|\big| \leq \varepsilon [/math]
where orthogonal projections [math] P_i [/math] and some real numbers [math] \alpha_i [/math]
>>8010866
>Spectral decomposition
reminder that there is a constructive one
Constructive Results on Operator Algebras
Journal of Universal computation volume 11, issue 12 2005.
ps.gz pdf bib tm html
AbstractWe present a to following results in the constructive theory of operator algebras. A representation theorem for finite dimensional von Neumann-algebras. A representation theorem for normal functionals. The spectral measure is independent of the choice of the basis of the underlying Hilbert space. Finally, the double commutant theorem for finite von Neumann algebras and for Abelian von Neumann algebras.
http://www.cs.ru.nl/~spitters/articles_abs.html
>>8011125
Ema-Stone-fag?
Thanks for the paper, reading it now. Will get back soon.
Bump just in case
>>8011125
Were you actually thinking of Theorem 3? Because otherwise, I can't see a result close to the apprxoimate SVD as I mentioned. But Theorem 3 does not provide the isomorphism explicitley. Or you meant density? But that's precisely >>8011019.
I was actually interested in its relation to eigenvectors, eigenspaces etc. I. e. I'd like to have the spectral theorem in exactly the same format as it appears classically, but approximately. This is possible constructively.
Why are you doing this?
I don't believe this hasn't been done somewhere. Is it literally so that any algorithm is ineffective and prone to issues computing spectral decompositions?
This is not next level necroing.
>>8017689
What's your problem? Hide.
>>8010866
Google "Fredholm spectrum"; does that have anything you want?
In finite dim, check the book " trefethen bau" for alg's, but power method should suffice. Good luck with algs in infdim, but just try some power method variant...
>>8017752
Numerical algorithms != effective algorithms
Computability is something completely different
Here is a good reference: cca-net.de/vasco/publications/spectral.ps
>>8017963
I am not him, but can you state your problem in details?
The constructive version is just pure mathematics, not CS related explicitly.
You can find three version of constructive spectral theorem in
Constructive and intuitionistic integration theory and functional analysis.
Ph. D. thesis, University of Nijmegen, 2002
in the above link, bottom of the page
You have various versions depending on your hypothesis about your matrices.
Ye has a famous version exposed in the thesis and there are other sin the thesis too. All of this relies on the literature as you can see.
>>8018026
I know this theorem, it's nice, but I am looking for a theorem for operators on finite-dimensional spaces with (classically) discrete spectrum.
Actually, it should be an approximate version of the Ye's theorem, that I marked with (I) on the picture. Approximate version was given by Bishop (II), but he didn't say anything about (approximate) eigenvectors and eigenspaces.
Eventually, I wanna have approximate and effectively computable matrix decompositions, such as SVD or spectral decomposition.
>>8018089
This was my post. There, the theorem is EXACT provided that the number of mutually distinct eigenvalues is KNOWN before computing the decomposition.
That's not what I am asking.
>>8018102
okay, so you know nothing about the eigenvalues nor the eigenvectors beforehand?
>>8018102
all I have to offer is the effective method of the dunford decomposition;
http://arxiv.org/abs/1307.4410
These notes are not intended to substitute for a course in linear algebra on reduction of endomorphisms nor an exhaustive presentation of the Dunford's decomposition. We will limit ourselves to the case where the base is R or C, and the purpose of this presentation is to make an inventory of the various Dunford's decomposition methods. When the eigenvalues are known with their exact values, decomposition into simple elements of the inverse of a polynomial annihilator provides us the spectral projectors and a fortiori the expected decomposition.
The most difficult case occurs when the spectrum of the endomorphism is not at our disposal, which is a common situation when the dimension of the vector space is greater than 4. The Newton-Raphson method then comes to the rescue to provide a sequence which converges quadratically to diagonalizable component. While this method is very popular quite effective regardless of the size matrix studied, but it leaves us hungry. Indeed, we know that Dunford components are polynomials in the matrix and would know these generator polynomials. The good news is that effective method using the Chinese lemma there and it was introduced by Chevalley in the fifty years of the century last. I will focus on this method which was mentioned in an article of Danielle Couty, Jean Esterle and Rachid Zarouf, detailing evidence of the algorithm where the characteristic polynomial is divided on the body base, then I will detail the actual case is a more subtle situation requiring further study. A reminder of the semi-simple endomorphisms was introduced to justify the importance of finding an effective method for testing diagonalisability in Mn (R) when no eigenvalues of the endomorphism studied. To achieve this I have proposed as the Sturm verification tool diagonalisabilit\'e in R.
lel Ye trolls at the end. I really cannot believe that nobody cares enough to compute the vectors and the values constructively.
Perhaps, write an email to Bas spitters or Ye directly, asking them if they have seen somewhere in the literature the computation that you desire.
this is the only explicit computation form the thesis here>>8018026
so you are right, we fall back on >>8011019
>>8018165
Δεν μιλάω γαλλιkά!
>>8018105
Say, you're just given a matrix and that's it. Sure, its entries are computable complex numbers. Needed is an approximate spectral- or eigendecomposition or SVD.
>>8018225
I had a whole discussion with physicists on this concern and it's not as much trolling as you think. This paragraph is somewhat justified for real-world applications. Degeneracy is not as much a natural phenomenon. Lüder's rule is one way of addressing it. Ye didn't just make up the words "artificial constructions". It's up to us to define measurement operators. Read also Lamb shift. But it's not the matter of this discussion.
Btw, Ye has another justification in approximate format in his draft. It was removed in the book.
Regarding eigenvalues and eigenvectors, I believe Bishop's [math]c_i[/math]'s >>8018082 should be close to the (computable) solutions of [math] \det ( T - \lambda I ) [/math]. Bishop also mentioned [math]\varepsilon-[/math]eigenvectors, but only briefly. Since an eigenvector is precisely the solution to a system of linear equations, effective approximation should be possible.
After all, I rather need approximate matrix decompositions. That's what I do frequently in my work. I am on the right track of converting my stuff into constructive/computable form.
----
I don't think I have enough reason to bother Spitters or Ye with this question. Maybe, if it really doesn't go any further, I'll do it.
>>8018248
Where is this from?
>>8018625
Ok, that's from the thesis I see. Will take a look at it.
Meanwhile, just a remark, Dedekind reals suck.
>>8018638
Ooops, I confused it with the paper above. There they used Dedekind reals. Nevermind.
>>8018165
冗談ですか?
>>8018638
>Dedekind reals suck.
why?
they are used in constructive topology for instance.
Use Gaussian
>>8019550
> Exact real arithmetic
> Effective algorithm
Sure
>>8019511
Because you can't do effective computations with Dedekind reals. They don't admit a consistent decision procedures.
If you can't do effective computations, it's arguable if your setup is really constructive or you just use it as a buzzword.
>>8019951
>>Because you can't do effective computations with Dedekind reals.
yes I forgot about Bauer's article in ASD.
>Abstract: Cauchy’s construction of reals as sequences of rational approximations is the theoretical basis for a number of implementations of exact real numbers, while Dedekind’s construction of reals as cuts has inspired fewer useful computational ideas. Nevertheless, we can see the computational content of Dedekind reals by constructing them within Abstract Stone Duality (ASD), a computationally meaningful calculus for topology. This provides the theoretical background for a novel way of computing with real numbers in the style of logic programming. Real numbers are defined in terms of (lower and upper) Dedekind cuts, while programs are expressed as statements about real numbers in the language of ASD. By adapting Newton’s method to interval arithmetic we can make the computations as efficient as those based on Cauchy reals.
http://math.andrej.com/2008/08/24/efficient-computation-with-dedekind-reals/
>>8019967
I read it. It turns out that Bauer and Taylor are the only people who took a bit care of this matter.
But, at the end of this article you'll see that such computations are non-predictable. Refinement might not behave well. If you take Cauchy, there is always an effective algorithm.
>>8018248
But isn't this not enough? Can we simply take some basis vectors from those spaces [math]\text{Range}_{\chi_{B_i}}(A)[/math]?
Can we derive an approximate SVD from this?
>>8018248
But isn't this not enough? Can we simply take some basis vectors from those spaces [math] \text{Range}_{\chi_{B_i}}(A) [/math] ?
Can we derive an approximate SVD from this?
>>8021872
I think that if the existence is assured in constructive setting, then you can derive what OP wants, but apparently nobody has done it so far for the values and vectors, which is odd, especially from Bishop, since my bet is that somebody else has had the same problem. So either OP must ask around to people who write about this stuff, or Op must do it himself.
At least it would make a very nice publication by OP.
Bishop is too lazy to do it
>>8021958
this is proposition 4
this is how he uses prop 4 in a proof
anyway there seem to be people to work on this and the problem is famous. and so far there is no good methods according to them
http://math.unice.fr/~frapetti/CorsoF/cours4part1.pdf
I saw your thread on some stack site Op, and even there nobody could help you.
>>8021958
>Bishop is too lazy to do it
Well, maybe cos he's is dead.
So, I stumbled upon the question of whether to work out constructive matrix canonical forms, or to inquire Bridges or Ye, or someone else.
>>8021959
By the way, can do you also think that it's hard sometimes to recognize whether countable or dependent choice is used in the proofs? Like in this example, say.
>>8021985
>and even there nobody could help you
I also wrote on a local forum. Will post the idea here today evening or tomorrow morning.
>>8021985
Meanwhile, look at this:
https://www.cse.buffalo.edu/tech-reports/94-16.ps
So here is the idea. Let [math]A[/math] be an [math]n \times n[/math] Hermitian matrix (I won't consider operators since I don't know measure theory and operator theory well).
Its eigenvalues [math]\lambda_1, \ldots ,\lambda_n[/math] are all computable since FTA admits a constructive proof. However, we can't decide [math]\lambda_i = \lambda_j \low \lambda_i \neq \lambda_j, i \neq j[/math] for it entails Halting problem. What we can is, to compare each [math]\lambda_i[/math] to a non-trivial interval.
Minimum and maximum of the set [math] \{ \lambda_1, \ldots ,\lambda_n \} [/math] are definable (even though we can't find exactly which [math]\lambda_i[/math] is minimal/maximal). So we may find an interval that contains all eigenvalues and split it into subintervals of required length, and decide which intervals contain which eigenvalues.
Take an interval, say, [math]I[/math] that contains some [math]d \leq n[/math] eigenvalues. Take the projector defined by the circle integral [math]P_i:=\frac{1}{2\pi i}\oint\limits_{\mathcal{C}(c_i, \varepsilon)} (A-z I)^{-1}\,dz [/math] where [math]\mathcal{C}(c_i, \varepsilon)[/math] is a circle of radius [math] \varepsilon [/math] centered at [math]c_i[/math]. This gives an orthogonal projection onto a [math]d-[/math]dimensional subspace [math]S_i[/math] such that [math]\forall v \in S. \|Av-c_i v\| \le \frac{\varepsilon}{2}\|v\| [/math]. And this is precisely the definition of an [math]\varepsilon-[/math]eigenvector used by Bishop. So we can compute an orthonormal basis for [math]S_i[/math]. In total, if we adjust [math] \varepsilon [/math] a bit, we can acquire the approximation >>8011019.
This should answer the question of full statement of spectral theorem in approximate format. I wonder why no one could comment on it on SE.
Next step. SVD. In SVD, we must have [math] \| A - \hat{U} \hat{\Sigma} \hat{V}^* \| \leq \varepsilon [/math] for [math] \hat{U} [/math] and [math] \hat{V}^* [/math] unitary (rotation) ...
>>8022453
[math] \lambda_i = \lambda_j \lor \lambda_i \neq \lambda_j, i \neq j [/math]
Also comment on approximate spectral theorem: what if effectively do is, we "glue" some eigenvalues together if they fall under the give precision. So we have less details (read: terms) in the final decomposition than the classical one.
(addendum on ST)
It is easy to see that we can find exactly [math] n [/math] linearly independent [math] \varepsilon-[/math]eigenvectors for the matrix. This reflects the fact that the geometric multiplicity coincides with the algebraic multiplicity for Hermitian matrices.
(cont. on SVD)
So [math] \hat{U} [/math] and [math] \hat{V}^* [/math] are unitary rotation matrices formed by the eigenvectors of [math] A A^* [/math] and [math] A^* A [/math] respectively.
What we do here is we take the diagonal matrix of singular values [math] \Sigma [/math] as approximate eigenvalues of [math] A A^* [/math] just as we did before. So, some entries may be repeated. Corresponding to those, we have [math] n [/math] [math] \varepsilon-[/math]eigenvectors of [math] A A^* [/math]. We do the same for [math] A A^* [/math] and obtain its [math] n [/math] [math] \varepsilon-[/math]eigenvectors. It seems we may form [math] \hat{U} [/math] and [math] \hat{V}^* [/math] from those.
Here is where I start needing help ...
>>8022548
squares of those eigenvalues of course
http://philosophy.stackexchange.com/questions/33787/what-are-computable-numbers-and-what-is-their-philosophical-significance
All mathematical formalizations of (intuitive) computability are known to be equivalent, in particular they are equivalent to computability on the universal Turing machine. So technological implementation is irrelevant. The Church–Turing thesis states that this coincides in scope with what is "computable by a human being" unconstrained by limitations of time and resources. This is obviously a philosophical statement, and some disagree, albeit a small minority, but notably Gödel and Lucas. According to them human mind exhibits an ability to creatively "transgress" algorithmic computation, see Can a Turing machine generate an inconsistent formal system?
Computable numbers are the real numbers for which there is an algorithm that given desired precision returns approximation of the number to that precision in guaranteed finite time. Those are the real numbers that constructivists and finitists would be allowing in their version of real analysis. Extensions of this to epistemology more broadly are discussed under Do limitations on computability and computational resources have any consequences for epistemology? See also What are the "undefinable numbers" in real analysis and philosophy? for a related class of real numbers.
Let us write a short paper together and post it on arxiv anonymously? That'd be win. Especially if the result will be useful. And it will.
