3 ms·

For those curious about applications: Suppose you have a learning algorithm that requires the eigenvectors/eigenvalues for a large matrix. Suppose new data is

For those curious about applications: Suppose you have a learning algorithm that requires the eigenvectors/eigenvalues for a large matrix. Suppose new data is streamed in that increase the size of the matrix. well, now you have an algorithm for updating your existing solution instead of needing to compute the entire thing from scratch. (consider updating principal components over time for example). Suppose you want to accelerate the process of computing eigenvectors for a large matrix. Well, you can now do parallel reduction relatively trivially given the theorem. *edit: wording.

deleted 7y ago
[deleted]
auggierose 7y ago
If the matrix is symmetric (or hermitian in the complex case).
yxhuvud 7y ago
Won't you need a way to figure out the sign of the vector, though? Am I wrong in that this method only output the norms?
- banachtarski 7y ago
  Yes but whether such conditioning is important will depend on your domain. In many cases, just knowing the axis and two sample points is enough to fully determine the orientation.
mxcrossb 7y ago
Can you go into more detail? I don’t see how that would work. In this algorithm, you need the eigenvalues of all of the minors. So if I’m adding rows/columns to the matrix, yes I have one of the minors from my last solution, but I have to compute N more. And I also need the eigenvalues of the new full matrix. I think this result has some intriguing opportunities, and have been toying with them since yesterday’s post, but I don’t see something so straightforward.
- banachtarski 7y ago
  I obviously haven't worked it out myself, but I think you can memoize the results from the smaller minors to accelerate the computation of the big one. So you would need to decide for yourself the speed/memory tradeoff.
- liuliu 7y ago
  I think what the parent comment meant is it can be recursive. If you update one row, a lot of these recursively small minors of minors won't change, and you probably can do the computation quicker. I haven't fully worked out the math yet as well.
suslik 7y ago
But you would still need to know the eigenvalue λi(A) of the full matrix, no? How would you do it in this streaming setting?
ArtWomb 7y ago
Not to downplay the pure and applied mathematics implications. But the immediate discovery was made in the context of calculating neutrino oscillation probabilities. Yielding insight into matter / anti-matter imbalance in the known universe ;) Eigenvalues: the Rosetta Stone for Neutrino Oscillations in Matter https://arxiv.org/abs/1907.02534 https://arxiv.org/abs/1907.02534 Deep Underground Neutrino Experiment https://en.wikipedia.org/wiki/Deep_Underground_Neutrino_Experiment https://en.wikipedia.org/wiki/Deep_Underground_Neutrino_Expe...
- MarkMMullin 7y ago
  Don't get me wrong, I like your cites - but at the end of the day, math is math. Either it works or it doesn't. If it works, apply it where you can! I've got a sneaking suspicion a PCA based analyzer for lidar generated point clouds is going to be a lot faster.......

deleted 7y ago

[deleted]

auggierose 7y ago

If the matrix is symmetric (or hermitian in the complex case).

yxhuvud 7y ago

Won't you need a way to figure out the sign of the vector, though? Am I wrong in that this method only output the norms?

banachtarski 7y ago
Yes but whether such conditioning is important will depend on your domain. In many cases, just knowing the axis and two sample points is enough to fully determine the orientation.

mxcrossb 7y ago

Can you go into more detail? I don’t see how that would work. In this algorithm, you need the eigenvalues of all of the minors. So if I’m adding rows/columns to the matrix, yes I have one of the minors from my last solution, but I have to compute N more. And I also need the eigenvalues of the new full matrix. I think this result has some intriguing opportunities, and have been toying with them since yesterday’s post, but I don’t see something so straightforward.

banachtarski 7y ago
I obviously haven't worked it out myself, but I think you can memoize the results from the smaller minors to accelerate the computation of the big one. So you would need to decide for yourself the speed/memory tradeoff.
liuliu 7y ago
I think what the parent comment meant is it can be recursive. If you update one row, a lot of these recursively small minors of minors won't change, and you probably can do the computation quicker. I haven't fully worked out the math yet as well.

suslik 7y ago

But you would still need to know the eigenvalue λi(A) of the full matrix, no? How would you do it in this streaming setting?

ArtWomb 7y ago

Not to downplay the pure and applied mathematics implications. But the immediate discovery was made in the context of calculating neutrino oscillation probabilities. Yielding insight into matter / anti-matter imbalance in the known universe ;) Eigenvalues: the Rosetta Stone for Neutrino Oscillations in Matter https://arxiv.org/abs/1907.02534 https://arxiv.org/abs/1907.02534 Deep Underground Neutrino Experiment https://en.wikipedia.org/wiki/Deep_Underground_Neutrino_Experiment https://en.wikipedia.org/wiki/Deep_Underground_Neutrino_Expe...

MarkMMullin 7y ago
Don't get me wrong, I like your cites - but at the end of the day, math is math. Either it works or it doesn't. If it works, apply it where you can! I've got a sneaking suspicion a PCA based analyzer for lidar generated point clouds is going to be a lot faster.......