Triangular" Dvoretzky matrices and online coding

Seminar | March 6 | 3-4 p.m. | 1011 Evans Hall

 Piyush Srivastava, Tata Institute of Fundamental Research

 Department of Statistics

A special case of the classical Dvoretzky theorem states that the space of n-dimensional real vectors equipped with the l1 norm admits a large "Euclidean section", i.e. a subspace of dimension Θ(n) on which a scaled l1 norm essentially agrees with the Euclidean norm. In particular, such a subspace can be realized as the column space of a "tall" n × (n/k) random matrix A with identically distributed independent Gaussian entries (k > 1).

This special case of the Dvoretzky theorem has a natural interpretation in the setting of encoding real vectors for transmission across an adversarial noisy channel when the vector x to be encoded is given in advance (the so-called "block coding" scenario), so that the encoding can be computed in an "offline" fashion. Motivated by the same problem in the setting when the encoding has to be "online", i.e., has to be carried out as each entry of x becomes available, we give randomized constructions of triangular matrices with properties similar to Dvoretzky matrices. The guarantees provided by these constructions in the "online" scenario are close to, but still somewhat worse than, those provided by the Dvoretzky theorem in the "block" scenario, and the question of finding the optimal triangular version of the Dvoretzky theorem remains open.

Joint work with Leonard J. Schulman.

 CA, sganguly@berkeley.edu