Sampling Theorems for Deterministic Combinatorial Structures and Their Applications

Abstract:

Due to the work of Borel (later re-discovered by Nyquist and Shannon) sampling of deterministic signals (e.g. band-limited signals) is relatively well-understood. However, much is not known about the sampling of combinatorial structures e.g. Codes, Block Designs and Graphs. Sampling of graphs for instance has numerous applications to the studies of disease propagation, human interactions, anomalies in networks, etc.

We discuss our recent contributions toward this direction and their applications:

First, we consider sampling of linear binary vector spaces (a.k.a binary linear codes). For this purpose, our main tools are Random Matrix Theory and the Kolmogorov-Smirnov results. The Marchenko-Pastur law implies (among other things) that singular values of (normalized) +-1 matrices with all i.i.d. elements asymptotically follow the Marchenko-Pastur distribution. We consider a (normalized) +-1 random matrix $A$ whose rows are formed by drawing from elements of a $k$ dimensional binary vector space V $\subseteq GF(2)^n$ (V is sometimes referred to as a k-dimensional binary linear block code of length n) uniformly and in an i.i.d. manner, and then applying the mapping 0--> 1 and 1 ---> -1.

We establish and prove the following result: Assume that all nonzero vectors of V^${\perp}$, the dual of the vector space V (also referred to as the dual code) have at least d non-zero elements (i.e. minimum Hamming distance of the dual code is >= d). We produce an almost sure bound on the distance between the distribution of singular values of $A$ and the Marchenko-Pastur distribution. It follows from our bound that as $d$ grows large, the spectral distribution of $A$ (formed from a structured code) is almost surely identical to that of an i.i.d +-1 matrix!

Philosophically, our result implies that the randomness of a code is related to the minimum distance of the dual code. We briefly discuss the implications of this result on designing random sequences. In particular, it follows immediately from our results that pseudo-noise (PN) sequences (that are used in CDMA systems) do not have desirable randomness properties!

We then mention other generalizations of our results. We discuss generalizations of our result to the spectra of products of structured matrices, and to the similarity of eigenvalues of structured matrices to those given by the Girko circular rule, etc.). The proof of these generalizations requires applications of Voiculescu's free probability theory. These results may be used to compute tight bounds on the spectral efficiency of "practical" (non-random) CDMA systems that use deterministic sequences (such as shift register sequences).

Time remaining, I will discuss our Sampling Theorems for graphs. Here we seek after Borel type theories. At present, our results only apply to large graphs (asymptotic results), but perhaps this may the best that one can expect.

This is a joint work with Behtash Babadi.

Biography:

Vahid Tarokh worked at AT&T Labs-Research and AT&T wireless services until August 2000, where he was the head of the Department of Wireless Communications and Signal Processing. In September 2000, he joined the Department of Electrical Engineering and Computer Sciences (EECS) at MIT as an associate professor. In June 2002, he joined Harvard University as a Gordon McKay Professor of Electrical Engineering . Since July 2005, he is a Hammond Vinton Hayes Senior Fellow of Electrical Engineering at Harvard University, and a Perkins Professor of Applied Mathematics.

Tarokh's output of the last 20 years is summarized in less than 50 research journal papers that have been cited more than 18000 times by other scholars. He is the recipient of a number of awards, and holds 2 honorary degrees.