j********3
发帖数: 9 | 1 Couple beginner questions:
(1) What is the run time for computing the principal components of data? Is
there faster than O(n^3) algorithms?
(2) What if I only need one of the principal components (say, the largest)?
I remember seeing somewhere that SVD takes O(n^3). If you happen to know
some references, that would be great.
I appreciate your help. Thank you very much. | e***e
发帖数: 3872 | 2 "Using the Nystrom Method to Speed Up Kernel Machines" Williams and Seeger
Is
【在 j********3 的大作中提到】
: Couple beginner questions:
: (1) What is the run time for computing the principal components of data? Is
: there faster than O(n^3) algorithms?
: (2) What if I only need one of the principal components (say, the largest)?
: I remember seeing somewhere that SVD takes O(n^3). If you happen to know
: some references, that would be great.
: I appreciate your help. Thank you very much.
| j********3
发帖数: 9 | 3 etude: Thank you very much for the link. I will have to study it for a
while since I'm not familiar with the area. In the paper, they mentioned:
"There are methods to compute the first p eigenvalues and eigenvectors of K,
but their average running times are significantly below O(n^3) only if p<
But they didn't give any references to these methods... I'm interested in p=
1, do you (or anyone) know what these "methods" are? |
|
