Can the Power Method be used here?

Question

Given a set of $n$ points on which a triangulation is performed, it is possible to construct coefficients $\lambda_{ij}>0$ such that each point $x_i$ is a convex combination of the points connected to it. Suppose $N(i)$ is a set of points adjacent to $x_i$ in a triangulation; then, for each $x_i$,

$$\sum_{j\in N(i)} \lambda_{ij}x_j = x_i $$

and

$$\sum_{j\in N(i)} \lambda_j = 1.$$

In matrix form,

$$\Lambda x=x$$

where $\Lambda$ is a square, $n\times n$, row stochastic matrix (non-negative entries, and no self-loops).

Now suppose matrix $\Lambda$ is given. My questions are:

1. Can one reach configuration $x$ by the power method, i.e., by repeatedly multiplying $\Lambda$ by a vector? The "dominant" eigenvector is $1_n$, so one would have to orthogonalize against it to the "second dominant". I am asking because the above matrix form reminds me of the definition of eigenvalue/eigenvector.

2. If not, what would be a good approach to compute such a configuration? Is the solution unique?

I think that configuration $x$ is the solution to the problem of finding minimum of

$$ \sum_{(i,j) \in E} (x_i - x_j)^2, $$

where $E$ is the set of the edges of the triangulation. However, here one should compute the eigenvectors associated with the smallest eigenvalues. To establish the relation, I used the relation between the Laplacian and the adjacency matrix, as in the following paper.

• Yehuda Koren, On Spectral Graph Drawing [PDF].

One more interesting question:

3. Can the coefficients $\lambda_{ij}$ be constructed in such a way that $\lambda_{ij} = \lambda_{ji}$, meaning that the matrix $\Lambda$ is symmetric? This way of constructing coefficients means that the power method should converge to $x$.

Answer 1

Your intuition is right, solving $\Lambda x = x$ for $x$ given $\Lambda$ is similar to an eigenvalue problem, except you already know the eigenvalue $\lambda_1 = 1$ and its corresponding eigenvector $x_1 = 1_n$. You also know that the rest of the eigenvalues have modulus less than one since $\Lambda$ is a left-stochastic matrix, so it seems that the power method will work if you are interested in the finding the rest of the eigenvalues/eigenvectors. The idea that you suggest of "removing" the largest eigenvalue $\lambda_1 = 1$ so that the power method converges to the second-dominant eigenvector $x_2$ is known as deflation, and this would be necessary if you wanted to find the rest of the eigenvectors using the power method. There are some very simple ways to accelerate the power method, you should search up shifted inverse iteration, and its improvement Rayleigh quotient iteration.

The power (shifted inverse, Rayleigh quotient) method may not work if you have multiple dominant eigenvalues (i.e., $\lambda_2$ and $\lambda_3$ have the same modulus). To overcome this, you can use subspace iteration, which is basically the power method, except you replace your random initial $x$ vector with a matrix (whose columns are linearly independent), so that you get convergence to multiple eigenvectors at once. The most popular version of subspace iteration makes use of the QR factorization for normalization, and it is commonly known as the QR algorithm. The advantage of the QR algorithm is that it can be set up to obtain all of the eigenvalues of $\Lambda$. Many of the ideas from the power method (e.g., using shifts, using deflation) can be extended to the QR algorithm to accelerate convergence. There are also other things you can do to make the QR algorithm faster (e.g., reduce your matrix $\Lambda$ into an upper-Hessenberg matrix using Householder transformations, or using Given's rotations if your matrix is sparse or you are interested in parallelism).

TLDR; If you want all of the eigenvalues, you should probably use the QR algorithm instead. If you only want a few of the largest (or smallest, or middle) eigenvalues, you can use rayleigh quotient iteration + deflation. This might be advantageous if your matrix is huge and sparse, in which case you wouldn't need to compute an expensive QR factorization.

Note that all of these methods fall under the category of "subspace iteration" (their proof of convergence is essentially the same as the power method). You can conveniently look up most of the things I mentioned here. Also, these methods are extremely easy to understand and implement, which is why I recommend these. More sophisticated eigenvalue algorithms are commonly used nowadays, but many of them rely on the same principles.