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.

Maximum Eigenpair

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 .

Minimum Eigenpair

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 .

Written on June 9, 2019