An Elementary Proof of the Restricted Invertibility Theorem

Introduction

In this note we study the following well-known theorem of Bourgain and Tzafriri.

for all scalars $\{a_{i}\}_{i\in\sigma}$.

This theorem has had significant applications in the local theory of Banach spaces and in the study of convex bodies in high dimensions. It is also considered a step towards the resolution of the famous Kadison-Singer conjecture, which asks if there exists a partition of $[n]$ into a constant number of subsets $\sigma_{1},\ldots,\sigma_{k}$ for which (1) holds. Recently, the theorem has attracted attention in numerical analysis due to its connection with the column subset selection problem, which seeks to select a ‘representative’ subset of columns from a given matrix. In particular, Tropp has developed a randomized polynomial time algorithm which finds the subset $\sigma$ efficiently.

Bourgain and Tzafriri’s proof of Theorem 1 uses probabilistic and functional analytic techniques and is non-constructive. In the original paper the theorem was shown to hold for $c=d\sim\frac{1}{10^{72}}$. Later on , the same authors proved it for $c=c(\epsilon)=c^{\prime}\epsilon^{2}$ and $d=(1+\epsilon)^{-1}$ for every $0<\epsilon<1$, where $c^{\prime}$ is a universal (tiny) constant. They were interested in the case when $\epsilon$ is small; the quadratic dependence of $c(\epsilon)$ on $\epsilon$ was shown to be necessary in . In another regime, modern methods can be used to obtain the constants $c=1/128$ and $d=1/8\sqrt{2\pi}$ .

In this note, we present a short proof that uses only basic linear algebra, achieves much better constants, and contains a deterministic $O(n^{4})$ time algorithm for finding the set $\sigma$. Our method of proof involves building $\sigma$ iteratively using a ‘barrier’ potential function. Such a method was used by Batson and the authors in to construct linear size spectral sparsifiers of graphs.

Specifically, we prove the following generalization of Theorem 1, in which $\|\cdot\|_{2}$ refers to the spectral (i.e., operator) norm and $\|\cdot\|_{F}$ refers to the Frobenius (i.e., Hilbert-Schmidt) norm.

The original form of Bourgain and Tzafriri’s theorem follows quickly from Theorem 2 with constants

by taking $\{v_{i}\}$ from the standard basis $\{e_{i}\}_{i\leq n}$ and assuming $\|Le_{i}\|=1$. This dominates previous bounds in all regimes, for $\epsilon$ small and large.

Proof of the Theorem

We will build the matrix $A=\sum_{i\in\sigma}(Lv_{i})(Lv_{i})^{T}$ by an iterative process that adds one vector to $\sigma$ in each step. The process will be guided by the potential function This potential function was inspired by Stieltjes transform, which appears in the analysis of the eigenvalues of random matrices. However, we are unaware of a formal connection. This potential function is also related to, but is not identical to, the logarithmic barrier function used in Interior Point Algorithms for Linear Programming.

where the barrier $b$ is a real number that varies from step to step.

Initially $A=0$, the barrier is at $b=b_{0}>0$, and the potential is

Each step of the process involves adding some rank-one matrix $ww^{T}$ to $A$ where $w\in\{Lv_{i}\}_{i\leq m}$ (if $w=Lv_{j}$ then this corresponds to adding $j$ to $\sigma$) and shifting the barrier towards zero by some fixed amount $\delta>0$, without increasing the potential. Specifically, we want

We will maintain the invariant that after $k$ vectors have been added, $A$ has exactly $k$ nonzero eigenvalues, all greater than $b$. Keeping the potential small (in fact, sufficiently negative) will ensure that there is a suitable vector to add at each step.

In any step of the process, we are only interested in vectors $w$ which add a new nonzero eigenvalue that is greater than $b^{\prime}=b-\delta$. These are identified in the following lemma, where the notation $A\succeq B$ means that $A-B$ is positive semidefinite.

Suppose $A\succeq 0$ has $k$ nonzero eigenvalues, all greater than $b^{\prime}>0$. If $w\neq 0$ and

then $A+ww^{T}$ has $k+1$ nonzero eigenvalues greater than $b^{\prime}$.

Let $\lambda_{1}\geq\dotsb\geq\lambda_{k}$ be the nonzero eigenvalues of $A$, and let $\lambda_{1}^{\prime}\geq\dotsb\geq\lambda_{k+1}^{\prime}$ be the $k+1$ largest eigenvalues of $A+ww^{T}$. As the latter matrix is obtained from $A$ by the addition of a rank one positive semi-definite matrix, their eigenvalues interlace :

where we have written the positive and negative terms in the sum separately. By the Sherman-Morisson formula,

Since $w^{T}(A-b^{\prime}I)^{-1}w<-1$, the denominator in the right-hand term is negative. The numerator is positive since $A-b^{\prime}I$ is non-singular and $(A-b^{\prime}I)^{-2}\succeq 0$. So, the right-hand side of (3) is positive.

On the other hand, a direct evaluation of this difference yields

As $\lambda_{k+1}^{\prime}\geq 0$, this is only possible if $\lambda_{k+1}^{\prime}>b^{\prime}$, as desired. ∎

The updated potential after one step, as the barrier moves from $b$ to $b^{\prime}=b-\delta$, can be calculated using the Sherman-Morisson formula:

To prevent an increase in potential, we want choose a $w$ such that

We can now determine how small we need the potential to be in order to guarantee that a suitable $w$, which will allow us to keep on going, always exists.

Suppose $A$ has $k$ nonzero eigenvalues, all of which are greater than $b$, and let $Q$ be the orthogonal projection onto the kernel of $A$. If

then there exists a vector $w\in\{Lv_{i}\}_{i\leq m}$ for which $A+ww^{T}$ has $k+1$ nonzero eigenvalues greater than $b^{\prime}=b-\delta$ and $\Phi_{b^{\prime}}(A+ww^{T})\leq\Phi_{b}(A)$.

The vectors satisfying both of the inequalities (2) and (4) are precisely those $w$ for which

We can show that such a $w$ exists by taking the sum over all $w\in\{Lv_{i}\}_{i\leq m}$ and ensuring that the inequality holds in the sum, i.e., that

Let $\Delta_{b}:=\Phi_{b}(A)-\Phi_{b^{\prime}}(A)$. From the assumption $\Phi_{b}(A)\leq-m-\frac{\|L\|_{2}^{2}}{\delta}$ we immediately have

Noting that $LL^{T}\preceq\|L\|_{2}^{2}I$, we can bound the left hand side as

As $P(A-b^{\prime}I)^{-1}P\succeq 0$ and $P(A-bI)^{-1}P\succeq 0$, it is easy to check that

Thus, by (8), (9), and (10), we are done if we can show that

Taking into account that $\Delta_{b}^{P},\Delta_{b}^{Q}\geq 0$, this is implied by the statement

which upon substituting and rearranging reduces (11) to

Requirement (5) of Lemma 4 is satisfied at the beginning of the process as

To verify that requirement (6) is satisfied initially, first note that the theorem is vacuously true if $\epsilon^{2}\frac{\|L\|_{F}^{2}}{\|L\|_{2}^{2}}<1$. Assuming the converse and recalling that $\epsilon<1$, we may show $\frac{\|L\|_{F}^{2}}{\|L\|_{2}^{2}}\geq 1/\epsilon$ which implies that $\delta<b_{0}$. The inequality

As long as condition (6) is satisfied, we may apply Lemma 4 to add a vector to $\sigma$ while maintaining $\Phi_{b}(A)\leq\Phi_{b_{0}}(0)$. The left-hand inequality in (6) will be satisfied after the first $t-1$ steps if

This inequality is satisfied for all $t\leq\epsilon^{2}\frac{\|L\|_{F}^{2}}{\|L\|_{2}^{2}}$ as

The right-hand inequality in (6) will always be satisfied if it is satisfied initially as the Frobenius norm $\|QL\|_{F}^{2}$ decreases by at most $\|L\|_{2}^{2}$ in each step. Taking $t=\left\lfloor\epsilon^{2}\frac{\|L\|_{F}^{2}}{\|L\|_{2}^{2}}\right\rfloor$ steps leaves the barrier at

Acknowledgements

We would like to thank Kate Juschenko, Roman Vershynin and especially Pete Casazza for helpful comments and corrections to an earlier version of this manuscript.

References