Moscow-Petersburg Seminar on Low-dimensional mathematics
December 29, 2006

Mark Rudelson (University of Missouri-Columbia)
Singular values of a random matrix and applications to convexity.

Abstract

Let A be an N by n matrix, whose entries are independent random
variables. Such matrices are frequently used in convex geometry to
construct sections or projections of a convex body having certain
properties. In many problems deterministic constructions are not
available, so the random sections or projections are used instead.
To apply this approach one has to show that a random matrix defines
a "nice" embedding of R^n into R^N with high probability. This
requires bounding the distortion of the Euclidean metric by the
matrix A, i.e. the ratio of the largest and the smallest singular
value of A.

For a random matrix with independent entries, the largest
singular value is the most robust, being exponentially concentrated
about its mean. Therefore, the study of the distortion of a random
matrix can be essentially reduced to the estimates of the smallest
singular value. For general random matrices such estimates were
known only for N>>n. The problem of obtaining such estimates becomes
more difficult when N is close to n, since in this case the smallest
singular value possesses no concentration properties. In this talk
we show that this problem is related to finding sections of the
N-dimensional cross polytope, which are close to the Euclidean ball
and obtain bounds for the distortion valid for any N and n.

---
http://www.pdmi.ras.ru/~lowdimma