Almost orthogonal submatrices of an orthogonal matrix (Q1806260): Difference between revisions

The author deals with a problem on orthogonal matrices posed by \textit{B. Kashin} and \textit{L. Tzafriri} in a preprint entitled ``Some remarks on the restrictions of operators to coordinate subspaces'', namely: given \(\varepsilon> 0\), \(n,M\in\mathbb{N}\), \(n< M\), and \(A\) an \(n\times M\) matrix whose rows are orthogonal, determine the smallest cardinality \(L(A,\varepsilon)\) of a subset \(I\subset \{1,\dots, M\}\) so that for all \(x\in \ell^n_2\) \[ (1- \varepsilon)\cdot\|x\|\leq \sqrt{{M\over|I|}}\cdot\|R_I A^T x\|\leq (1+\varepsilon)\cdot\|x\|, \] where \(R_I\) is the orthogonal projection from \(\mathbb{R}^M\) onto the space generated by the vector \(e_i\), \(i\in I\), of the canonical basis of \(\mathbb{R}^M\). This problem arises from the question of finding a good discretization of an orthonormal system, and can be seen as the dual of finding an approximate John decomposition. B. Kashin and L. Tzafriri (loc. cit.) give an estimate of \(L(A,\varepsilon)\), under the assumption that all the entries of \(A\) have the same absolute value \(1/\sqrt M\). This estimate is improved by the author in this paper: If \(A= (a_{ij})\), and there exists \(t\geq 1\) such that for all \(j\) \[ \sqrt{{M\over n}}\cdot \sqrt{\sum^n_{i= 1} a^2_{i,j}}\leq t \] then \(L(A,\varepsilon)\leq C{t^2\over \varepsilon^2} n\log{nt^2\over \varepsilon^2}\).