Concept · Feb 2024
SVD intuition
This is in essence what SVD is, inspecting the last equation closely, one sees that what happens is that x is projected onto each one of the eigenvectors of , and then the resulting projection is used to scaled the vector that the eigenvector is mapped to by A.
The Power Method
hence, by applying to one gets . From this follows the theorem leading to the power method:
“Let x be a random unit vector and define then with high probability, is in the span of the first singular vector . If we normalize to a unit vector at each s then furthermore the limit is .”
- The proof is immediate from the fact that and so by applying B infinity times and normalizing we get that the ratio of the coefficients of the result is
- In this way we can find v1 by applying B to a random unit vector as long as the ration between is very small (i.e it is no longer being rotated since it is almost entirely in the span of v1).
- Afterwards, to complete the SVD algorithm all one needs to do is define (i.e subtracting the rank-1 component of A corresponding to v1) and applying the same procedure.
- Note that for the convergence of SVD using the power method, one assumes that the ratio of consecutive eigenvalues is not too close to 1, if that is the case the convergence may take a long time, as a result the power method is not the industry method to compute SVD, but rather a technique using something called housefelder reflections