Processing math: 100%

Statistical Computing

Lecture 9: Eigenanalysis



Yanfei Kang
yanfeikang@buaa.edu.cn

School of Economics and Management
Beihang University
http://yanfei.site

Why numerical linear algebra?

  • Difference between linear algebra and applied linear algebra.
  • Think about linear algebra in Statistics.
  • In curve fitting.
  • In image processing.
  • In signal processing.
  • etc.

We need to know numerical techniques!

Eigenanalysis

  • In general, a matrix acts on a vector by changing both its magnitude and its direction.
  • However, a matrix may act on certain vectors by changing only their magnitude, and leaving their direction unchanged (or reversing it).
    • these vectors are the eigenvectors of the matrix
    • the scaling factor is the eigenvalue.

Example

  • Think about the linear transformation y=Ax, where

A=(2000), x=(cosθsinθ), y=(y1y2).

  • What is its geometric interpretation?

  • What happens when θ=π4?

  • When θ=π2?

  • When θ=0?

Example

  • What if A is not diagnal?
  • How to find its eigenvalues and eigenvectors?
  • If A is a real symmetric matrix
    • Only real eigenvalues
    • n distinct linearly independent eigenvectors
    • pairwise orthogonal
    • A=QΛQT
  • When A is diagonalisable?
  • If a diagonalisation doesn't exist, there is always a triangularisation via Schur Decomposition: A=QSQT.
  • Let us revisit together the properties of eigenvalues and eigenvectors.

What does eigenanalysis help to do?

  • Let's try to understand what Ax=λx is really asking.
  • Can we find a pair of λ and x such that when a matrix A is applied to x, it doesn't change the direction and just scales the vector?
  • If we can find such a pair, then everytime we do something with Ax in some mathematical operation, we can replace it with λx.

What does eigenanalysis help to do?

  • Consider A=(5124) and x=(11).
    • what if we now want to calculate A20x?
    • what if we now want to calculate A1x?
  • Computationally, we would rather work with scalars than matrices and this is what eigenanalysis helps us do.
  • But what if we are not lucky enough to be asked to multiply a matrix by one of its eigenvectors?

Advantages of eigenanalysis

  • It enables us to replace a matrix with a scalar when we have the opportunity to change our coordinate system to the eigenvectors of a matrix.
  • We can express any vector in terms of this new coordinate system.
  • We can use the fact that Ax=λx to simplify calculations.

Application of Eigenanalysis: Google

How to know page rank?

  • How does the search engine know which pages are the most important?
  • Google assigns a number to each individual page, expressing its importance.
  • This number is known as the PageRank and is computed via the eigenvalue problem Aw=λw, where A is based on the link structure of the Internet.

Google's pagerank

  • Suppose we have a set of webpages W, with |W|=n as the number of webpages.
  • We define a connectivity (adjacency) matrix A as follows: Ai,j is 1 if there is a hyperlink from page i to page j and 0 otherwise.
  • Typically A is huge (27.5 billion x 27.5 billion in 2011), but extremely sparse (lots of zero values)

A small example

  • Consider the small set of five webpages.
  • The connectivity matrix is A=(0101100111100100000100100)

A small example

  • The ranking of page i is proportional to the sum of the rankings of all pages that link to i: r4=α(r1+r2+r3).
  • So this is a system of n=5 linear equations: r=αATr, or ATr=(1/α)r.
  • The ranking vector is treated like a probability of relevance, so we need to then rescale so that Σni=1=1.
  • Go to R and compute pageranks.

What you need to realise for now

  • Finding the eigenvalues and eigenvectors of a massive matrix is computationally challenging though (don’t try to solve the characteristic polynomial!)
  • and you will learn numerical techniques later.