An elementary proof of the restricted invertibility theorem (Q1760392)

In a seminal and oft-quoted paper [Isr. J. Math. 57, 137--224 (1987; Zbl 0631.46017)], \textit{J. Bourgain} and \textit{L.Tzafriri} proved their ``restricted invertibility theorem'' for operators on finite-dimensional \(\ell_p\)-spaces. The case \(p=2\) is of special interest; in this case, their theorem reads as follows. There exist constants \(c,d>0\) such that, whenever \(T: \ell_2^n \to \ell_2^n\) is a linear operator satisfying the normalisation \(\|Te_i\|=1\) for all~\(i\), there is a subset \(\sigma\subset \{1,\dots,n\}\) of proportional size, i.e., of cardinality \(|\sigma|\geq cn/\|T\|^2\), such that \(T\) is well invertible on \(\text{span}\{e_i: i\in\sigma\}\) in that \(\|Tx\|\geq d\|x\|\) for all vectors supported on~\(\sigma\). The point is, of course, that \(c\) and \(d\) are independent of~\(n\). In their paper, Bourgain and Tzafriri gave a beautiful proof that was, however, not constructive and was based on deep probabilistic and combinatorial reasoning. (In fact, they even gave two proofs.) Also, they did not pay any attention to the size of the constants. The paper under review presents a new proof that is elementary in that it only uses linear algebra, it is algorithmic in that the desired set \(\sigma\) is found by an iterative process, and it gives better constants; in fact, for \(0<\alpha<1\), one can achieve \(c=\alpha^2\) and \(d=(1-\alpha)^2\) so that for \(\alpha\approx 0\), \(d\) is close to~\(1\), and for \(\alpha\approx 1\), \(c\) is close to~\(1\). Actually, the authors prove a generalisation of the Bourgain-Tzafriri theorem from which that result follows readily. Reviewer's remark: An even simpler version of the proof giving slightly worse constants, based on the arguments of the present paper, was provided by \textit{P. G. Casazza} [``The simplified version of the Spielman and Srivastava algorithm for proving the Bourgain-Tzafriri restricted invertiblity theorem'' (2012), \url{arXiv:1208.4013}].