# Projected Gradient Descent for Max and Min Eigenpairs - Proof of Convergence

Let A be a $n \times n$ positive semi-definite matrix. Let $\lambda_1\geq \lambda_2 \geq \dots \geq \lambda_n$ be the eigenvalues in decreasing order and $u_1,u_2,\dots,u_n$ be the corresponding orthonormal eigenvectors. We have

You need to find the Condition number of $A$, which is defined as $\lambda_1/\lambda_n$. You could compute all the eigenvalues and then compute the condition number. But this is superfluous as you just need to compute $\lambda_1$ and $\lambda_n$.

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 $\min (-x^\top Ax)$ subject to $x^\top x=1$.

### 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 $I+\eta A$. So we could try analyzing it like power iteration.

First note that $A$ and $I+\eta A$ have the same eigenvectors when $\eta \geq 0$. The eigenvectors of $I+\eta A$ are $u_1, u_2, \dots, u_n$ and the corresponding eigenvalues are $1+\eta \lambda_1 \geq 1+\eta \lambda_2 \geq \dots \geq 1+\eta \lambda_n$. So we know:

• $A$ and $I+\eta A$ have the same eigenvectors
• PGD on $A$ is just power iteration on $I+\eta A$
• 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 $x_t^\top u_j \to 0$ for $j \neq 1$, then $x_t \to u_1$. We have:

When $j\neq 1$, $x_t^\top u_j \to 0$ so $x_t \to u_1$. Hence, The sequence $x_t^\top A x_t$ converges to $\lambda_1$.

## Minimum Eigenpair

The minimum eigenvalue of $A$ is the inverse of the largest eigenvalue of $A^{-1}$. We can run power iteration on $A^{-1}$ to compute the minimum eigenvalue. But we must compute $A^{-1}$, which is an overhead.

I proposed PGD on the objective $\min (x^\top Ax)$ subject to $x^\top x=1$. This avoids computing the inverse. The update for this will be:

Choose $% $. Note that $A$ and $I - \eta A$ have the same eigenvectors. The eigenvalues corresponding to $u_1, u_2, \dots ,u_n$ are $1-\eta \lambda_1\leq 1-\eta \lambda_2\leq \dots \leq 1-\eta \lambda_n$. So power iteration on $I - \eta A$ will converge to $u_n$ and $x_t^\top A x_t$ will converge to $\lambda_n$.

To compute the condition number, first find the largest eigenvalue $\lambda_1$ by using PGD. Then choose $% $ and compute the smallest eigenvalue $\lambda_n$ by using PGD. Compute the ratio $\lambda_1/\lambda_n$.

Written on June 9, 2019