Tayzwi

Should be reading more and writing less, but well...

Thursday, November 30, 2006

 

Eigen

The inimitable quip-fuckin'-master forced a comment which is worth expanding a little more.

Ever since I found that the PageRank vector of the web-graph is the dominant eigenvector of its matrix representation, I have been meaning to get to the bottom of this eigenvector-eigenvalue concept. I am still snorkeling; long time to scuba dive.

Most of us studied concepts like simultaneous equations in our high school algebra classes, but never really wondered about them deeply, or even more so, felt that they were difficult. Problems like - 3 oranges and 4 apples cost 17 rupees; 2 oranges and 3 apples cost 12 rupees; how much does each apple cost? - never seemed that difficult. We knew that the equations that represented these statements were 'fluid,' and need not apply to just these statements, and an overall tool was being mastered.

Somehow, the same never happened to tools like primal-dual, or eigenvalues-eigenvectors, or other tools from linear algebra, statistics, calculus, etc. Somewhere, the learning process got fucked because of an emphasis on just the concept, and a palpable lack of intuitive visualization. When people talk about a matrix, I never think in terms of transformations. If I did, I could see that some transformations would leave some 'victims' unchanged. And these victims were the eigenvectors of that transformation. Maybe they could change in terms of scale, but not in terms of what they fundamentally are. Here is an example from the Wikipedia entry on Eigenvalue:

As the Earth rotates, every arrow pointing outward from the center of the Earth also rotates, except those arrows that lie on the axis of rotation. Consider the transformation of the Earth after one hour of rotation: An arrow from the center of the Earth to the Geographic South Pole would be an eigenvector of this transformation, but an arrow from the center of the Earth to anywhere on the equator would not be an eigenvector. Since the arrow pointing at the pole is not stretched by the rotation of the Earth, its eigenvalue is 1.

So, was Neo an Eigenvector of The Matrix? I wonder...

As for what it means when they say that PageRank is the dominant eigenvector of the web-graph, we have to visualize the web-graph's matrix representation as a transformation. The matrix representation has all web-pages in rows and columns, and if a web-page in row i has a hyperlink to a web-page in column j, the [i, j] entry is 1, else 0. What does it mean to say that this matrix is a transformation? And what does it mean to say that it can act on 'victims' to change them? And if the 'victim' happens to be a vector which has the pages' pagerank values, the transformation doesn't affect it. What does that say about PageRank, and how is that related to our intuitive perception of pagerank as the importance of each page on a global scale?

We will get to primal-dual some other time. My head hurts. It hurts.

ps: And these are all just tools; albeit mental in nature. If we don't master them, well, it's ok I guess. We can always go back to intellectual stone age, or whatever was there before that. I mean, I always fancied myself as a Cro-Magnon.

Labels:


Archives

February 2004   July 2004   August 2004   September 2004   October 2004   November 2004   December 2004   January 2005   February 2005   March 2005   April 2005   May 2005   June 2005   July 2005   August 2005   September 2005   October 2005   November 2005   December 2005   January 2006   February 2006   March 2006   April 2006   May 2006   June 2006   July 2006   August 2006   September 2006   October 2006   November 2006   January 2007   April 2007   May 2007   June 2007   November 2007   December 2007   January 2008   March 2008   June 2008   February 2009   June 2009   February 2010   November 2010  

Quick index to blog-posts I like (from my personal website)

This page is powered by Blogger. Isn't yours? Statscounter is generating statistics of this page