Almost orthogonal submatrices of an orthogonal matrix

Abstract

Lett≥1 and letn, M be natural numbers,n<M. Leta=(a _i,j ) be ann xM matrix whose rows are orthonormal. Suppose that the ℓ₂-norms of the columns ofA are uniformly bounded. Namely, for allj $\sqrt {\frac{M}{n}} \cdot \left( {\sum\limits_{i = 1}^n {a_{i,j}^2 } } \right)^{1/2} \leqslant t.$

Using majorizing measure estimates we prove that for every ε>0 there exists, a setI ⊃ {1,…,M} of cardinality at most$C \cdot \frac{{t^2 }}{{\varepsilon ^2 }} \cdot n \cdot log\frac{{nt^2 }}{{\varepsilon ^2 }}$ such that the matrix$\sqrt {M/\left| I \right|} \cdot A_I^T$, whereA _I =(a _i,j ) _j∈I , acts as a (1+ε)-isomorphism from ℓ ⁿ₂ into$\ell _2^{\backslash I\backslash }$.