Geometric perspective of error correcting codes
Roman Vershynin
UC Davis
Error correcting codes are used in modern technology to protect
information from errors. An encoder transforms an n-letter word X (over
some some alphabet F) into an m-letter word Y with m>n. The decoder must
be able to recover X even if r letters of Y are corrupted in any way.
Known constructions of algorithmically efficient error correcting codes
involve deep combinatorial and algebraic methods. I will talk on a
different approach to error correcting codes, through the asymptotic
convex geometry (geometric functional analysis). The main ideais that
most of orthogonal transformations from R^n to R^m form good error
correcting codes over reals (with an efficient decoder). These codes are
robust, so quantization leads to good codes over finite alphabets. The
intuition for this method has been developed from experimental and
theoretical work in signal processing (sparsest representations of
signals). This a joint work with Mark Rudelson.