PageRank

March 6, 2008 in linear algebra, technology | Tags: | Leave a comment

Google’s PageRank idea is a marvel of power and simplicity. An introduction to the basic version of this algorithm was provided in a Numerical Linear Algebra course and is reproduced here.

Read the rest of this entry »

Shifted Transversal Designs and Expander Graphs

March 5, 2008 in coding theory, compressed sensing, expander graphs, group testing | Tags: | 16 comments

Observation : A shifted transversal design (STD) is similar to the adjacency matrix of an (unbalanced) expander graph.

STD(n;q;k) is a matrix construction algorithm that accepts parameters : n,q and k to produce a (qk x n) 0-1 matrix with certain special properties. Each of the n columns has k 1’s in it, which are distributed, one in every q x n block. Each row has usually \lceil \frac{n}{q} \rceil 1’s in it. Such matrices are very useful as pooling design schemes and error-correcting codes, among other things. The STD algorithm is due to N. Thierry-Mieg.

Expander Graphs are sparse but highly connected graphs. From here, we learn that a bipartite graph H = (X,Y,E) is said to be an (n,m,d, \alpha, \gamma)-expander if |X|=n, |Y|=m, the degree of each node in X is d, and for every A \subseteq X, \left|A\right| \le \alpha n, the set of vertices N(A) \subseteq Y that are adjacent to A satisfies \left|N(A)\right| \ge \gamma \left|A\right|. A higher value of \gamma implies a better expansion property.

Read the rest of this entry »

Rat Poison and Information Theory

February 27, 2008 in group testing, information theory | 1 comment

Consider this puzzle :

Some scientist-types have a week to throw a party. They have 7 bottles of wine in their cellar. However, the vintage bottles have lost their labels. Of these, 1 bottle was rat poison, but which one ? To test this out, they volunteer their pet rats, but have only 3 such rats. Also it takes a rat about a week to die of the poison. They need to figure out a way to test all 7 bottles using just 3 rats, such that, at the end of the week they know exactly which bottle was rat poison.

Read the rest of this entry »

Matrix Norms

January 24, 2008 in linear algebra | Tags: , , | Leave a comment

A matrix norm (for some A \in \mathbb{C}^{m \times n}) is defined as :

\left|\left|A\right|\right| = \sup_{x \ne 0} \frac{\left|\left|Ax\right|\right|}{\left|\left|x\right|\right|}

where, \left|\left|.\right|\right| is a vector norm and \sup is the supremum, a sort of maximum value \ge this value. In some sense, this measures the stretching that the matrix A imparts onto the vector x.

Interestingly, it can be shown that the \left|\left|A\right|\right|_1 norm is nothing but the maximum column (absolute) sum of the matrix A and the \left|\left|A\right|\right|_{\infty} norm is the maximum sum of absolute values of elements of a row in A. More importantly, the useful \left|\left|A\right|\right|_2 norm is actually the largest singular value of A.

We can also show how these norms are related to each other. For example,

\frac{1}{\sqrt{m}}\left|\left|A\right|\right|_2 \le \left|\left|A\right|\right|_{\infty} \le \sqrt{n}\left|\left|A\right|\right|_2

To show this, first consider the vector norm relationship for x \in \mathbb{C}^n.

\left|\left|x\right|\right|_{\infty} = \left(\left|x\right|^2 \right)^{1/2} \le \left(\sum_{i=1}^{n}\left|x\right|^2 \right)^{1/2} = \left|\left|x\right|\right|_2

Therefore, \left|\left|x\right|\right|_{\infty} \le \left|\left|x\right|\right|_2

\left|\left|x\right|\right|_2 = \left(\sum_{i=1}^{n}\left|x\right|^2 \right)^{1/2}

Replace each x_i with the maximum (absolute) value among them. Thus,

\left|\left|x\right|\right|_2 \le \mathsf{max}_i \left|x_i\right|\left(\sum_i 1\right)^{1/2} = \sqrt{n}\left(\mathsf{max}_i \left|x\right|\right) = \sqrt{n}\left| \left|x\right|\right|_{\infty}

So, \left|\left|x\right|\right|_{\infty} \le \left|\left|x\right|\right|_2 \le \sqrt{n} \left|\left|x\right|\right|_{\infty}.

Now, we know, \left|\left|A\right|\right|_{\infty} = \sup_{x \ne 0} \frac{\left|\left|Ax\right|\right|_{\infty}}{\left|\left|x\right|\right|_{\infty}}.

Using the inequalities from the vector norm, we have, \left|\left|Ax\right|\right|_{\infty} \le \left|\left|Ax\right|\right|_{2} and \left|\left|x\right|\right|_{\infty} \ge \frac{1}{\sqrt{n}}\left|\left|x\right|\right|_{2} .

So, substituting them into the matrix norm definition, we get,

\left|\left|A\right|\right|_{\infty} \le \sup_{x \ne 0} \frac{\left|\left|Ax\right|\right|_{2}}{\frac{\left|\left|x\right|\right|_{2}}{\sqrt{n}}}.

This is how we get, \left|\left|A\right|\right|_{\infty} \le \sqrt{n}\left|\left|A\right|\right|_{2}.

Similarly, \left|\left|Ax\right|\right|_{2} \le \sqrt{m}\left|\left|Ax\right|\right|_{\infty} (since the vector Ax \in \mathbb{C}^m) and \left|\left|x\right|\right|_{2} \ge \left|\left|x\right|\right|_{\infty}, implies,

\left|\left|A\right|\right|_{2} = \sup_{x \ne 0} \frac{\left|\left|Ax\right|\right|_{2}}{\left|\left|x\right|\right|_{2}} \le \sup_{x \ne 0} \frac{\sqrt{m}\left|\left|Ax\right|\right|_{\infty}}{\left|\left|x\right|\right|_{\inf}} = \sqrt{m}\left|\left|A\right|\right|_{\infty}

Finally, we get,

\frac{1}{\sqrt{m}}\left|\left|A\right|\right|_2 \le \left|\left|A\right|\right|_{\infty} \le \sqrt{n}\left|\left|A\right|\right|_2