Projected Gradient Descent for Max and Min Eigenpairs - Proof of Convergence
Let A be a positive semi-definite matrix. Let be the eigenvalues in decreasing order and be the corresponding orthonormal eigenvectors. We have
You need to find the Condition number of , which is defined as . You could compute all the eigenvalues and then compute the condition number. But this is superfluous as you just need to compute and .
Almost two years ago, I wrote a blog post on using Projected Gradient Descent for finding the maximum and minimum eigenvectors and the corresponding eigenvalues. However, I did not offer any proof for the correctness of the algorithm. I do that in this blog post.
Consider the following algorithm:
This corresponds to doing projected gradient descent on the objective subject to .
Similarity to Power Iteration
Power Iteration is possibly the most widely used algorithm for computing the max eigenvector. Its update is:
The PGD update could be written as:
The PGD update is actually just power iteration on . So we could try analyzing it like power iteration.
First note that and have the same eigenvectors when . The eigenvectors of are and the corresponding eigenvalues are . So we know:
- and have the same eigenvectors
- PGD on is just power iteration on
- Power iteration converges to the maximum eigenvector
Hence, PGD will converge to the maximum eigenvector of A.
For a more rigorous proof, consider the following analysis:
If for , then . We have:
When , so . Hence, The sequence converges to .
The minimum eigenvalue of is the inverse of the largest eigenvalue of . We can run power iteration on to compute the minimum eigenvalue. But we must compute , which is an overhead.
I proposed PGD on the objective subject to . This avoids computing the inverse. The update for this will be:
Choose . Note that and have the same eigenvectors. The eigenvalues corresponding to are . So power iteration on will converge to and will converge to .
To compute the condition number, first find the largest eigenvalue by using PGD. Then choose and compute the smallest eigenvalue by using PGD. Compute the ratio .