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...