On a new method for controlling the entire spectrum in the problem of column subset selection (Q2334433)

Let \(X \in \mathbb R ^{n\times p}\) be a matrix such that all columns of \(X\) have unit Euclidean \(\ell_2\)-norm. The authors consider a problem of well conditioned column selection. It consists of finding the largest subset of columns of \(X\) such that the singular values of the corresponding submatrix are elements of a prescribed interval \([1-\varepsilon, 1+\varepsilon]\). The one-sided problem of finding the largest possible \(T \subset \{1, \dots, p\}\) such that the corresponding submatrix \(X_T\) satisfies \(\lambda_{\min}(X^t_TX_T)\geq 1-\varepsilon\) is called the restricted invertibility problem and has a long history starting with the seminal work of \textit{J. Bourgain} and \textit{L. Tzafriri} [Isr. J. Math. 57, 137--224 (1987; Zbl 0631.46017)]. The authors give a short and elementary proof of the following result: Let \(X\) be an \(n\times p\) matrix whose columns have unit \(\ell_2\)-norm and let \(\varepsilon\) be an element of \((0,1)\). Then there exists \(T \subset \{1, \dots, p\}\) with \(|T| \geq R\) and \[R \log R \leq \frac{\varepsilon^2}{4(1+\varepsilon)}\frac{p}{\|X\|^2}\] such that \(1-\varepsilon \leq \lambda_{\min}(X_T^tX_T)\leq\lambda_{\max}(X_T^tX_T)\leq 1+\varepsilon\). Moreover, there are bounds on each of the individual eigenvalues of \(X_T^tX_T\).