2
$\begingroup$

I was trying to understand how to use the inverse interation method to compute the page rank as an exercise.

In this chapter (page 4) about page rank (by Cleve Moler), the author suggests to use the following statements to compute the page rank using the inverse iteration:

c = sum(G, 1);
k = find(c ~= 0);
D = sparse(k, k, 1 ./ c(k), n, n);
e = ones(n, 1);
I = speye(n, n);
...

A = p*G*D + delta
x = (I - A) \ e
x = x / sum(x)

where p should be the probability that a random walk follows a link and delta should be (1 - p) / n (as far I've understood), i.e. the probability that a particular random page is chosen. Note that 1 - p is the probability that some arbitrary page is chosen.

Now, in the chapter 8 of the book A First Course in Numerical Methods (about Eigenvalues and Singular Values), at page 228 (at least in this version that I've), there's the following inverse iteration method:

enter image description here

Main Questions

Excluding the calculation of $\lambda$ (the eigenvalue), what's the relation between this inverse iteration and the previous? How does one reach from this last exposure of the algorithm (in the picture) to the Matlab implementation above? A step by step procedure would really be appreciated!


Notes (so that you don't have to answer to these):

  1. I understood that the shift inverse method consists in finding the eigenven values of $(A - \alpha I)^{-1}$ instead of $A$. Even though I can't visualize really how this would be helpful.

  2. I understood that $(A - \alpha I)\tilde{v} = v_{k - 1}$ comes from $\tilde{v} = (A - \alpha I)^{-1}v_{k - 1}$, but we don't want to compute the inverse of $(A - \alpha I)$.

  3. I understood that we can choose $\alpha$ (so that it's close to the wanted eigenvalue). Since we know that the sought eigenvalue is $1$, we the statement $(A - \alpha I)$ may simplify to $(A - I)$...

Other Minor Questions

  1. Why are we using delta in A = p*G*D + delta.

  2. What's A in the inverse iteration of the picture?

  3. Again in this chapter (page 4) about page rank (by Cleve Moler), the author says (after those statements above) that (I - A) is theoretically singular. Why is that? And how could we avoid it?

$\endgroup$
  • $\begingroup$ It usually goes by the name Rayleigh_quotient_iteration for symmetric matrices. $\endgroup$ – percusse Oct 4 '16 at 13:38
  • $\begingroup$ @percusse From what I understood the Rayleigh quotient iteration is actually an extension of the inverse iteration method, where at each iteration we try to approximate the eigenvalue we're seeking, in the case it's unknown. But in the case above, the eigenvalue is known, so there's no point of trying to approximate it. $\endgroup$ – nbro Jan 17 '17 at 14:38
2
$\begingroup$

The MATLAB code that you've computed finds the eigenvector of $A$ associated with the eigenvalue 1. We know for this particular problem that $A$ has 1 as an eigenvalue- this can be shown using the Perron-Frobenius Theorem. This code isn't using the inverse iteration algorithm.

The inverse iteration algorithm can be used to find an eigenvalue and corresponding eigenvector of $A$ starting with a value of $\alpha$ that is close to an eigenvalue. The algorithm could be used starting with $\alpha=1$ to compute the eigenvector of $A$ associated with the eigenvalue 1. However, this is overkill since we already know that the eigenvalue is exactly 1.

You can easily implement the inverse iteration and start it with $\alpha=1$ to verify this.

$\endgroup$
  • $\begingroup$ Actually Perron-Frobenius does not state that $A$ has 1 as eigenvalue. This fact can be proved directly using the fact that $e^TA=e^T$ (with $e$ as in OP's code). $\endgroup$ – Federico Poloni Jan 18 '17 at 14:11
0
$\begingroup$

I haven't found all answers to my questions, but in the meantime I found some answers to a few questions.


  1. Why are we using delta in A = p*G*D + delta?

delta = $\delta = \frac{1 - p}{n}$, as defined in page 2 of C. Moler's article, is the probability that a particular random page is chosen. Note that $1 - p$ is the probability that some arbitrary page is chosen and $p$ is the probability that a random walk from a user follows a specific link.

Why would this be helpful to answer my question?

It's helpful because we're defining A we're assuming that there are always outlinks.

Why is that the case?

In the same paper, $A$ is defined for the power method as $A = pGD + ez^T$, which is very similar to the formula for the inverse iteration, but we use $ez^T$ instead of delta.

$$ z^T= \begin{cases} \delta = \frac{1 - p}{n}, \text{ if } c_j \neq 0 \\ \frac{1}{n}, \text{ if } c_j = 0 \end{cases} $$

So, as we can see from the definition of $z$, by using just $\delta$ in the inverse iteration method I assume that we're assuming that all nodes have an outgoing link or, equivalently, $c_j \neq 0$. Note that $n$ is the number of nodes in the graph.

  1. Again in this chapter (page 4) about page rank (by Cleve Moler), the author says (after those statements above) that (I - A) is theoretically singular. Why is that? ...

We want to solve the equation $Ax = x$. We know that our sought eigenvalue is $1$, and this is why we're omitting $\lambda$ in $Ax = \lambda x$. Given this, we can manipulate the equation as follows

\begin{align*} Ax &= x \\ Ax &= Ix \\ Ax - Ix &= \vec{0} \\ (A - I)x &= \vec{0} \end{align*}

Now, from the beginning, we're actually assuming $x$ is not the zero vector because it represents the state vector or PageRank vector. Hence, knowing that $x$ can't be $\vec{0}$, we conclude that $(A - I)$ has a non-trivial null-space (or kernel) or, equivalently, $(A - I)$ is singular, or has determinant zero, or $(A - I)$ is not invertible.

... And how could we avoid it?

It's explained in page $4$ of the previously mentioned article. Apparently, using Guassian elimination (i.e. \ operator in Matlab, which is a robust operation that takes into account many possibilities regarding the operands), roundoff errors seem to make $(A - I)$ not singular and the computation not fail. From the article:

Because $I − A$ is theoretically singular, with exact computation some diagonal element of the upper triangular factor of $I − A$ should be zero and this computation should fail.

But with roundoff error, the computed matrix $I - A$ is probably not exactly singular. Even if it is singular, roundoff during Gaussian elimination will most likely prevent any exact zero diagonal elements.

We know that Gaussian elimination with partial pivoting always produces a solution with a small residual, relative to the computed solution, even if the matrix is badly conditioned.

The vector obtained with the backslash operation, (I - A)\e, usually has very large components. If it is rescaled by its sum, the residual is scaled by the same factor and becomes very small.

Consequently, the two vectors $x$ and $A*x$ equal each other to within roundoff error.

In this setting, solving the singular system with Gaussian elimination blows up, but it blows up in exactly the right direction.


Note

Questions still not answered

  • Main question
  • Minor question number 2
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.