RESTRICTED INVERTIBILITY REVISITED

ASSAF NAOR AND PIERRE YOUSSEF

Dedicated to Jirka Matoušek

Abstract. Suppose that m, n ∈ ℕ and that A : ℝ^{m} → ℝ^{n} is a linear operator. It is shown here that if k, r ∈ ℕ satisfy k < r ⩽ rank(A) then there exists a subset σ ⊆ {1, …, m} with |σ| = k such that the restriction of A to ℝ^{σ} ⊆ ℝ^{m} is invertible, and moreover the operator norm of the inverse A^{−1} : A(ℝ^{σ}) → ℝ^{m} is at most a constant multiple of the quantity \sqrt{mr/((r − k) ∑_{i=r}^{m} s_{i}(A)^{2})}, where s_{1}(A) ⩾ … ⩾ s_{m}(A) are the singular values of A. This improves over a series of works, starting from the seminal Bourgain–Tzafriri Restricted Invertibility Principle, through the works of Vershynin, Spielman–Srivastava and Marcus–Spielman–Srivastava. In particular, this directly implies an improved restricted invertibility principle in terms of Schatten–von Neumann norms.

1. Introduction

Given m, n ∈ ℕ, the rank of a linear operator A : ℝ^{m} → ℝ^{n} equals the largest possible dimension of a linear subspace V ⊆ ℝ^{m} on which A is injective, i.e., the inverse A^{−1} : A(V) → V exists. The restricted invertibility problem asks for conditions on A that ensure a strengthening of this basic fact from linear algebra in two ways, corresponding to additional structural information on the subspace V ⊆ ℝ^{m} on which A is injective, as well as quantitative information on the behavior of the inverse A^{−1} : A(V) → V. Firstly, the goal is to find a large dimensional coordinate subspace on which A is invertible, i.e., we wish to find a large subset σ ⊆ {1, …, m} such that A is injective on ℝ^{σ} ⊆ ℝ^{m}. Secondly, rather than being satisfied with mere invertibility we ask for A to be quantitatively invertible on ℝ^{σ} in the sense that the operator norm of the inverse A^{−1} : A(ℝ^{σ}) → ℝ^{σ} is not too large. Obviously, additional assumptions on A are required for such conclusions to hold true.

The following theorem, which is known as the Bourgain–Tzafriri Restricted Invertibility Principle [BT87, BT89, BT91], is a seminal result that addressed the above question and had major influence on subsequent research, with a variety of interesting applications to several areas. Throughout what follows, for m ∈ ℕ the standard coordinate basis of ℝ^{m} will be denoted by e_{1}, …, e_{m} ∈ ℝ^{m}.

Theorem 1 (Bourgain–Tzafriri). There exist two universal constant c, C ∈ (0, ∞) with the following property. Suppose that m ∈ ℕ and that A : ℝ^{m} → ℝ^{m} is a linear operator such that the Euclidean norm of the vector Ae_{j} ∈ ℝ^{m} equals 1 for every j ∈ {1, …, m}. Letting ∥A∥ denote the operator norm of A, there exists a subset σ ⊆ {1, …, m} with |σ| ⩾ cm/∥A∥^{2} such that A is injective on ℝ^{σ} and the operator norm of the inverse A^{−1} : A(ℝ^{σ}) → ℝ^{σ} is at most C.

In what follows, for p ∈ [1, ∞] and m ∈ ℕ the ℓ_{p} norm of a vector x ∈ ℝ^{m} will be denoted as usual by ∥x∥_{p}. Thus ∥x∥_{2} is the Euclidean norm of x. We shall also denote (as usual) by ℓ_{p}^{m} the normed space ℝ^{m} equipped with the ℓ_{p} norm. The standard scalar product on ℝ^{m} will be denoted ⟨·, ·⟩. For k, m, n ∈ ℕ and a k-dimensional subspace V ⊆ ℝ^{m}, the Schatten–von Neumann p norm of a linear operator A : V → ℝ^{n} will be denoted below by ∥A∥_{S_{p}}. Thus

∥A∥_{S_{p}} =^{def} (Tr(A^{∗}A)^{\frac{p}{2}} )^{\frac{1}{p}} = ( ∑_{j=1}^{k} s_{j}(A)^{p})^{\frac{1}{p}} ,

A. N. was supported by BSF grant 2010021, the Packard Foundation and the Simons Foundation.

where s_{1}(A) ⩾ s_{2}(A) ⩾ … ⩾ s_{k}(A) denote the singular values of A, i.e., they are the (decreasing rearrangement of the) eigenvalues of the positive semidefinite operator \sqrt{A^{∗}A} : V → V^{∗}. Thus ∥A∥_{S_{∞}} = s_{1}(A) is the operator norm of A. Also, ∥A∥_{S_{2}} is the Hilbert–Schmidt norm of A, i.e., for every orthonormal basis u_{1}, …, u_{k} of V we have ∥A∥_{S_{2}}^{2} = ∑_{i=1}^{k} ∑_{j=1}^{n}⟨Au_{i}, e_{j}⟩^{2} = ∑_{i=1}^{k} ∥Ae_{i}∥_{2}^{2}. Below it will sometimes be convenient to denote the smallest singular value of A by s_{min}(A) = s_{k}(A). Thus A is injective if and only if s_{min}(A) > 0, in which case ∥A^{−1}∥_{S_{∞}} = 1/s_{min}(A).

Given m ∈ ℕ and σ ⊆ {1, …, m} it will be convenient to denote the formal identity from ℝ^{σ} to ℝ^{m} by J_{σ} : ℝ^{σ} → ℝ^{m}, i.e., J_{σ}((a_{j})_{j∈σ}) = ∑_{j∈σ} a_{j}e_{j} for every (a_{j})_{j∈σ} ∈ ℝ^{σ}. With this notation, given an operator A : ℝ^{m} → ℝ^{n} that is injective on ℝ^{σ} we can consider the operator (AJ_{σ})^{−1} : A(ℝ^{σ}) → ℝ^{σ}. We shall sometimes drop the need to mention explicitly that A is injective on ℝ^{σ} by adhering to the convention that if A is not injective on ℝ^{σ} then ∥(AJ_{σ})^{−1}∥_{S_{∞}} = ∞.

Using the above notation, Theorem 1 asserts that if A : ℝ^{m} → ℝ^{m} is a linear operator that satisfies ∥Ae_{j}∥_{2} = 1 for all j ∈ {1, …, m} then there exists σ ⊆ {1, …, m} with |σ| ≳ m/∥A∥_{S_{∞}} such that ∥(AJ_{σ})^{−1}∥_{S_{∞}} ≲ 1, or equivalently s_{min}(AJ_{σ}) ≳ 1. Here, and in what follows, we use the following standard asymptotic notation. Given two quantities K, L ∈ ℝ the notation K ≲ L (respectively K ≳ L) means that there exists a universal constant c ∈ (0, ∞) such that K ⩽ cL (respectively K ⩾ cL). The notation K ≍ L means that both K ≲ L and K ≳ L hold true.

The following theorem is a useful strengthening of the Bourgain–Tzafriri Restricted Invertibility Principle that was discovered by Vershynin in [Ver01].

Theorem 2 (Vershynin). There exists a universal constant c ∈ (0, ∞) with the following property. Fix k, m, n ∈ ℕ. Let A : ℝ^{m} → ℝ^{n} be a linear operator with ∥Ae_{j}∥_{2} = 1 for all j ∈ {1, …, m}. Also, let Δ : ℝ^{n} → ℝ^{n} be a positive definite diagonal operator, i.e., there exist d_{1}, …, d_{n} ∈ (0, ∞) such that Δx = (d_{1}x_{1}, …, d_{n}x_{n}) for every x = (x_{1}, …, x_{n}) ∈ ℝ^{n}. Suppose that k < ∥AΔ∥_{S_{2}}^{2}/∥AΔ∥_{S_{∞}}^{2} and write k = (1 − ε)∥AΔ∥_{S_{2}}^{2}/∥AΔ∥_{S_{∞}}^{2} where ε ∈ (0, 1) (thus ε = 1 − k∥AΔ∥_{S_{∞}}^{2}/∥AΔ∥_{S_{2}}^{2}). Then there exists a subset σ ⊆ {1, …, m} with |σ| = k such that ∥(AJ_{σ})^{−1}∥_{S_{∞}} ⩽ ε^{−c log(1/ε)}.

For a linear operator T : ℝ^{m} → ℝ^{n}, the quantity ∥T ∥_{S_{2}}^{2}/∥T ∥_{S_{∞}}^{2} is often called the stable rank of T, though this terminology sometimes also refers to the quantity ∥T ∥_{S_{1}}/∥T ∥_{S_{∞}}. In both cases, the use of the term ‘stable’ in this context expresses the fact that the quantity in question is a robust replacement for the rank of T in the sense that the rank of T could be large due to the fact that T has many positive but nevertheless very small singular values, while if the stable rank of T is large then its singular values are large on average. Below we shall use the terminology ‘stable rank’ exclusively for the quantity ∥T ∥_{S_{2}}^{2}/∥T ∥_{S_{∞}}^{2}, which we denote by srank(T) = ∥T ∥_{S_{2}}^{2}/∥T ∥_{S_{∞}}^{2}.

Theorem 1 coincides with the special case ε = \frac{1}{2} and Δ = I_{n} of Theorem 2, where I_{n} is the identity operator on ℝ^{n}. However, Theorem 2 improves over Theorem 1 in three ways that are important for geometric applications. Firstly, Theorem 2 treats rectangular matrices while Theorem 1 treats only the case m = n. Secondly, even in the special case Δ = I_{n} of Theorem 2 the size of the subset σ ⊆ {1, …, m} is allowed to be arbitrarily close to srank(A), while in Theorem 1 it can only be taken to be a constant multiple of srank(A). Lastly, Theorem 2 actually allows for the size of the subset σ ⊆ {1, …, m} to be arbitrarily close to the supremum of srank(AΔ) over all positive definite diagonal operators Δ : ℝ^{m} → ℝ^{m}, a quantity that could be much larger than srank(A).

Remark 3. Theorem 2 is often stated in the literature as a subset selection principle for John decompositions of the identity. Namely, suppose that k, m, n ∈ ℕ and x_{1}, …, x_{m} ∈ ℝ^{n} ∖{0} satisfy ∑_{j=1}^{m}⟨x_{j}, y⟩^{2} = ∥y∥_{2}^{2} for all y ∈ ℝ^{n}. Equivalently, we have ∑_{j=1}^{m} x_{j} ⊗ x_{j} = I_{n}, where for x, y ∈ ℝ^{n} the rank-one operator x ⊗ y : ℝ^{n} → ℝ^{n} is defined as usual by setting (x ⊗ y)(z) = ⟨x, z⟩y for every z ∈ ℝ^{n}. Suppose that T : ℝ^{n} → ℝ^{n} is a linear operator satisfying T x_{1}, …, T x_{m} ≠ 0, and that k = (1 − ε)srank(T) for some ε ∈ (0, 1). Then there exists σ ⊆ {1, …, m} with |σ| = k such that

∀ \{a_{j}\}_{j∈σ} ⊆ ℝ,  ∥ ∑_{j∈σ} \frac{a_{j}}{∥T x_{j}∥_{2}} T x_{j}∥_{2} ⩾ ε^{c log(1/ε)}( ∑_{j∈σ} a_{j}^{2})^{\frac{1}{2}} .

The above formulation is equivalent to Theorem 2 as stated in terms of rectangular matrices by considering the operator A : ℝ^{m} → ℝ^{n} that is given by Ae_{j} = T x_{j}/∥T x_{j}∥_{2} for every j ∈ {1, …, m}.

A recent breakthrough of Spielman–Srivastava [SS12], that relies nontrivially on a remarkable method for sparsifying quadratic forms that was developed by Batson–Spielman–Srivastava [BSS12] (see also the survey [Nao12]), yielded the following improved restricted invertibility principle, via techniques that are entirely different from those used by Bourgain–Tzafriri and Vershynin.

Theorem 4 (Spielman–Srivastava). Suppose that k, m, n ∈ ℕ and let A : ℝ^{m} → ℝ^{n} be a linear operator such that k < srank(A). Write k = (1 − ε)srank(A) where ε ∈ (0, 1). Then there exists a subset σ ⊆ {1, …, m} with |σ| = k such that

∥(AJ_{σ})^{−1}∥_{S_{∞}} ⩽ \frac{1}{1 − \sqrt{1 − ε}} · \frac{\sqrt{m}}{∥A∥_{S_{2}}} ⩽ \frac{2\sqrt{m}}{ε∥A∥_{S_{2}}} .

In the setting of Theorem 4, since ∥A∥_{S_{2}} = \sqrt{m} when the columns of A have unit Euclidean norm, Theorem 1 is a special case of Theorem 4. As in the case Δ = I_{n} of Theorem 2, the statement of Theorem 4 has the additional feature that the subset σ ⊆ {1, …, m} can have size arbitrarily close to srank(A). Moreover, in Theorem 4 the columns of A need not have unit Euclidean norm, and the upper bound on ∥(AJ_{σ})^{−1}∥_{S_{∞}} in terms of ε is much better in Theorem 4 than the corresponding bound in the case Δ = I_{n} of Theorem 2; in fact this bound is asymptotically sharp [BHKW88] as ε → 0. An additional feature of Theorem 4 is that its proof in [SS12] yields a deterministic polynomial time algorithm for finding the subset σ, while previous to [SS12] only a randomized polynomial time algorithm was available [Tro09]. Theorem 2 does have a feature that Theorem 4 does not, namely the size of the subset σ ⊆ {1, …, m} can be taken to be arbitrarily close to the supremum of srank(AΔ) over all positive definite diagonal operators Δ : ℝ^{m} → ℝ^{m}, albeit with worse dependence on ε. However, in [You14] it was shown how to combine the features of Theorem 2 and Theorem 4 so as to yield this stronger guarantee with the better dependence on ε that is asserted in Theorem 4. This improvement is important for certain geometric applications [You14]. The new results that are presented below have this stronger “weighted” feature, but for the sake of simplicity of the initial discussion in the Introduction we shall first present all the ensuing statements in their “unweighted” form that corresponds to the way Theorem 4 is stated above.

A different proof of Theorem 4 in the special case AA^{∗} = I_{n} was found by Marcus, Spielman and Srivastava in [MSS14], using their powerful method of interlacing polynomials [MSS15a, MSS15b]. In fact, their forthcoming work [MSS16] obtains Theorem 5 below, which yields for the first time a restricted invertibility principle for subsets that can be asymptotically larger than the stable rank, with their size depending on the ratio of the Hilbert–Schmidt norm and the Schatten–von Neumann 4 norm. This result was announced by Srivastava in his talk at the conference Banach Spaces: Geometry and Analysis (Hebrew University, May 2013), and it is actually a precursor to the outstanding subsequent work [MSS15b]. Its proof will appear for the first time in the forthcoming preprint [MSS16], but we confirmed with the authors that they obtain Theorem 5 as stated below.

Theorem 5 (Marcus–Spielman–Srivastava). Suppose that k, m, n ∈ ℕ and let A : ℝ^{m} → ℝ^{n} be a linear operator such that k < \frac{1}{4}(∥A∥_{S_{2}}/∥A∥_{S_{4}})^{4}. Define ε ∈ (3/4, 1) by k = (1 − ε)∥A∥_{S_{2}}^{4}/∥A∥_{S_{4}}^{4}. Then there exists a subset σ ⊆ {1, …, m} with |σ| = k such that

∥(AJ_{σ})^{−1}∥_{S_{∞}} ⩽ \frac{1}{\sqrt{1 − 2\sqrt{1 − ε}}} · \frac{\sqrt{m}}{∥A∥_{S_{2}}} .  (1)

Theorem 5 can be much better than the previously known restricted invertibility principles at detecting large well-invertible sub-matrices. To state a concrete example, suppose that the singular values of A are s_{1}(A) ≍ \sqrt[4]{m} and s_{2}(A) ≍ s_{3}(A) ≍ … ≍ s_{m}(A) = 1. Then Theorem 4 yields a subset σ ⊆ \{1, …, m\} of size of order \sqrt{m} for which the operator norm of the inverse of AJ_{σ} is O(1), while Theorem 5 yields such a subset whose size is at least a constant multiple of m.

The restriction k < \frac{1}{4}(∥A∥_{S_{2}}/∥A∥_{S_{4}})^{4} in Theorem 5 ensures that ε > 3/4, so that the quantity appearing under the square root in (1) is positive. Thus, in the statement of Theorem 5 k cannot be arbitrarily close to the “modified stable rank” ∥A∥_{S_{2}}^{4}/∥A∥_{S_{4}}^{4}, but this will be remedied below.

It is important to note that the quantity ∥A∥_{S_{2}}^{4}/∥A∥_{S_{4}}^{4} is always at least srank(A). More generally, given p ∈ (2, ∞], if we define the p-stable rank of A to be the quantity

srank_{p}(A) =^{def} (\frac{∥A∥_{S_{2}}}{∥A∥_{S_{p}}} )^{\frac{2p}{p−2}} ,  (2)

then in particular srank_{4}(A) = ∥A∥_{S_{2}}^{4}/∥A∥_{S_{4}}^{4} and srank_{∞}(A) = srank(A). We claim that

p ⩾ q > 2 ⟹ srank_{p}(A) ⩽ srank_{q}(A),  (3)

Indeed, by direct application of Hölder’s inequality we have

∥A∥_{S_{q}} ⩽ ∥A∥S_{2}^{\frac{2(p−q)}{q(p−2)}} · ∥A∥S_{p}^{\frac{p(q−2)}{q(p−2)}} ,

which simplifies to give (3). The limit as p → 2^{+} of srank_{p}(A) can be computed explicitly, yielding the quantity below, denoted Entrank(A), which we naturally call the entropic stable rank of A.

Entrank(A) =^{def} lim_{p→2^{+}} srank_{p}(A) = exp ( log ∑_{j=1}^{m} s_{j}(A)^{2} − \frac{2 ∑_{j=1}^{m} s_{j}(A)^{2} log s_{j}(A)}{∑_{j=1}^{m} s_{j}(A)^{2}})

= exp (\frac{Tr(A^{∗}A) log Tr(A^{∗}A) − Tr(A^{∗}A log(A^{∗}A))}{Tr(A^{∗}A)}) = ∥A∥_{S_{2}}^{2} ∏_{j=1}^{m} s_{j}(A)^{− \frac{2s_{j} (A)^{2}}{∥A∥{2 \atop S_{2}}}} .

As we shall explain in the next section, here we obtain an improved restricted invertibility theorem that in particular yields a strengthening of Theorem 5 that allows one to make use of the p-stable rank of A for every p > 2, thus producing well-invertible sub-matrices of A of size that can be any integer that is less than the entropic stable rank of A.

1.1. Restricted invertibility in terms of rank. Our main new result is the following theorem.

Theorem 6. Suppose that k, m, n ∈ ℕ. Let A : ℝ^{m} → ℝ^{n} be a linear operator with rank(A) > k. Then there exists a subset σ ⊆ {1, …, m} with |σ| = k such that

∥(AJ_{σ})^{−1}∥_{S_{∞}} ≲ min_{r∈\{k+1,...,rank(A)\}} \sqrt{\frac{mr}{(r − k) ∑_{i=r}^{m} s_{i}(A)^{2}}} .  (4)

Example 7. To illustrate the relation between Theorem 4, Theorem 5 and Theorem 6, consider a linear operator A : ℝ^{m} → ℝ^{n} with s_{j}(A) ≍ 1/\sqrt{j} for every j ∈ \{1, …, m\}. Thus rank(A) = m, srank(A) ≍ log m and srank_{4}(m) ≍ (log m)^{2}. Since \sqrt{m}/∥A∥_{S_{2}} ≍ \sqrt{m/ log m}, Theorem 4 yields σ ⊆ \{1, …, m\} with |σ| ≍ log m and ∥(AJ_{σ})^{−1}∥_{S_{∞}} ≲ \sqrt{m/ log m}, Theorem 5 yields such a subset with |σ| ≍ (log m)^{2}, and Theorem 6 yields such a subset with |σ| ≳ \sqrt{m}. In fact, for every ε ∈ (0, 1), Theorem 6 yields σ ⊆ \{1, …, m\} with |σ| ≳ m^{1−ε} such that ∥(AJ_{σ})^{−1}∥_{S_{∞}} ≲ \frac{1}{\sqrt{ε}} \sqrt{m/ log m}.

Theorem 6 has the feature that it asserts the existence of a coordinate subspace of dimension arbitrarily close to the rank of the given operator on which it is invertible, with quantitative control on the operator norm of the inverse. The rank is not a stable quantity, but it is simple to deduce stable consequences of Theorem 6 that are stronger than Theorem 5. Indeed, continuing with the notation of Theorem 6, for every p ∈ (2, ∞) we can apply Hölder’s inequality to deduce that

∥A∥_{S_{2}}^{2} = ∑_{i=1}^{r−1} s_{i}(A)^{2} + ∑_{i=r}^{m} s_{i}(A)^{2}

⩽ (r − 1)^{1− \frac{2}{p}} ( ∑_{i=1}^{r−1} s_{i}(A)^{p})^{\frac{2}{p}} + ∑_{i=r}^{m} s_{i}(A)^{2} ⩽ (r − 1)^{1− \frac{2}{p}} ∥A∥_{S_{p}}^{2} + ∑_{i=r}^{m} s_{i}(A)^{2}.

Hence,

∑_{i=r}^{m} s_{i}(A)^{2} ⩾ ∥A∥_{S_{2}}^{2} − (r − 1)^{1− \frac{2}{p}} ∥A∥_{S_{p}}^{2} =^{(2)} ∥A∥_{S_{2}}^{2} (1 − (\frac{r − 1}{srank_{p}(A)})^{1− \frac{2}{p}} ) .  (5)

A substitution of (5) into (4) yields the following estimate.

s_{min}(AJ_{σ})^{2} ≳ max_{r∈\{k+1,...,srank_{p}(A)\}} (1 − \frac{k}{r} ) (1 − (\frac{r − 1}{srank_{p}(A)})^{1− \frac{2}{p}} ) · \frac{∥A∥_{S_{2}}^{2}}{m} .  (6)

The estimate (6) is nontrivial only when k < srank_{p}(A), so write k = (1 − ε)srank_{p}(A) for some ε ∈ (0, 1). One checks that the following choice of r ∈ {k + 1, …, srank_{p}(A)} attains the maximum in the right hand side of (6), up to universal constant factors. If ε is bounded away from 1, say ε ∈ (0, 1/2], choose r ≍ (1 − ε/2)srank_{p}(A). If 1/2 < ε ⩽ 1 − e^{−p/(p−2)} then choose r ≍ log(1/(1 − ε)) · srank_{p}(A). If 1 − e^{−p/(p−2)} < ε < 1 then choose r ≍ e^{−p/(p−2)}srank_{p}(A). Thus,

0 < ε ⩽ \frac{1}{2} ⟹ ∥(AJ_{σ})^{−1}∥_{S_{∞}} ≲ \sqrt{\frac{p}{p − 2}} · \frac{\sqrt{m}}{ε∥A∥_{S_{2}}} ,
\frac{1}{2} < ε ⩽ 1 − e^{− \frac{p}{p−2}} ⟹ ∥(AJ_{σ})^{−1}∥_{S_{∞}} ≲ \sqrt{\frac{p}{p − 2}} · \frac{\sqrt{m}}{log (1/(1 − ε)) ∥A∥_{S_{2}}} ,
1 − e^{− \frac{p}{p−2}} < ε < 1 ⟹ ∥(AJ_{σ})^{−1}∥_{S_{∞}} ≲ \frac{\sqrt{m}}{∥A∥_{S_{2}}} .

A more concise way to write these estimates is as follows.

∥(AJ_{σ})^{−1}∥_{S_{∞}} ≲ (1 + \frac{p}{(p − 2)| log (1 − ε^{2}) |})^{\frac{1}{2}} \frac{\sqrt{m}}{∥A∥_{S_{2}}} .

For ease of future reference, we record the above corollary of Theorem 6 as Theorem 8 below.

Theorem 8 (Restricted invertibility in terms of Schatten–von Neumann norms). Suppose that k, m, n ∈ ℕ, ε ∈ (0, 1) and p ∈ (2, ∞). Let A : ℝ^{m} → ℝ^{n} be a linear operator that satisfies k ⩽ (1 − ε)srank_{p}(A). Then there exists a subset σ ⊆ {1, …, m} with |σ| = k such that

∥(AJ_{σ})^{−1}∥_{S_{∞}} ≲ (1 + \frac{p}{(p − 2)| log (1 − ε^{2}) |})^{\frac{1}{2}} \frac{\sqrt{m}}{∥A∥_{S_{2}}} .

Equivalently, if k < Entrank(A) then there exists σ ⊆ {1, …, m} with |σ| = k such that

∥(AJ_{σ})^{−1}∥_{S_{∞}} ≲ inf_{p>2} ψ_{p}(1 − \frac{k}{srank_{p}(A)}) \frac{\sqrt{m}}{∥A∥_{S_{2}}} ,

where ψ_{p} : ℝ → [0, ∞] is defined by ψ_{p}(ε) = ∞ if ε ⩽ 0, ψ_{p}(x) = (\sqrt{p/(p − 2)})/ε if 0 < ε < 1/2, ψ_{p}(ε) = (\sqrt{p/(p − 2)})/ log(1/(1 − ε)) if 1/2 < ε ⩽ 1 − e^{−p/(p−2)} and ψ_{p}(ε) = 1 if ε > 1 − e^{−p/(p−2)}.

The case p = 4 of Theorem 8 implies (up to constant factors) the conclusion of Theorem 5, though now treating any ε ∈ (0, 1), i.e., k arbitrarily close to srank_{4}(A), while Theorem 5 applies only when ε > 3/4. Theorem 8 can detect the well-invertibility of A on coordinate subspaces that are much larger than those detected by Theorem 5. For example suppose that the singular values of A are s_{1}(A) ≍ \sqrt[3]{m} and s_{2}(A) ≍ s_{3}(A) ≍ … ≍ s_{m}(A) ≍ 1. Then Theorem 5 yields a subset σ ⊆ {1, …, m} of size of order m^{2/3} for which the operator norm of the inverse of AJ_{σ} is O(1), while (the case p = 3 of) Theorem 8 yields such a subset whose size is proportional to m.

We shall prove Theorem 6 through an application of Theorem 9 below, which is a restricted invertibility statement of independent interest, in combination with a volumetric argument that leads to Lemma 10 below. Throughout what follows, given n ∈ ℕ and a linear subspace F ⊆ ℝ^{n}, we shall denote the orthogonal projection from ℝ^{n} onto F by Proj_{F} : ℝ^{n} → F.

Theorem 9. Fix k, m, n ∈ ℕ and a linear operator A : ℝ^{m} → ℝ^{n} satisfying rank(A) > k. Let ω ⊆ {1, …, m} be any subset with |ω| = rank(A) such that the vectors {Ae_{i}}_{i∈ω} ⊆ ℝ^{n} are linearly independent. For every j ∈ ω let F_{j} ⊆ ℝ^{n} be the orthogonal complement of the span of {Ae_{i}}_{i∈ω∖{j}} ⊆ ℝ^{n}, i.e.,

F_{j} =^{def} (span {Ae_{i}}_{i∈ω∖{j}})^{⊥} .  (7)

Then there exists a subset σ ⊆ ω with |σ| = k such that

∥(AJ_{σ})^{−1}∥_{S_{∞}} ≲ \sqrt{rank(A)} ; \sqrt{rank(A) − k} · max_{j∈ω} \frac{1}{∥Proj_{F_{j}}Ae_{j}∥_{2}} .  (8)

The link between Theorem 9 and Theorem 6 is furnished through the following lemma.

Lemma 10. Fix r, m, n ∈ ℕ. Let A : ℝ^{m} → ℝ^{n} be a linear operator with rank(A) ⩾ r. For every τ ⊆ {1, …, m} let E_{τ} ⊆ ℝ^{n} be the orthogonal complement of the span of {Ae_{j}}_{j∈τ} ⊆ ℝ^{n}, i.e.,^{1}

E_{τ} =^{def} (span {Ae_{j}}_{j∈τ} )^{⊥} .  (9)

Then there exists a subset τ ⊆ {1, …, m} with |τ| = r such that

∀ j ∈ τ,  ∥Proj_{E_{τ∖\{j\}}}Ae_{j}∥_{2} ⩾ \frac{1}{\sqrt{m}}( ∑_{i=r}^{m} s_{i}(A)^{2})^{\frac{1}{2}} .  (10)

The deduction of Theorem 6 from Theorem 9 and Lemma 10 is simple. Indeed, in the setting of Theorem 6, take r ∈ {k + 1, …, rank(A)} and apply Lemma 10 to obtain a subset τ ⊆ {1, …, m} with |τ| = r that satisfies (10). This implies in particular that {Ae_{j}}_{j∈τ} are linearly independent, hence the operator AJ_{τ} : ℝ^{τ} → ℝ^{n} has rank r. By Theorem 9 applied with A replaced by AJ_{τ}, m = r = rank(A) and ω = τ, we obtain a further subset σ ⊆ τ with |σ| = k such that

∥(AJ_{σ})^{−1}∥_{S_{∞}} ≲^{(8)∧(10)} \sqrt{\frac{mr}{(r − k) ∑_{i=r}^{m} s_{i}(A)^{2}}} .

This is precisely the assertion of Theorem 6.

In Section 5 we shall prove the following variant of Theorem 9.

1Comparing (7) and (9) we see that F_{j} = E_{ω∖{j}} for every j ∈ ω.

Theorem 11. Fix k, m, n ∈ ℕ and a linear operator A : ℝ^{m} → ℝ^{n} satisfying rank(A) > k. Then there exists a subset σ ⊆ {1, …, m} with |σ| = k such that

∥(AJ_{σ})^{−1}∥_{S_{∞}} ⩽ \frac{\sqrt{m}}{\sqrt{rank(A)} − \sqrt{k}} (\frac{1}{rank(A)} ∑_{i=1}^{rank(A)} \frac{1}{s_{i}(A)^{2}} )^{\frac{1}{2}} .  (11)

To explain how Theorem 11 relates to Theorem 6, note that in the setting of Theorem 6 we have

∑_{j∈ω} \frac{1}{∥Proj_{F_{j}}Ae_{j}∥_{2}^{2}} = ∑_{i=1}^{rank(A)} \frac{1}{s_{i}(AJ_{ω})^{2}} .  (12)

The simple linear-algebraic justification of (12) appears in Section 2.1 below. For simplicity suppose that ω = {1, …, m}, so rank(A) = m, and write k = (1−ε)m for some ε ∈ (0, 1). Then Theorem 6 yields a subset σ ⊆ {1, …, m} with |σ| = k such that

∥(AJ_{σ})^{−1}∥_{S_{∞}} ≲ \frac{1}{\sqrt{ε}} · max_{j∈\{1,...,m\}} \frac{1}{∥Proj_{F_{j}}Ae_{j}∥_{2}} ,  (13)

while, due to (12), Theorem 11 yields a subset σ ⊆ {1, …, m} with |σ| = k such that

∥(AJ_{σ})^{−1}∥_{S_{∞}} ⩽ \frac{1}{1 − \sqrt{1 − ε}}(\frac{1}{m} ∑_{i=1}^{m} \frac{1}{∥Proj_{F_{j}}Ae_{j}∥_{2}^{2}} )^{\frac{1}{2}} ≍ \frac{1}{ε}(\frac{1}{m} ∑_{i=1}^{m} \frac{1}{∥Proj_{F_{j}}Ae_{j}∥_{2}^{2}} )^{\frac{1}{2}} .  (14)

The estimates (13) and (14) are incomparable since (13) yields a dependence on ε that is better than that of (14) as ε → 0, while the bound in (14) is in terms of the average of the quantities {1/∥Proj_{F_{j}}Ae_{j}∥_{2}^{2}}_{j=1}^{m} rather than their maximum. It remains an interesting open question whether one could obtain a restricted invertibility theorem that combines the best terms in (13) and (14).

Remark 12. Theorem 9 is best possible, up to constant factors. Indeed, fix k, m ∈ ℕ with k < m and let B be the m by m matrix all of whose diagonal entries equal m and all of whose off-diagonal entries equal −1. Then B is positive definite (diagonal-dominant) and we choose A = \sqrt{B}. We are thus in the setting of Theorem 9 with m = n = rank(A) and ω = {1, …, m}. The quantity 1/∥Proj_{F_{j}}Ae_{j}∥_{2}^{2} is equal to the j’th diagonal entry of (A^{∗}A)^{−1} = B^{−1}; see equation (16) in Section 2.1 below for a simple justification of this fact. The matrix B is an invertible circulant matrix, and as such B^{−1} is also a circulant matrix whose diagonal entries equal 2/(m + 1); see [Dav79, KS12] for more on the explicit evaluation of basic quantities related to circulant matrices, including their inverses and eigenvalues, which we use here. Therefore 1/∥Proj_{F_{j}}Ae_{j}∥_{2} = \sqrt{2/(m + 1)} for every j ∈ \{1, …, m\}, so that the right hand side of (8) equals \sqrt{2m/((m + 1)(m − k))} ≍ 1/\sqrt{m − k}. At the same time, take any σ ⊆ {1, …, m} with |σ| = k. Then (AJ_{σ})^{∗}(AJ_{σ}) = J_{σ}^{∗}BJ_{σ} corresponds to a k by k matrix whose diagonal entries equal m and whose off-diagonal entries equal −1. This is again a circulant matrix whose eigenvalues equal to m+1 with multiplicity k−1 and m+1−k with multiplicity 1. Thus s_{1}(AJ_{σ}) = … = s_{k−1}(AJ_{σ}) = \sqrt{m + 1} and s_{k}(AJ_{σ}) = s_{min}(AJ_{σ}) = 1/∥(AJ_{σ})^{−1}∥_{S_{∞}} = \sqrt{m + 1 − k}. This shows that ∥(AJ_{σ})^{−1}∥_{S_{∞}} ≍ 1/\sqrt{m − k}, so that (8) is sharp up to constant factors.

1.2. Remarks on the proofs. The original proof of Bourgain and Tzafriri of Theorem 1 consists of a beautiful combination of probabilistic, combinatorial and analytic arguments. It proceeds roughly along three steps. Firstly, using random selectors one finds a large collection of columns of A that is “well separated.” In the second step one uses the Sauer–Shelah lemma [Sau72, She72] to find a further subset of the columns such that the inverse of the restriction of A to this subset, when viewed as an operator from ℓ_{2} to ℓ_{1}, has small norm; the Sauer–Shelah lemma is discussed in Section 2.4 below, since it plays an important role here as well. The third step of the Bourgain–Tzafriri proof uses tools from functional analysis, specifically the Little Grothendieck’s Inequality [Gro53] and the Pietsch Domination Theorem [Pie67], to control the desired Hilbertian operator norm; these analytic tools are used here as well, and are explained in detail in Section 2.2 and Section 2.3 below.

Vershynin’s proof of Theorem 2 uses the Bourgain–Tzafriri restricted invertibility theorem as a “black box,” alongside with (unpublished) work of Kashin and Tzafriri (see Theorem 2.5 in [Ver01]). A key contribution of Verhynin was the idea to work with the Hilbert–Schmidt norm so as to allow for an iterative argument. As we stated earlier, the proof of Spielman and Srivastava of Theorem 4 is entirely different from the previously used methods in this context, relying on the ‘sparsification method’ of Batson–Spielman–Srivastava [BSS12]. This refreshing approach led to many important developments, and it was subsequently augmented by the powerful ‘method of interlacing polynomials’ of Marcus–Spielman–Srivastava, which they used to prove Theorem 5, showing that one could use higher Schatten–von Neumann norms to address the restricted invertibility problem.

Our starting point here was the realization that one could use ideas and techniques that predate the works of Vershynin, Spielman–Srivastava and Marcus–Spielman–Srivastava to obtain asymptotically sharp results such as Theorem 4, and even to strengthen the statement in terms of higher Schatten–von Neumann norms that is contained in Theorem 5. These later results were based on the discovery of powerful new techniques, leading to many additional applications (crowned by the solution of the Kadison–Singer problem [MSS15b]) that are not covered here, but the present work shows how to apply classical methods to improve over the best known bounds on the restricted invertibility problem. Specifically, we rely on the beautiful work of Giannopoulos [Gia96], which treats a seemingly unrelated geometric question (see also [Gia95]), though it is partially inspired by the work of Bourgain–Tzafriri [BT87] itself, as well as the works of Bourgain–Szarek [BS88] and Szarek–Talagrand [ST89] (see also [Sza91]). The key step is to use Giannopoulos’ clever iterative application of the Sauer–Shelah lemma (Bourgain–Tzafriri used the Sauer–Shelah lemma only once in their original argument) in the proof of Theorem 9. In fact, one could use a geometric statement of Giannopoulos [Gia96] as a “black box” so as to obtain a shorter proof of Theorem 9; this is carried out in Section 4.1 below, but only after we present a self-contained argument in Section 4.

Theorem 11 is of a different nature, since its proof uses the Marcus–Spielman–Srivastava method of interlacing polynomials. We do not see how to prove it using the classical analytic techniques that are utilized elsewhere in this article, and in fact we do not need it for the applications that are obtained here (as we explained earlier, Theorem 11 is incomparable to Theorem 9, being weaker in terms of the dependence on certain parameters and stronger in other respects). Nevertheless, Theorem 11 certainly belongs to the family of restricted invertibility results that we study here.

Among the interesting questions that arise naturally from the present work, we ask whether Theorem 6, Theorem 8, Theorem 9 and Theorem 11 can be made to be algorithmic. Our current proofs do not yield a polynomial time algorithm that finds the desired coordinate subspace, due to various reasons, including (but not limited to) the use of the Sauer–Shelah lemma (in Theorem 6, Theorem 8 and Theorem 9) and the use of the method of interlacing polynomials (in Theorem 11).

1.3. Roadmap. While this article is primarily devoted to new results, it also has an expository component due to the fact that we are using tools and ideas from diverse fields, with which some readers may not be familiar. Being very much inspired by Matoušek’s exceptionally clear style of mathematical exposition, we also made an effort for the ensuing arguments to be self-contained by including quick explanations of classical results that are being used. It seems impossible to fully achieve a Matoušek-style exposition, but hopefully his influence helped us to make an important area of mathematics and a collection of powerful and versatile tools accessible to a wider audience.

Section 2 describes auxiliary statements that will be used in the subsequent proofs. These include classical results of major importance to several fields, and we include brief deductions of what we need so as to make this article self-contained. Section 3 contains the proof of Lemma 10. A selfcontained proof of Theorem 6, using a clever iterative procedure of Giannopoulus [Gia96], appears in Section 4. This is followed by Section 4.1, where it is shown that Theorem 6 is equivalent to a geometric theorem of Giannopulos [Gia96], thus yielding a shorter (but not self-contained) proof of Theorem 6. Section 5 contains the proof of Theorem 11.

Acknowledgements. We thank Bill Johnson for helpful discussions. This work was initiated while we were participating in the workshop Beyond Kadison–Singer: paving and consequences at the American Institute of Mathematics. We thank the organizers for the excellent working conditions.

2. Preliminaries

In this section we shall describe several tools that will be used in the ensuing arguments, and derive certain corollaries of them in forms that will be easy to quote as the need arises later.

2.1. A bit of linear algebra. We shall start with elementary linear algebraic reasoning that clarifies the meaning of some of the quantities that were discussed in the Introduction. In particular, we shall see why the identity (12) holds true.

We work here in the setting of Theorem 9, namely we are given k, m, n ∈ ℕ and a linear operator A : ℝ^{m} → ℝ^{n} satisfying rank(A) > k. We are also fixing any subset ω ⊆ {1, …, m} with |ω| = rank(A) such that the vectors {Ae_{i}}_{i∈ω} ⊆ ℝ^{n} are linearly independent. For j ∈ ω we consider the linear subspace F_{j} ⊆ ℝ^{n} that is defined in (7), namely F_{j} is the orthogonal complement of the span of {Ae_{i}}_{i∈ω∖{j}} ⊆ ℝ^{n}. For every j ∈ ω define a vector v_{j} ∈ ℝ^{n} as follows.

v_{j} =^{def} \frac{Proj_{F_{j}}Ae_{j}}{∥Proj_{F_{j}}Ae_{j}∥_{2}^{2}} ∈ ℝ^{n}.  (15)

For every j ∈ ω, since I_{n} − Proj_{F_{j}} is the orthogonal projection onto span({Ae_{i}}_{i∈ω∖{j}}) ⊆ ℝ^{n}, we know that I_{n} − Proj_{F_{j}}Ae_{j} ∈ span({Ae_{i}}_{i∈ω∖{j}}). So, {Proj_{F_{j}}Ae_{j}}_{j∈ω} ⊆ span({Ae_{i}}_{i∈ω}), and therefore {v_{j}}_{j∈ω} ⊆ span({Ae_{i}}_{i∈ω}). For j ∈ ω we have ⟨Proj_{F_{j}}Ae_{j}, Ae_{j}⟩ = ∥Proj_{F_{j}}Ae_{j}∥_{2}^{2}, so ⟨v_{j}, Ae_{j}⟩ = 1. Also, because Proj_{F_{j}}Ae_{j} is orthogonal to {Ae_{i}}_{i∈ω∖{j}}, we have ⟨v_{j}, Ae_{i}⟩ = 0 for every i ∈ ω ∖ {j}. Since {Ae_{i}}_{i∈ω} is a basis of span({Ae_{i}}_{i∈ω}) and {v_{j}}_{j∈ω} ⊆ span({Ae_{i}}_{i∈ω}), this means that {v_{j}}_{j∈ω} is the unique dual basis of {Ae_{i}}_{i∈ω} in span({Ae_{i}}_{i∈ω}).

The operator (AJ_{ω})^{∗}(AJ_{ω}) : ℝ^{ω} → ℝ^{ω} has rank |ω| = rank(A), hence it is invertible. For every j ∈ ω we may therefore consider the vector

w_{j} =^{def} (AJ_{ω})((AJ_{ω})^{∗}(AJ_{ω}))^{−1}e_{j} ∈ span({Ae_{i}}_{i∈ω}).

Observe that for every i, j ∈ ω we have

⟨w_{j}, Ae_{i}⟩ = ⟨(AJ_{ω})((AJ_{ω})^{∗}(AJ_{ω}))^{−1}e_{j}, (AJ_{ω})e_{i}⟩

= ⟨(AJ_{ω})^{∗}(AJ_{ω})((AJ_{ω})^{∗}(AJ_{ω}))^{−1}e_{j}, e_{i}⟩ = ⟨e_{j}, e_{i}⟩.

By the uniqueness of the dual basis of {Ae_{i}}_{i∈ω} in span({Ae_{i}}_{i∈ω}), we conclude that v_{j} = w_{j} for every j ∈ ω. This implies in particular that for every j ∈ ω we have

\frac{1}{∥Proj_{F_{j}}Ae_{j}∥_{2}^{2}} = ∥v_{j}∥_{2}^{2} = ⟨w_{j}, w_{j}⟩ = ⟨(AJ_{ω})((AJ_{ω})^{∗}(AJ_{ω}))^{−1}e_{j}, (AJ_{ω})((AJ_{ω})^{∗}(AJ_{ω}))^{−1}e_{j}⟩

= ⟨((AJ_{ω})^{∗}(AJ_{ω}))^{−1}e_{j}, (AJ_{ω})^{∗}(AJ_{ω})((AJ_{ω})^{∗}(AJ_{ω}))^{−1}e_{j}⟩ = ⟨((AJ_{ω})^{∗}(AJ_{ω}))^{−1}e_{j}, e_{j}⟩ . (16)

Consequently,

∑_{j∈ω} \frac{1}{∥Proj_{F_{j}}Ae_{j}∥_{2}^{2}} = ∑_{j∈ω} ⟨((AJ_{ω})^{∗}(AJ_{ω}))^{−1}e_{j}, e_{j}⟩ = Tr (((AJ_{ω})^{∗}(AJ_{ω}))^{−1}) = ∑_{i=1}^{rank(A)} \frac{1}{s_{i}(AJ_{ω})^{2}} .

This is precisely the identity (12). The above discussion, and in particular the auxiliary vectors (15) and their properties that were derived above, will play a role in later arguments as well.

2.2. Grothendieck. We shall use later the following important theorem of Grothendieck [Gro53].

Theorem 13 (Little Grothendieck Inequality). Fix k, m, n ∈ ℕ. Suppose that T : ℝ^{m} → ℝ^{n} is a linear operator. Then for every x_{1}, …, x_{k} ∈ ℝ^{m} there exists i ∈ {1, …, m} such that

∑_{r=1}^{k} ∥T x_{r}∥_{2}^{2} ⩽ \frac{π}{2} ∥T ∥_{ℓ_{∞}^{m}→ℓ_{2}^{n}}^{2} ∑_{r=1}^{k} x_{ri}^{2}.  (17)

Here ∥T ∥_{ℓ_{∞}^{m}→ℓ_{2}^{n}} =^{def} max_{x∈[−1,1]^{m}} ∥T x∥_{2} is the operator norm of T when it is viewed as an operator from ℓ_{∞}^{m} to ℓ_{2}^{n}, and x_{ri} = ⟨x_{r}, e_{i}⟩ is the i’th coordinate of x_{r} ∈ ℝ^{m}.

To see the significance of Theorem 13, note that the definition of the operator norm of T when it is viewed as an operator from ℓ_{∞}^{m} to ℓ_{2}^{n} is nothing more than the smallest C ⩾ 0 such that for every x ∈ ℝ^{m} there exists i ∈ {1, …, m} for which ∥T x∥_{2}^{2} ⩽ C^{2}x_{i}^{2}. So, the case k = 1 of (17) without the factor π/2 in the right hand side is a tautology. Theorem (13) asserts that the case k = 1 of (17) automatically “upgrades” to (17) for general k ∈ ℕ at the cost of a loss of the constant factor π/2.

The literature contains clear expositions of Theorem 13 and its various useful generalizations and equivalent formulations; see e.g. [Pis86, DJT95]. Nevertheless, for the sake of completeness we shall now quickly explain why Theorem 13 holds true, following (a specialization of) the standard proofs of this fact [Pis86, DJT95]. We note that the factor π/2 in (17) is sharp; see e.g. the remark immediately following the proof of Theorem 5.4 in [Pis86].

To prove Theorem 13, by rescaling both T and (x_{1}, …, x_{k}) we may assume without loss of generality that ∥T ∥_{ℓ_{∞}^{m}→ℓ_{2}^{n}} = 1 and ∑_{r=1}^{k} ∥T x_{r}∥_{2}^{2} = 1. With this normalization, we claim that

∑_{j=1}^{m} ( ∑_{r=1}^{k}(T^{∗}T x_{r})_{j}^{2})^{\frac{1}{2}} ⩽ \sqrt{\frac{π}{2}} .  (18)

Once proven, (18) implies the desired estimate (17) via the following application of Cauchy–Schwarz.

1 = ∑_{r=1}^{k} ∥T x_{r}∥_{2}^{2} = ∑_{r=1}^{k}⟨x_{r}, T^{∗}T x_{r}⟩ = ∑_{j=1}^{m} ∑_{r=1}^{k} x_{rj}(T^{∗}T x_{r})_{j} ⩽ ∑_{j=1}^{m} ( ∑_{r=1}^{k} x_{rj}^{2})^{\frac{1}{2}} ( ∑_{r=1}^{k}(T^{∗}T x_{r})_{j}^{2})^{\frac{1}{2}}

⩽ max_{i∈\{1,...,m\}} ( ∑_{r=1}^{k} x_{ri}^{2})^{\frac{1}{2}} ∑_{j=1}^{m} ( ∑_{r=1}^{k}(T^{∗}T x_{r})_{j}^{2})^{\frac{1}{2}} ⩽^{(18)} \sqrt{\frac{π}{2}} · max_{i∈\{1,...,m\}} ( ∑_{r=1}^{k} x_{ri}^{2})^{\frac{1}{2}} .

To prove (18), let {g_{r}}_{r=1}^{k} be i.i.d. standard Gaussian random variables. For every j ∈ {1, …, m} the random variable ∑_{r=1}^{k} g_{r}(T^{∗}T x_{r})_{j} is Gaussian with mean 0 and variance ∑_{r=1}^{k}(T^{∗}T x_{r})_{j}^{2}. So,

𝔼[ ∑_{j=1}^{m} |(T^{∗} ∑_{r=1}^{k} g_{r}T x_{r})_{j}|] = 𝔼[ ∑_{j=1}^{m} | ∑_{r=1}^{k} g_{r}(T^{∗}T x_{r})_{j}|] = ∑_{j=1}^{m} 𝔼[| ∑_{r=1}^{k} g_{r}(T^{∗}T x_{r})_{j}|]

= 𝔼[|g_{1}|] ∑_{j=1}^{m} ( ∑_{r=1}^{k}(T^{∗}T x_{r})_{j}^{2})^{\frac{1}{2}} = \sqrt{\frac{2}{π}} ∑_{j=1}^{m} ( ∑_{r=1}^{k}(T^{∗}T x_{r})_{j}^{2})^{\frac{1}{2}} . (19)

Let z ∈ {−1, 1}^{m} be the random vector given by z_{j} =^{def} sign((T^{∗} ∑_{r=1}^{k} g_{r}T x_{r})_{j}). Then

∑_{j=1}^{m} |(T^{∗} ∑_{r=1}^{k} g_{r}T x_{r})_{j}| = ⟨z, T^{∗} ∑_{r=1}^{k} g_{r}T x_{r}⟩ = ⟨T z, ∑_{r=1}^{k} g_{r}T x_{r}⟩

⩽ ∥T z∥_{2} · ∥ ∑_{r=1}^{k} g_{r}T x_{r}∥_{2} ⩽ ∥T ∥_{ℓ_{∞}^{m}→ℓ_{2}^{n}} · ∥z∥_{∞} · ∥ ∑_{r=1}^{k} g_{r}T x_{r}∥_{2} = ∥ ∑_{r=1}^{k} g_{r}T x_{r}∥_{2}. (20)

By taking expectations in (20) we see that

\sqrt{\frac{2}{π}} ∑_{j=1}^{m} ( ∑_{r=1}^{k}(T^{∗}T x_{r})_{j}^{2})^{\frac{1}{2}} =^{(19)} 𝔼[ ∑_{j=1}^{m} |(T^{∗} ∑_{r=1}^{k} g_{r}T x_{r})_{j}|]

⩽^{(20)} 𝔼[∥ ∑_{r=1}^{k} g_{r}T x_{r}∥_{2}] ⩽ (𝔼[∥ ∑_{r=1}^{k} g_{r}T x_{r}∥_{2}^{2}])^{\frac{1}{2}} = ∑_{r=1}^{k} ∥T x_{r}∥_{2}^{2} = 1,

This is precisely the desired estimate (18), thus completing the proof of Theorem 13. □

2.3. Pietsch. Another classical tool that will be used later (together with the Little Grothendieck Inequality) is the Pietsch Domination Theorem [Pie67].

Theorem 14 (Pietsch Domination). Fix m, n ∈ ℕ and M ∈ (0, ∞). Suppose that T : ℝ^{m} → ℝ^{n} is a linear operator such that for every k ∈ ℕ and x_{1}, …, x_{k} ∈ ℝ^{m} there exists i ∈ {1, …, m} with ∑_{r=1}^{k} ∥T x_{r}∥_{2}^{2} ⩽ M^{2} ∑_{r=1}^{k} x_{ri}^{2}. Then there exist μ_{1}, …, μ_{m} ∈ [0, 1] with ∑_{i=1}^{m} μ_{i} = 1 such that

∀ w = (w_{1}, …, w_{m}) ∈ ℝ^{m}, ∥T w∥_{2}^{2} ⩽ M^{2} ∑_{i=1}^{m} μ_{i}w_{i}^{2}.

Observe in passing that the conclusion of Theorem 14 immediately implies its assumption. Indeed, by applying this conclusion with w = x_{r} for each r ∈ {1, …, k}, and then summing the resulting inequalities over r ∈ {1, …, k}, we get that ∑_{r=1}^{k} ∥T x_{r}∥_{2}^{2} ⩽ ∑_{i=1}^{m} μ_{i}(M^{2} ∑_{r=1}^{k} x_{ri}^{2}), so the existence of the desired index i ∈ {1, …, m} follows from the fact that (μ_{1}, …, μ_{m}) is a probability measure. The main point here is therefore the reverse implication, as stated in Theorem 14.

In Banach space theoretic terminology, the assumption on the operator T in Theorem 14 says that T has 2-summing norm at most M when it is viewed as an operator from ℓ_{∞}^{m} to ℓ_{2}^{n}. We refer to the monographs [TJ89, DJT95] for much more on this topic, as well as proofs of (more general versions of) the Pietsch Domination Theorem. As before, for the sake of completeness we shall now explain why Theorem 14 holds true, following (a specialization of) the standard proofs [TJ89, DJT95] of this fact, which amount to an application of the separation theorem (equivalently, Hahn–Banach or duality of linear programming) to appropriately chosen convex sets.

Let K ⊆ ℝ^{m} be the set of all those vectors y ∈ ℝ^{m} for which there exists k ∈ ℕ and x_{1}, …, x_{k} ∈ ℝ^{m} such that y_{i} = ∑_{r=1}^{k} ∥T x_{r}∥_{2}^{2} − M^{2} ∑_{r=1}^{k} x_{ri}^{2} for every i ∈ {1, …, m}. It is immediate to check that K is convex, and the assumption on T can be restated as saying that K ∩ (0, ∞)^{m} = ∅. By the separation theorem there exist μ = (μ_{1}, …, μ_{m}) ∈ ℝ^{m} such that ∑_{i=1}^{m} μ_{i}y_{i} < ∑_{i=1}^{m} μ_{i}z_{i} for every y ∈ K and z ∈ (0, ∞)^{m}. In particular, μ ≠ 0 and inf_{z∈(0,∞)^{m}}⟨z, μ⟩ > −∞, so necessarily μ_{i} ⩾ 0 for all i ∈ {1, …, m}. We may rescale so that ∑_{i=1}^{m} μ_{i} = 1. If w ∈ ℝ^{m} then (∥T w∥_{2}^{2} − M^{2}w_{i}^{2})_{i=1}^{m} ∈ K, so ∥T w∥_{2}^{2} − M^{2} ∑_{i=1}^{m} μ_{i}w_{i}^{2} = ∑_{i=1}^{m} μ_{i}(∥T w∥_{2}^{2} − M^{2}w_{i}^{2}) ⩽ inf_{z∈(0,∞)^{m}} ∑_{i=1}^{m} μ_{i}z_{i} = 0. □

The following lemma is a combination of the Little Grothendieck Inequality and the Pietsch Domination Theorem; this is how Theorem 13 and Theorem 14 will be used in what follows.

Lemma 15. Fix m, n ∈ ℕ and ε ∈ (0, 1). Let T : ℝ^{n} → ℝ^{m} be a linear operator. Then there exists a subset σ ⊆ {1, …, m} with |σ| ⩾ (1 − ε)m such that

∥Proj_{ℝ^{σ}}T ∥_{S_{∞}} ⩽ \sqrt{\frac{π}{2εm}} · ∥T ∥_{ℓ_{2}^{n}→ℓ_{1}^{m}}.  (21)

Proof. Since we have ∥T^{∗}∥_{ℓ_{∞}^{m}→ℓ_{2}^{n}} = ∥T ∥_{ℓ_{2}^{n}→ℓ_{1}^{m}}, an application of Theorem 13 to T^{∗} : ℝ^{m} → ℝ^{n} shows that the assumption of Theorem 14 holds true with T replaced by T^{∗} and M = \sqrt{π/2} · ∥T ∥_{ℓ_{2}^{n}→ℓ_{1}^{m}}. Hence, Theorem 14 shows that there exists μ ∈ [0, 1]^{m} with ∑_{i=1}^{m} μ_{i} = 1 such that

∀ y ∈ ℝ^{m},  ∥T^{∗}y∥_{2}^{2} ⩽ \frac{π}{2} ∥T ∥_{ℓ_{2}^{n}→ℓ_{1}^{m}}^{2} ∑_{i=1}^{m} μ_{i}y_{i}^{2}.  (22)

Define

σ =^{def} \{i ∈ \{1, …, m\} : μ_{i} ⩽ \frac{1}{mε}\} .  (23)

Since μ is a probability measure on {1, …, m}, by Markov’s inequality we have |σ| ⩾ (1 − ε)m. Take x ∈ ℝ^{n} and choose y ∈ ℝ^{m} such that ∥y∥_{2} = 1 and ∥Proj_{ℝ^{σ}}T x∥_{2} = ⟨y, Proj_{ℝ^{σ}}T x⟩. Then,

∥Proj_{ℝ^{σ}}T x∥_{2}^{2} = ⟨y, Proj_{ℝ^{σ}}T x⟩^{2} = ⟨T^{∗}Proj_{ℝ^{σ}}y, x⟩^{2} ⩽ ∥T^{∗}Proj_{ℝ^{σ}}y∥_{2}^{2} · ∥x∥_{2}^{2}

⩽^{(22)} \frac{π}{2} ∥T ∥_{ℓ_{2}^{n}→ℓ_{1}^{m}}^{2} · ∥x∥_{2}^{2} ∑_{i∈σ} μ_{i}y_{i}^{2} ⩽^{(23)} \frac{π}{2mε}∥T ∥_{ℓ_{2}^{n}→ℓ_{1}^{m}}^{2} · ∥x∥_{2}^{2} · ∥y∥_{2}^{2} = \frac{π}{2mε}∥T ∥_{ℓ_{2}^{n}→ℓ_{1}^{m}}^{2} · ∥x∥_{2}^{2}. (24)

Since (24) holds true for every x ∈ ℝ^{n}, this completes the proof of the desired estimate (21). □

2.4. Sauer–Shelah. The Sauer–Shelah lemma [Sau72, She72] is a fundamental combinatorial principle of wide applicability that will be used crucially later.

Lemma 16 (Sauer–Shelah). Fix m, n ∈ ℕ. Suppose that Ω ⊆ \{−1, 1\}^{n} satisfies |Ω| > ∑_{k=0}^{m−1} \binom{n}{k}. Then there exists a subset σ ⊆ {1, …, n} with |σ| ⩾ m such that Proj_{ℝ^{σ}}Ω = {−1, 1}^{σ}, i.e., for every ε ∈ {−1, 1}^{σ} there exists δ ∈ Ω such that δ_{j} = ε_{j} for every j ∈ σ. In particular, if |Ω| > 2^{n−1} then such a subset σ ⊆ {1, …, n} exists with |σ| ⩾ ⌈(n + 1)/2⌉ ⩾ n/2.

It is simple to prove Lemma 16 by induction on n when one strengthens the inductive hypothesis as follows. Denoting sh(Ω) = {σ ⊆ {1, …, n} : Proj_{ℝ^{σ}}Ω = {−1, 1}^{σ}}, we claim that |sh(Ω)| ⩾ |Ω|; this would imply Lemma 16 since the number of subsets of {1, …, n} of size at most m − 1 equals ∑_{k=0}^{m−1} \binom{n}{k}. This stronger statement is due to Pajor [Paj85], and the resulting very short inductive proof which we shall now sketch for completeness appears as Theorem 1.1 in [ARS02].

The case n = 1 holds trivially (here we use the convention that {−1, 1}^{∅} = ∅ and Proj_{ℝ^{∅}}Ω = ∅). Assuming the validity of the above statement for n, take Ω ⊆ {−1, 1}^{n+1} = {−1, 1}^{n} × {−1, 1} and denote Ω_{1} = {x ∈ {−1, 1}^{n} : (x, 1) ∈ Ω} and Ω_{−1} = {x ∈ {−1, 1}^{n} : (x, −1) ∈ Ω}. Then |Ω_{1}| + |Ω_{−1}| = |Ω| and by the inductive hypothesis we have |sh(Ω_{1})| ⩾ |Ω_{1}| and |sh(Ω_{−1})| ⩾ |Ω_{−1}|. By our definitions we have sh(Ω) ⊇ (sh(Ω_{1}) ∪ sh(Ω_{−1})) ·∪ {σ ∪ {n + 1} : σ ∈ sh(Ω_{1}) ∩ sh(Ω_{−1})}, so |sh(Ω)| ⩾ |sh(Ω_{1})∪sh(Ω_{−1})|+|sh(Ω_{1})∩sh(Ω_{−1})| = |sh(Ω_{1})|+|sh(Ω_{−1})| ⩾ |Ω_{1}|+|Ω_{−1}| = |Ω|. □

2.5. Fan and Hilbert–Schmidt. We record for ease of future use the following lemma that controls the influence of multiplication by an orthogonal projection on the Hilbert–Schmidt norm of a linear operator. Its proof is a simple consequence of the classical Fan Maximum Principle [Fan49], but we couldn’t locate a reference where it is stated explicitly in the form that we will use later.

Lemma 17. Fix m, n ∈ ℕ and r ∈ {1, …, n}. Let A : ℝ^{m} → ℝ^{n} be a linear operator and let P : ℝ^{n} → ℝ^{n} be an orthogonal projection of rank r. Then

∥PA∥_{S_{2}} ⩾ ( ∑_{i=n−r+1}^{m} s_{i}(A)^{2})^{\frac{1}{2}} .

Proof. Since I_{n} − P is an orthogonal projection of rank n − r, by a classical result of Fan [Fan49],

Tr(AA^{∗}(I_{n} − P)) ⩽ ∑_{i=1}^{n−r} s_{i}(AA^{∗}) = ∑_{i=1}^{n−r} s_{i}(A)^{2}  (25)

The proof of (25) is simple; see e.g. [Stø13, Lemma 8.1.8] for a short proof and [Bha97, Chapter III] for more general variational principles along these lines. Now, since P is an orthogonal projection,

∥PA∥_{S_{2}}^{2} = Tr((PA)^{∗}(PA)) = Tr(A^{∗}PA) = Tr(AA^{∗}P) = Tr(AA^{∗}) − Tr(AA^{∗}(I_{n} − P))

= ∑_{i=1}^{m} s_{i}(A)^{2} − Tr(AA^{∗}(I_{n} − P)) ⩾^{(25)} ∑_{i=1}^{m} s_{i}(A)^{2} − ∑_{i=1}^{n−r} s_{i}(A)^{2} = ∑_{i=n−r+1}^{m} s_{i}(A)^{2}. □

3. Proof of Lemma 10

In this section we shall prove Lemma 10 in a more general weighted form that corresponds to the renormalization step in Vershynin’s Theorem, i.e., Theorem 2. Using this weighted version of Lemma 10, one can directly deduce weighted versions of Theorem 6 and Theorem 8 as well, by combining Lemma 18 below with Theorem 9, exactly as we did in the Introduction.

Lemma 18 (weighted version of Lemma 10). Fix r, m, n ∈ ℕ. Let A : ℝ^{m} → ℝ^{n} be a linear operator with rank(A) ⩾ r. For every τ ⊆ {1, …, m} let E_{τ} ⊆ ℝ^{n} be defined as in (9), i.e., it is the orthogonal complement of the span of {Ae_{j}}_{j∈τ} ⊆ ℝ^{n}. Then for every d_{1}, …, d_{m} ∈ (0, ∞) there exists a subset τ ⊆ {1, …, m} with |τ| = r such that

∀ j ∈ τ,  ∥Proj_{E_{τ∖\{j\}}}Ae_{j}∥_{2} ⩾ \frac{d_{j}}{\sqrt{∑_{i=1}^{m} d_{i}^{2}}} ( ∑_{i=r}^{m} s_{i}(A)^{2})^{\frac{1}{2}} .  (26)

Proof. For every τ ⊆ {1, …, m} let K_{τ} ⊆ ℝ^{n} be the convex hull of the vectors {±Ae_{j}/d_{j}}_{j∈τ}, i.e.,

K_{τ} =^{def} conv (\{\frac{1}{d_{j}} Ae_{j} : j ∈ τ\} ∪ \{−\frac{1}{d_{j}} Ae_{j} : j ∈ τ\}) .  (27)

The desired subset τ ⊆ {1, …, m} will be chosen so as to maximize the r-dimensional volume of the convex hull of K_{σ} over all those subsets σ of {1, …, m} of size r. Namely, we shall fix from now on a subset τ ⊆ {1, …, m} with |τ| = r such that

vol_{r}(K_{τ}) = max_{\begin{matrix}σ⊆\{1,...,m\} \\ |σ|=r \end{matrix}} vol_{r}(K_{σ}).  (28)

Take any β ⊆ {1, …, m} with |β| = r − 1 and fix i ∈ {1, …, m} ∖ β. Then by the definition (27) we have K_{β∪{i}} = conv({±Ae_{i}/d_{i}} ∪ K_{β}), i.e., K_{β∪{i}} is the union of the two cones with base K_{β} and apexes at ±Ae_{i}/d_{i}. Recalling (9), note that K_{β} ⊆ span(K_{β}) = E_{β}^{⊥}. Hence, the height of these two cones equals the Euclidean length of the orthogonal projection of Ae_{i}/d_{i} onto E_{β}. Therefore,

vol_{r}(K_{β∪\{i\}}) = \frac{2∥Proj_{E_{β}}Ae_{i}∥_{2}vol_{r−1}(K_{β})}{rd_{i}}.  (29)

Returning to the subset τ that was chosen in (28), we see that if j ∈ τ and i ∈ {1, …, m} then

\frac{2∥Proj_{E_{τ∖\{j\}}}Ae_{j}∥_{2}vol_{r−1}(K_{τ∖\{j\}})}{rd_{j}} =^{(29)} vol_{r}(K_{τ})

⩾^{(28)} vol_{r}(K_{(τ∖\{j\})∪\{i\}}) =^{(29)} \frac{2∥Proj_{E_{τ∖\{j\}}}Ae_{i}∥_{2}vol_{r−1}(K_{τ∖\{j\}})}{rd_{i}}. (30)

Since we are assuming that r ⩽ rank(A), we know that vol_{r}(K_{τ}) > 0. It therefore follows from (30) that also vol_{r−1}(K_{τ∖{j}}) > 0, so me may cancel the quantity 2vol_{r−1}(K_{τ∖{j}}) /r from both sides of (30). Since the resulting estimate holds true for every i ∈ {1, …, m}, we conclude that

∀ j ∈ τ,  \frac{∥Proj_{E_{τ∖\{j\}}}Ae_{j}∥_{2}}{d_{j}} = max_{i∈\{1,...,m\}} \frac{∥Proj_{E_{τ∖\{j\}}}Ae_{i}∥_{2}}{d_{i}} .  (31)

Consequently, for every j ∈ τ we have

\frac{∥Proj_{E_{τ∖\{j\}}}Ae_{j}∥_{2}^{2}}{d_{j}^{2}} ( ∑_{i=1}^{m} d_{i}^{2}) ⩾^{(31)} ∑_{i=1}^{m} ∥Proj_{E_{τ∖\{j\}}}Ae_{i}∥_{2}^{2} = ∥Proj_{E_{τ∖\{j\}}}A∥_{S_{2}}^{2}.

Equivalently,

∀ j ∈ τ,  ∥Proj_{E_{τ∖\{j\}}}Ae_{j}∥_{2} ⩾ \frac{d_{j}}{\sqrt{∑_{i=1}^{m} d_{i}^{2}}} ∥Proj_{E_{τ∖\{j\}}}A∥_{S_{2}}.  (32)

Recalling (9), since |τ| = r we know that dim(E_{τ∖{j}}) = n − (r − 1) for every j ∈ τ. Consequently, Proj_{E_{τ∖{j}}} : ℝ^{n} → ℝ^{n} is an orthogonal projection of rank n − (r − 1), so that the desired inequality (26) follows from (32) and Lemma 17. □

4. Giannopoulos

In this section we shall prove Theorem 9, following the lines of a clever iterative procedure that was devised by Giannopoulos in [Gia96]. Throughout the ensuing discussion, we may assume in the setting of Theorem 9 that ω = {1, …, m}, in which case rank(A) = m. Indeed, there is no loss of generality by doing so because for general ω ⊆ {1, …, m} we could then consider the restricted operator AJ_{ω} : ℝ^{ω} → ℝ^{n} in order to obtain Theorem 9 as stated in the Introduction.

Proof overview. The overall strategy of the ensuing proof can be explained in broad strokes given the tools that were already presented in Section 2. The ultimate goal of Theorem 9 is to obtain an upper bound on the operator norm ∥·∥_{S_{∞}} of a certain m by n matrix (the inverse of an appropriate coordinate restriction of the given n by m matrix A), while we have already seen in Lemma 15 that if one does not mind composing with a further coordinate projection then such a bound follows automatically from a weaker upper estimate on the operator norm ∥ · ∥_{ℓ_{2}^{n}→ℓ_{1}^{m}}. The latter quantity can be controlled using the Sauer–Shelah lemma due to the following reasoning.

Let {v_{j}}_{j=1}^{m} be the dual basis of {Ae_{j}}_{j=1}^{m} that is given in (15). Consider the subset Ω of the hypercube {−1, 1}^{m} consisting of all those sign vectors ε = (ε_{1}, …, ε_{m}) for which the Euclidean norm ∥ ∑_{j=1}^{m} ε_{j}v_{j}∥_{2} is not too large, with the precise meaning of “not too large” here to be specified in the proof of Lemma 19 below; see (37). The parallelogram identity says that if ε ∈ {−1, 1}^{m} is chosen uniformly at random then the expectation of ∥ ∑_{j=1}^{m} ε_{j}v_{j}∥_{2}^{2} equals ∑_{j=1}^{m} ∥v_{j}∥_{2}^{2}. So, by Markov’s inequality, an appropriate setting of the parameters would yield that the cardinality of Ω is greater than 2^{m−1} = |{−1, 1}^{m}|/2. The Sauer–Shelah lemma would then furnish a coordinate subset β ⊆ {1, …, m} with the property that every sign pattern (ε_{j})_{j∈β} ∈ {−1, 1}^{β} can be completed to a full dimensional sign vector ε ∈ {−1, 1}^{m} such that ∑_{j=1}^{m} ε_{j}v_{j} is “short” in the Euclidean norm.

The above conclusion implies an upper bound on the operator norm of the inverse of the restriction of A to ℝ^{β}, when it is viewed as an operator from ℓ_{2}^{β} to ℓ_{1}^{m}. Indeed, given an arbitrary vector (a_{j})_{j∈β} ∈ ℝ^{β}, the goal is to bound ∑_{j∈β} |a_{j}| in terms of ∥ ∑_{j∈β} a_{j}Ae_{j}∥_{2}. The sign pattern to be considered is then the signs of the coefficients (a_{j})_{j∈β} ∈ ℝ^{β}, i.e., set ε_{j} = sign(a_{j}) for every j ∈ β. The (Sauer–Shelah) subset β ⊆ {1, …, m} was constructed so that this sign vector can be completed to a full dimensional sign vector ε ∈ {−1, 1}^{m} with control on the Euclidean length of ∑_{j=1}^{m} ε_{j}v_{j}. But {v_{j}}_{j=1}^{m} is a dual basis of {Ae_{j}}_{j=1}^{m}, so by the definition of (ε_{j})_{j∈β} the quantity ∑_{j∈β} |a_{j}| is equal to the scalar product of ∑_{j∈β} a_{j}Ae_{j} with the “short” vector ∑_{j=1}^{m} ε_{j}v_{j}. By Cauchy–Schwarz this scalar product is bounded from above by the Euclidean length of ∑_{j∈β} a_{j}Ae_{j} times the Euclidean length of ∑_{j=1}^{m} ε_{j}v_{j}, with the latter quantity being bounded above by design.

By Lemma 15 we can now pass to a further subset of β and compose the resulting inverse matrix with the coordinate projection onto that subset so as to “upgrade” this control on the operator norm from ℓ_{2}^{β} to ℓ_{1}^{m} to a better upper bound on ∥·∥_{S_{∞}}. Complications arise when one examines the above strategy from the quantitative perspective. The Sauer–Shelah lemma can at best produce a coordinate subset of size m/2, while we desire to obtain restricted invertibility on a potentially larger subset. Moreover, in the above procedure the Sauer–Shelah subset is further reduced in size due to the subsequent use of Lemma 15. Since we desire to extract larger coordinate subsets, one can attempt to apply this reasoning iteratively, i.e., start by using the Sauer–Shelah lemma to obtain a coordinate subset, followed by an application of Lemma 15 to pass to a further subset β′ ⊆ {1, …, m}. Now apply the same double selection procedure to {1, …, m}∖β′, thus obtaining a subset β′′ ⊆ {1, …, m} ∖ β′, and iterate this procedure by now considering {1, …, m} ∖ (β′ ∪ β′′) and so forth. To make this strategy work, one needs to formulate a stronger inductive hypothesis so as to allow one to “glue” the local information on the subsets that are extracted in each step of the iteration into global information on their union, while ensuring that the end result is a sufficiently large coordinate subset. This is the reason why the assumptions of Lemma 19 below are more complicated. The technical details that implement the above strategy are explained in the remainder of this section.

Lemma 19. Fix n ∈ ℕ and m ∈ {1, …, n}. Let A : ℝ^{m} → ℝ^{n} be a linear operator such that the vectors {Ae_{j}}_{j=1}^{m} ⊆ ℝ^{n} are linearly independent. Suppose that k ∈ ℕ ∪ {0} and σ ⊆ {1, …, m}. For j ∈ {1, …, m} recall the definition of the subspace F_{j} ⊆ ℝ^{n} in (7) (with ω = {1, …, m}), i.e,

F_{j} = (span {Ae_{i}}_{i∈{1,...,m}∖{j}})^{⊥} .

Then there exists τ ⊆ σ with |τ| ⩾ (1 − 2^{−k})|σ| such that for every ϑ ⊆ {1, …, m} that satisfies ϑ ⊇ τ and every a = (a_{1}, …, a_{m}) ∈ ℝ^{m} there exists an index j ∈ {1, …, m} for which

∑_{i∈τ} |a_{i}| ⩽ \frac{\sqrt{|σ|} ∑_{r=1}^{k} 2^{\frac{r}{2}}}{∥Proj_{F_{j}}Ae_{j}∥_{2}} ∥ ∑_{i∈ϑ} a_{i}Ae_{i}∥_{2} + (2^{k} − 1) ∑_{i∈ϑ∩(σ∖τ)} |a_{i}|.  (33)

Proof. It will be convenient to introduce the following notation.

M =^{def} max_{j∈\{1,...,m\}} \frac{1}{∥Proj_{F_{j}}Ae_{j}∥_{2}}  and  α_{k} =^{def} ∑_{r=1}^{k} 2^{\frac{r}{2}} .  (34)

Throughout we adhere to the convention that an empty sum vanishes, thus in particular α_{0} = 0.

Under the notation (34), our goal becomes to show that there exists τ ⊆ σ with |τ| ⩾ (1−2^{−k})|σ| such that for every ϑ ⊆ {1, …, m} that satisfies ϑ ⊇ τ and every a ∈ ℝ^{m} we have

∑_{i∈τ} |a_{i}| ⩽ α_{k}M\sqrt{|σ|}∥ ∑_{i∈ϑ} a_{i}Ae_{i}∥_{2} + (2^{k} − 1) ∑_{i∈ϑ∩(σ∖τ)} |a_{i}|.  (35)

We shall prove this statement by induction on k. The case k = 0 holds vacuously by taking τ = ∅. Assuming the validity of this statement for k, we shall proceed to deduce its validity for k + 1.

We are given τ ⊆ σ with |τ| ⩾ (1 − 2^{−k})|σ| such that for every ϑ ⊆ {1, …, m} that satisfies ϑ ⊇ τ we know that (35) holds true for every a ∈ ℝ^{m}. Observe that if τ = σ then τ itself would satisfy the required statement for k + 1, so we may assume from now on that σ ∖ τ ≠ ∅.

For every j ∈ {1, …, m} let v_{j} be given as in (15), i.e.,

v_{j} =^{def} \frac{Proj_{F_{j}}Ae_{j}}{∥Proj_{F_{j}}Ae_{j}∥_{2}^{2}} ∈ ℝ^{n}.  (36)

Observe that the denominator in (36) (and also in (33) and (34)) does not vanish since we are assuming in Lemma 19 that {Ae_{j}}_{j=1}^{m} are linearly independent. Define Ω ⊆ {−1, 1}^{σ∖τ} as follows.

Ω =^{def} \{ε ∈ \{−1, 1\}^{σ∖τ} : ∥ ∑_{i∈σ∖τ} ε_{i}v_{i}∥_{2} ⩽ M\sqrt{2|σ ∖ τ|}\}.  (37)

By the parallelogram identity we have

M^{2}|σ ∖ τ| ⩾^{(34)} ∑_{i∈σ∖τ} \frac{1}{∥Proj_{F_{i}}Ae_{i}∥_{2}^{2}} =^{(36)} ∑_{i∈σ∖τ} ∥v_{i}∥_{2}^{2} = \frac{1}{2^{|σ∖τ} |} ∑_{ε∈\{−1,1\}^{σ∖τ}} ∥ ∑_{i∈σ∖τ} ε_{i}v_{i}∥_{2}^{2}

>^{(37)} \frac{1}{2^{|σ∖τ|}} ∑_{ε∉Ω^{ε∈\{−1,1\}^{σ∖τ}}} 2M^{2}|σ ∖ τ| = 2M^{2}|σ ∖ τ| (1 − \frac{|Ω|}{2^{|σ∖τ|}} ) . (38)

Since |σ ∖ τ| > 0, it follows from (38) that |Ω| > 2^{|σ∖τ|−1}.

We can now apply the Sauer–Shelah lemma, i.e., Lemma 16, thus deducing that there exists a subset β ⊆ σ ∖ τ with |β| ⩾ |σ ∖ τ|/2 such that Proj_{ℝ^{β}}Ω = {−1, 1}^{β}. Defining τ^{∗} = τ ∪ β we shall now proceed to show that τ^{∗} satisfies the inductive hypothesis with k replaced by k + 1.

Since β ∩ τ = ∅, τ ⊆ σ and |β| ⩾ |σ ∖ τ|/2 we have

|τ^{∗}| = |τ| + |β| ⩾ |τ| + \frac{|σ| − |τ|}{2} = \frac{|τ| + |σ|}{2} ⩾ \frac{(1 − 2^{−k})|σ| + |σ|}{2} = (1 − 2^{−k−1})|σ|.  (39)

Next, suppose that ϑ ⊆ {1, …, m} satisfies ϑ ⊇ τ^{∗}. If a ∈ ℝ^{m} then because Proj_{ℝ^{β}}Ω = {−1, 1}^{β} there exists ε ∈ Ω such that for every j ∈ β we have ε_{j} = sign(a_{j}). The fact that ε ∈ Ω means that

∥ ∑_{i∈σ∖τ} ε_{i}v_{i}∥_{2} ⩽ M\sqrt{2|σ ∖ τ|} ⩽ \frac{M\sqrt{2|σ|}}{2^{k/2}},  (40)

where in the last step of (40) we used the fact that |τ| ⩾ (1 − 2^{−k})|σ|.

The definition (36) of {v_{j}}_{j=1}^{m} implies that ⟨v_{i}, Ae_{j}⟩ = δ_{ij} for every i, j ∈ {1, …, m}. Hence,

∑_{i∈β} |a_{i}| = ⟨ ∑_{i∈β} a_{i}Ae_{i}, ∑_{i∈σ∖τ} ε_{i}v_{i}⟩ = ⟨ ∑_{i∈ϑ} a_{i}Ae_{i}, ∑_{i∈σ∖τ} ε_{i}v_{i}⟩ − ∑_{i∈(ϑ∖β)∩(σ∖τ)} ε_{i}a_{i}

⩽ ∥ ∑_{i∈ϑ} a_{i}Ae_{i}∥_{2}∥ ∑_{i∈σ∖τ} ε_{i}v_{i}∥_{2} + ∑_{i∈ϑ∩(σ∖τ^{∗})} |a_{i}| ⩽^{(40)} \frac{M\sqrt{2|σ|}}{2^{k/2}} ∥ ∑_{i∈ϑ} a_{i}Ae_{i}∥_{2} + ∑_{i∈ϑ∩(σ∖τ^{∗})} |a_{i}|. (41)

The penultimate step of (41) uses the Cauchy–Schwarz inequality and the fact that, by the definition of τ^{∗}, we have (ϑ ∖ β) ∩ (σ ∖ τ) = ϑ ∩ (σ ∖ τ^{∗}). Now,

∑_{i∈τ^{∗}} |a_{i}| = ∑_{i∈τ} |a_{i}| + ∑_{i∈β} |a_{i}| ⩽^{(35)} α_{k}M\sqrt{|σ|}∥ ∑_{i∈ϑ} a_{i}Ae_{i}∥_{2} + (2^{k} − 1) ∑_{i∈ϑ∩(σ∖τ)} |a_{i}| + ∑_{i∈β} |a_{i}|

= α_{k}M\sqrt{|σ|}∥ ∑_{i∈ϑ} a_{i}Ae_{i}∥_{2} + (2^{k} − 1) ∑_{i∈ϑ∩(σ∖τ^{∗})} |a_{i}| + 2^{k} ∑_{i∈β} |a_{i}|, (42)

where for the last step of (42) recall that ϑ∩(σ ∖τ) = (ϑ∩(σ ∖τ^{∗})) ·∪β. It remains to combine (41) and (42) to deduce that

∑_{i∈τ^{∗}} |a_{i}| ⩽ (α_{k} + 2^{\frac{k+1}{2}} ) M\sqrt{|σ|}∥ ∑_{i∈ϑ} a_{i}Ae_{i}∥_{2} + (2^{k+1} − 1) ∑_{i∈ϑ∩(σ∖τ^{∗})} |a_{i}|.  (43)

Recalling the definition of α_{k} in (34), we have α_{k+1} = α_{k} + 2^{(k+1)/2}, so the validity of (39) and (43) completes the proof that τ^{∗} satisfies the inductive hypothesis with k replaced by k + 1. □

Lemma 20. Fix m, n, t ∈ ℕ and β ⊆ {1, …, m}. Let A : ℝ^{m} → ℝ^{n} be a linear operator such that the vectors {Ae_{j}}_{j=1}^{m} ⊆ ℝ^{n} are linearly independent. Then there exist two subsets σ, τ ⊆ β satisfying σ ⊆ τ, |τ| ⩾ (1 − 2^{−t})|β| and |τ ∖ σ| ⩽ |β|/4 such that if we denote ϑ = τ ∪ ({1, …, m} ∖ β) then

∥Proj_{ℝ^{σ}}(AJ_{ϑ})^{−1}∥_{S_{∞}} ≲ max_{j∈\{1,...,m\}} \frac{2^{\frac{t}{2}}}{∥Proj_{F_{j}}Ae_{j}∥_{2}} ,

where we recall that the definition of the subspace F_{j} ⊆ ℝ^{n} is given in (7).

Proof. An application of Lemma 19 with σ = β and k = t produces τ ⊆ β with |τ| ⩾ (1 − 2^{−t})|β| such that if we choose ϑ = τ ∪ ({1, …, m} ∖ β) in (33) and continue with the notation in (34) then

∀ a ∈ ℝ^{m},  ∑_{i∈τ} |a_{i}| ≲ 2^{\frac{t}{2}} M\sqrt{|β|}∥ ∑_{i∈ϑ} a_{i}Ae_{i}∥_{2}.  (44)

Note that the above choice of ϑ makes the second term in the right hand side of (33) vanish, and this is the only way by which (33) will be used here. However, the more complicated form of (33) was needed in Lemma 19 to allow for the inductive construction to go through.

A different way to state (44) is the following operator norm bound.

∥Proj_{ℝ^{τ}} (AJ_{ϑ})^{−1}∥_{ℓ_{2}^{ϑ}→ℓ_{1}^{τ}} ≲ 2^{\frac{t}{2}} M\sqrt{|β|}.

Since |τ| ⩾ (1 − 2^{−t})|β| ⩾ |β|/2, if we set ε =^{def} |β|/(4|τ|) then ε ∈ (0, 1/2). We are therefore in position to use Lemma 15, thus producing a subset σ ⊆ τ with |τ ∖ σ| ⩽ ε|τ| = |β|/4 such that

∥Proj_{ℝ^{σ}}(AJ_{ϑ})^{−1}∥_{S_{∞}} = ∥Proj_{ℝ^{σ}}Proj_{ℝ^{τ}} (AJ_{ϑ})^{−1}∥_{S_{∞}} ≲ \frac{2^{\frac{t}{2}} M\sqrt{|β|}}{\sqrt{ε|τ|}} ≍ 2^{\frac{t}{2}} M.  □

Proof of Theorem 9. Recall that, in the setting of Theorem 9, we are currently assuming without loss of generality that ω = {1, …, m}. Choose r ∈ ℕ ∪ {0} such that

\frac{1}{2^{2r+1}} ⩽ 1 − \frac{k}{m} ⩽ \frac{1}{2^{2r−1}} .  (45)

Denote τ_{0} =^{def} {1, …, m} and σ_{0} =^{def} ∅. We shall construct by induction on u ∈ {0, …, r + 1} two subsets σ_{u}, τ_{u} ⊆ {1, …, m} such that if we denote

β_{u} =^{def} τ_{u} ∖ σ_{u}  and  ∀ u ∈ {1, …, r + 1},  ϑ_{u} =^{def} τ_{u} ∪ ({1, …, m} ∖ β_{u−1}) ,  (46)

then the following properties hold true for every u ∈ {1, …, r + 1}.

(a) σ_{u} ⊆ τ_{u} ⊆ β_{u−1}.

(b) |τ_{u}| ⩾ (1 − 2^{−2r+u−4})|β_{u−1}| and |β_{u}| ⩽ \frac{1}{4}|β_{u−1}|.

(c) ∥Proj_{ℝ^{σu}} (AJ_{ϑ_{u}})^{−1}∥_{S_{∞}} ≲ 2^{r− \frac{u}{2}} M, where M is defined in (34).

Indeed, assuming inductively that σ_{u−1}, τ_{u−1} have been constructed, the existence of sets σ_{u}, τ_{u} with the desired properties follows from an application of Lemma 20 with β = β_{u−1} and t = 2r − u + 4.

Recalling (46), by (a) we have β_{u−1} = β_{u} ·∪ σ_{u} ·∪ (β_{u−1} ∖ τ_{u}) for every u ∈ {1, …, r + 1}. Hence,

|σ_{u}| = |β_{u−1}| − |β_{u}| − |β_{u−1} ∖ τ_{u}| ⩾ |β_{u−1}| − |β_{u}| − \frac{|β_{u−1}|}{2^{2r−u+4}} ⩾ |β_{u−1}| − |β_{u}| − \frac{m}{2^{2r+u+2}} , (47)

where the penultimate inequality in (47) uses the first assertion in (b) and the final inequality in (47) uses the fact that, by induction, the second assertion in (b) implies that |β_{u−1}| ⩽ m/4^{u−1}, since β_{0} = {1, …, m}. Observe that the sets {σ_{u}}_{u=1}^{r+1} are pairwise disjoint, so if we denote

σ =^{def} ⋃ ·_{u=1}^{r+1} σ_{u},  (48)

then

|σ| = ∑_{u=1}^{r+1} |σ_{u}| ⩾^{(47)} |β_{0}| − |β_{r+1}| − \frac{m}{2^{2r+2}} ∑_{u=1}^{∞} \frac{1}{2^{u}} ⩾ m − \frac{m}{4^{r+1}} − \frac{m}{2^{2r+2}} = m − \frac{m}{2^{2r+1}} ⩾^{(45)} k. (49)

Next, recalling the definition of ϑ_{u} in (46), observe that

σ ⊆ ⋂_{u=1}^{r+1} ϑ_{u}.  (50)

Indeed, in order to verify the validity of (50) note that due to (a) we have σ_{u}, σ_{u+1}, …, σ_{r+1} ⊆ τ_{u} and σ_{1}, …, σ_{u−1} ⊆ {1, …, m} ∖ β_{u−1} for every u ∈ {1, …, r + 1}. It follows from (50) that if a ∈ ℝ^{σ} then for every u ∈ {1, …, r + 1} we have J_{σ}a ∈ J_{ϑ_{u}}ℝ^{ϑ_{u}} ⊆ ℝ^{m}. Consequently,

Proj_{ℝ^{σu}} (AJ_{ϑ_{u}})^{−1}(AJ_{σ})a = Proj_{ℝ^{σu}} J_{σ}a.  (51)

We therefore have the following estimate.

∥J_{σ}a∥_{2}^{2} =^{(48)} ∥ ∑_{u=1}^{r+1} Proj_{ℝ^{σu}} J_{σ}a∥_{2}^{2} = ∑_{u=1}^{r+1} ∥Proj_{ℝ^{σu}} J_{σ}a∥_{2}^{2} =^{(51)} ∑_{u=1}^{r+1} ∥Proj_{ℝ^{σu}} (AJ_{ϑ_{u}})^{−1}(AJ_{σ})a∥_{2}^{2}

{(c) \atop ≲} ∑_{u=1}^{r+1} 2^{2r−u}M^{2} ∥(AJ_{σ})a∥_{2}^{2} ≍ 2^{2r}M^{2} ∥(AJ_{σ})a∥_{2}^{2} ≍^{(45)} \frac{mM^{2}}{m − k} ∥(AJ_{σ})a∥_{2}^{2} . (52)

Recalling the definition of M in (34), since (52) holds true for every a ∈ ℝ^{σ} we conclude that

∥(AJ_{σ})^{−1}∥_{S_{∞}} ≲ \begin{matrix}√ & \overline{m} \\ √ & \overline{m − k} \end{matrix} · max_{j∈\{1,...,m\}} \frac{1}{∥Proj_{F_{j}}Ae_{j}∥_{2}} .

This is the desired estimate (8), which, together with (49), concludes the proof of Theorem 9. □

4.1. Geometric interpretation of Theorem 9. Theorem 21 below is a result of Giannopoulos [Gia96]. It can be viewed as a geometric analogue of the Sauer–Shelah lemma for ellipsoids. The (rough) analogy between the two results is that they both assert that certain “large” subsets of ℝ^{n} must admit a large rank coordinate projection that contains a certain “canonical shape” (a full hypercube in the Sauer–Shelah case and a large Euclidean ball in Giannopoulos’ case). A different geometric analogue of the Sauer–Shelah lemma was proved by Szarek and Talagrand in [ST89].

Theorem 21 (Giannopoulos). There exists a universal constant c ∈ (0, ∞) with the following property. Suppose that m, n ∈ ℕ and ε ∈ (0, 1). Let y_{1}, …, y_{m} ∈ ℝ^{n} be vectors that satisfy ∥y_{i}∥_{2} ⩽ 1 for every i ∈ {1, …, m}. Denote

E =^{def} {a = (a_{1}, …, a_{m}) ∈ ℝ^{m}; ∥ ∑_{j=1}^{m} a_{j}y_{j}∥_{2} ⩽ 1}.  (53)

Then there exists a subset σ ⊆ \{1, …, m\} with |σ| ⩾ (1 − ε)m such that Proj_{ℝ^{σ}}(E) ⊇ c\sqrt{ε}B_{2}^{σ}, where B_{2}^{σ} = {x ∈ ℝ^{σ} : ∥x∥_{2} ⩽ 1} denotes the unit Euclidean ball in ℝ^{σ}.

In this section we shall show that Theorem 21 is equivalent to Theorem 9, thus in particular describing a shorter proof of Theorem 9 that relies on Theorem 21.

Let us first prove that Theorem 9 implies Theorem 21. Suppose that we are in the setting that is described in the statement of Theorem 21. It was observed in [Gia96] that Theorem 21 with the additional assumption that y_{1}, …, y_{m} are linearly independent formally implies Theorem 21 in the above stated generality. Indeed, this follows by applying (the linear independent case of) Theorem 21 to the linearly independent vectors y_{1} + e_{n+1}, y_{2} + e_{n+2}, …, y_{m} + e_{n+m} ∈ ℝ^{n+m}. So, suppose that y_{1}, …, y_{m} ∈ ℝ^{n} are linearly independent and let x_{1}, …, x_{m} ∈ span{y_{1}, …, y_{m}} be the corresponding dual basis, i.e.,

∀ i, j ∈ {1, …, m},  ⟨x_{i}, y_{j}⟩ = δ_{ij}.  (54)

Define a linear operator A : ℝ^{m} → ℝ^{n} by setting Ae_{i} = x_{i} for every i ∈ {1, …, m}. Continuing with the notation for the subspace F_{j} ⊆ ℝ^{n} that is given in (7) (with ω = {1, …, m}), we know by (54) that y_{j} ∈ F_{j}, so ⟨Proj_{F_{j}}x_{j}, y_{j}⟩ = ⟨x_{j}, y_{j}⟩ = 1. Since we are assuming in the setting of Theorem 21 that ∥y_{j}∥_{2} ⩽ 1, this implies that 1 = ⟨Proj_{F_{j}}x_{j}, y_{j}⟩ ⩽ ∥y_{j}∥_{2} · ∥Proj_{F_{j}}x_{j}∥_{2} ⩽ ∥Proj_{F_{j}}x_{j}∥_{2}.

An application of Theorem 9 now shows that there exists σ ⊆ {1, …, m} with |σ| ⩾ ⌊(1 − ε)m⌋ and a universal constant c ∈ (0, ∞) such that

∀ b ∈ ℝ^{σ},  ∥ ∑_{j∈σ} b_{j}x_{j}∥_{2} ⩾ c\sqrt{ε}( ∑_{j∈σ} b_{j}^{2})^{\frac{1}{2}} .  (55)

We claim that (55) implies that Proj_{ℝ^{σ}}(E) ⊇ c\sqrt{ε}B_{2}^{σ}, where E is given in (53). Indeed, suppose that a = ∑_{j∈σ} a_{j}e_{j} ∈ ℝ^{σ} satisfies

a ∈ c\sqrt{ε}B_{2}^{σ} ⟺ ( ∑_{j∈σ} a_{j}^{2})^{\frac{1}{2}} ⩽ c\sqrt{ε}.  (56)

Since the vectors {x_{j}}_{j∈σ} ∪ {y_{j}}_{j∈{1,...,m}∖σ} form a basis of span{y_{1}, …, y_{m}}, there exists a vector b = (b_{1}, …, b_{m}) ∈ ℝ^{m} such that

∑_{j∈σ} a_{j}y_{j} = ∑_{j∈σ} b_{j}x_{j} + ∑_{j∈{1,...,m}∖σ} b_{j}y_{j}.  (57)

Denote

a^{∗} = (a_{1}^{∗}, …, a_{m}^{∗}) =^{def} ∑_{j∈σ} a_{j}e_{j} − ∑_{j∈{1,...,m}∖σ} b_{j}e_{j} ∈ ℝ^{m}.  (58)

Then Proj_{ℝ^{σ}}a^{∗} = a and

∥ ∑_{j=1}^{m} a_{j}^{∗}y_{j}∥_{2}^{2} = ⟨ ∑_{j=1}^{m} a_{j}^{∗}y_{j}, ∑_{j=1}^{m} a_{j}^{∗}y_{j}⟩ =^{(57)∧(58)} ⟨ ∑_{j=1}^{m} a_{j}^{∗}y_{j}, ∑_{j∈σ} b_{j}x_{j}⟩ =^{(54)∧(58)} ∑_{j∈σ} a_{j}b_{j}

⩽ ( ∑_{j∈σ} a_{j}^{2})^{\frac{1}{2}} ( ∑_{j∈σ} b_{j}^{2})^{\frac{1}{2}} ⩽^{(56)} c\sqrt{ε}( ∑_{j∈σ} b_{j}^{2})^{\frac{1}{2}} ⩽^{(55)} ∥ ∑_{j∈σ} b_{j}x_{j}∥_{2} =^{(57)∧(58)} ∥ ∑_{j=1}^{m} a_{j}^{∗}y_{j}∥_{2}. (59)

By cancelling ∥ ∑_{j=1}^{m} a_{j}^{∗}y_{j}∥_{2} from both sides of (59) and recalling (53), we conclude that a^{∗} ∈ E. Thus a = Proj_{ℝ^{σ}}a^{∗} ∈ Proj_{ℝ^{σ}}(E), as required.

Next, we shall prove the converse implication, i.e., that Theorem 21 implies Theorem 9. Suppose that we are in the setting of Theorem 9. As we explained in the beginning of Section 4, we may assume without loss of generality that ω = {1, …, m}, hence rank(A) = m. Let M ∈ (0, ∞) be defined as in (34), i.e., M = max_{j∈{1,...,m}} ∥Proj_{F_{j}}Ae_{j}∥_{2}^{−1}. Set

∀ i ∈ \{1, …, m\}, y_{i} =^{def} \frac{Proj_{F_{i}}Ae_{i}}{∥Proj_{F_{i}}Ae_{i}∥_{2}} ∈ ℝ^{n}.

Then by definition ∥y_{i}∥_{2} = 1 for every j ∈ {1, …, m}, and, by the same reasoning as in the beginning of Section 2.1, we know that ⟨y_{j}, Ae_{j}⟩ ⩾ 1/M and ⟨y_{i}, Ae_{j}⟩ = 0 for every distinct i, j ∈ {1, …, m}. By Theorem 21 applied with ε = 1 − k/m there exists σ ⊆ {1, …, m} of size |σ| ⩾ (1 − ε)m = k such that Proj_{ℝ^{σ}}(E) ⊇ c\sqrt{ε}B_{2}^{σ}, where E is defined in (53). Suppose that a ∈ ℝ^{σ} ∖ \{0\}. Then c\sqrt{ε}a/∥a∥_{2} ∈ Proj_{ℝ^{σ}}(E), which means that there exists b ∈ ℝ^{m} such that b_{j} = c\sqrt{ε}a_{j}/∥a∥_{2} for every j ∈ σ and (by the definition of E) we have ∥ ∑_{i=1}^{m} b_{i}y_{i}∥_{2} ⩽ 1. So,

∥ ∑_{j∈σ} a_{j}Ae_{j}∥_{2} ⩾ ∥ ∑_{j∈σ} a_{j}Ae_{j}∥_{2} · ∥ ∑_{j=1}^{m} b_{j}y_{j}∥_{2} ⩾ ⟨ ∑_{j∈σ} a_{j}Ae_{j}, ∑_{j=1}^{m} b_{j}y_{j}⟩

= ∑_{j∈σ} a_{j}b_{j}⟨Ae_{j}, y_{j}⟩ = ∑_{j∈σ} \frac{c\sqrt{ε}a_{j}^{2}}{∥a∥_{2}} ⟨Ae_{j}, y_{j}⟩ ⩾ \frac{c\sqrt{ε}}{M∥a∥_{2}} ∑_{j∈σ} a_{j}^{2} = \frac{c\sqrt{m − k}}{M\sqrt{m}} ∥a∥_{2}.

This is precisely the desired conclusion in Theorem 9. □

5. Marcus–Spielman–Srivastava

Our goal here is to prove Theorem 11. This section differs from the previous sections in that we shall use the method of interlacing polynomials of Marcus–Spielman–Srivastava without sketching the proofs of the tools that we quote. The reason for this is that the ideas of Marcus–Spielman– Srivastava are remarkable and deep, but nevertheless elementary and accessible, and their presentation in [MSS15a, MSS15b] and especially in the beautiful survey [MSS14] (which is the main reference in the present section) is already a perfect exposition for a wide mathematical audience.

Suppose that A : ℝ^{m} → ℝ^{n} is a linear operator. Let j_{1}, …, j_{k} be i.i.d. random variables that are distributed uniformly over {1, …, m}. For every t ∈ {1, …, k} consider the random vector

w_{t} =^{def} \sqrt{m}Ae_{j_{t}}.  (60)

Then,

𝔼[w_{t} ⊗ w_{t}] = ∑_{i=1}^{m}(Ae_{i}) ⊗ (Ae_{i}) = AA^{∗}.  (61)

Denote

γ =^{def} \frac{rank(A) (\sqrt{rank(A)} − \sqrt{k})^{2}}{∑{rank(A) \atop i=1} \frac{1}{s_{i}(A)^{2}}} .  (62)

With this notation, we shall prove below that

Pr [s_{k}( ∑_{t=1}^{k} w_{t} ⊗ w_{t}) ⩾ γ] > 0.  (63)

Recalling (60), we see that (62) and (63) imply that there exist j_{1}, …, j_{k} ∈ {1, …, m} such that

s_{k}( ∑_{t=1}^{k}(Ae_{j_{t}}) ⊗ (Ae_{j_{t}})) ⩾ \frac{γ}{m} = \frac{rank(A) (\sqrt{rank(A)} − \sqrt{k})^{2}}{m ∑_{i=1}^{rank(A)} \frac{1}{s_{i}(A)^{2}}} .  (64)

The rank of the operator B =^{def} ∑_{t=1}^{k}(Ae_{j_{t}})⊗(Ae_{j_{t}}) is at most the cardinality of σ =^{def} {j_{1}, …, j_{k}}. At the same time, by (64) we know that s_{k}(B) > 0, because we are assuming that k < rank(A). Thus B has rank at least k, implying that the indices j_{1}, …, j_{k} are necessarily distinct, or equivalently that |σ| = k. Consequently B = (AJ_{σ})(AJ_{σ})^{∗} and s_{k}(B) = s_{min}(B) = s_{min}(AJ_{σ})^{2} = 1/∥(AJ_{σ})^{−1}∥_{S_{∞}}^{2}. Therefore (64) is the same as the desired restricted invertibility statement (11) of Theorem 11.

It remains to establish the validity of (63). Denote Q =^{def} AA^{∗} : ℝ^{n} → ℝ^{n} and let q : ℝ → ℝ be the polynomial that is defined as follows.

∀ x ∈ ℝ, q(x) =^{def} (I − ∂_{y})^{k}det(xI_{n} + yQ)|_{y=0} ,

where I denotes the identity operator on the space of polynomials and ∂_{y} is the differentiation operator with respect to the variable y (and, as before, I_{n} is the n by n identity matrix). By Theorem 4.1 in [MSS14], the degree n polynomial q is the expectation of the characteristic polynomial of the random matrix ∑_{t=1}^{k} w_{t} ⊗ w_{t}. By Theorem 4.5 in [MSS14], all the roots of q are real, and we denote their decreasing rearrangement by ρ_{1} ⩾ ρ_{2} ⩾ … ⩾ ρ_{n}. Thus, ρ_{k} is the k’th largest root of q. A combination of Theorem 1.7 in [MSS14] and Theorem 4.1 in [MSS14] shows that

Pr [s_{k}( ∑_{t=1}^{k} w_{t} ⊗ w_{t}) ⩾ ρ_{k}] > 0.  (65)

Consequently, in order to prove (63) it suffices to prove that ρ_{k} ⩾ γ, where γ is defined in (62).

Write Q = UΔU^{−1}, where U : ℝ^{n} → ℝ^{n} is an orthogonal matrix and Δ : ℝ^{n} → ℝ^{n} is a diagonal matrix whose diagonal equals (s_{1}(A)^{2}, …, s_{n}(A)^{2}) ∈ ℝ^{n}. Then for every x, y ∈ ℝ we have

det(xI_{n} + yQ) = det (U(xI_{n} + yΔ)U^{−1}) = ∏_{i=1}^{n} (x + ys_{i}(A)^{2}) = x^{n−rank(A)} ∏_{i=1}^{rank(A)} (x + ys_{i}(A)^{2}) ,

where we used the fact that s_{i}(A) = 0 when i > rank(A). Consequently,

q(x) = x^{n−rank(A)}(I − ∂_{y})^{k} ∏_{i=1}^{rank(A)} (x + ys_{i}(A)^{2}) |_{y=0}.  (66)

We claim that if we denote by D the differentiation operator on the space of polynomials then

q(x) = x^{n−k} ∏_{i=1}^{rank(A)} (I − s_{i}(A)^{2}D) x^{k}.  (67)

The identity (67) is proven in the special case s_{1}(A) = … = s_{rank(A)}(A) = 1 in [MSS14]. The validity of (67) in full generality follows from checking that the coefficients of the polynomials that appear in the right hand sides of (66) and (67) are equal to each other. Indeed, starting with (66),

x^{n−rank(A)}(I − ∂_{y})^{k} ∏_{i=1}^{rank(A)} (x + ys_{i}(A)^{2}) |_{y=0}

= x^{n−rank(A)} ∑_{u=0}^{k} \binom{k}{u}(−1)^{u}∂_{y}^{u} ∑_{Ω⊆\{1,...,rank(A)\}} x^{rank(A)−|Ω|}y^{|Ω|} ∏_{i∈Ω} s_{i}(A)^{2}|_{y=0}

= ∑_{\begin{matrix}Ω⊆\{1,...,rank(A)\} \\ |Ω|⩽k \end{matrix}} \frac{(−1)^{|Ω|}x^{n−|Ω|}k!}{(k − |Ω|)!} ∏_{i∈Ω} s_{i}(A)^{2},  (68)

since ∂_{y}^{u}y^{|Ω|}|_{y=0} = |Ω|!·1_{{|Ω|=u}} for every (u, Ω) ∈ {0, …, k}×{1, …, rank(A)}. At the same time,

x^{n−k} ∏_{i=1}^{rank(A)} (I − s_{i}(A)^{2}D) x^{k} = x^{n−k} ∑_{Ω⊆{1,...,rank(A)}}(−1)^{|Ω|}( ∏_{i∈Ω} s_{i}(A)^{2})D^{|Ω|}x^{k}.  (69)

Since for every for every (u, Ω) ∈ {0, …, k} × {1, …, rank(A)} we have D^{|Ω|}x^{k} = 0 if |Ω| > k and D^{|Ω|}x^{k} = x^{k−|Ω|}k!/(k − |Ω|)! if |Ω| ⩽ k, the validity of (67) follows by comparing (68) and (69).

Having established the identity (67), we shall proceed to prove the desired estimate ρ_{k} ⩾ γ by applying the barrier method of [BSS12], reasoning along the lines of the argument that is presented in [MSS14]. Following [BSS12, SV13], given a polynomial f : ℝ → ℝ and ϕ ∈ (0, ∞) we consider the corresponding “soft spectral edge” smin_{ϕ}(f) ∈ ℝ, which is defined as follows

smin_{ϕ}(f) =^{def} inf {b ∈ ℝ : f′(b) = −ϕf(b)} .  (70)

As explained in [MSS14, Section 3.2], it is simple to check that for every ϕ ∈ (0, ∞) the smallest real root of f is at least the quantity smin_{ϕ}(f). Hence, if we define

g(x) =^{def} ∏_{i=1}^{rank(A)} (I − s_{i}(A)^{2}D) x^{k},  (71)

then it follows from the above discussion and the identity (67) that it suffices to prove that

sup_{ϕ∈(0,∞)} smin_{ϕ}(g) ⩾ γ.  (72)

Indeed, by (67) the n real roots of q consist of 0 with multiplicity n − k and also the k roots of g (which are therefore necessarily real). Since g has degree k, the validity of (72) would imply that the smallest root of g is at least γ > 0, so the k’th largest root of q would be at least γ as well.

To prove (72), recall that Lemma 3.8 of [MSS14] asserts that for every polynomial f : ℝ → ℝ all of whose roots are real, and for every ϕ ∈ (0, ∞), we have

smin_{ϕ}((I − D)f) ⩾ smin_{ϕ}(f) + \frac{1}{1 + ϕ}.  (73)

For s ∈ (0, ∞) define f_{s} : ℝ → ℝ by setting f_{s}(x) =^{def} f(sx) for every x ∈ ℝ. Observe that

∀ s ∈ (0, ∞),  (I − sD)f = ((I − D)f_{s})_{1/s}  and  smin_{ϕ}(f_{s}) =^{(70)} \frac{smin_{ϕ/s}(f)}{s}.  (74)

Consequently, for every real-rooted polynomial f and every s, ϕ ∈ (0, ∞) we have

smin_{ϕ}((I − sD)f) =^{(74)} smin_{ϕ}(((I − D)f_{s})_{1/s}) =^{(74)} s · smin_{sϕ}((I − D)f_{s})

⩾^{(73)} s (smin_{sϕ}(f_{s}) + \frac{1}{1 + sϕ}) =^{(74)} smin_{ϕ}(f) + \frac{1}{\frac{1}{s} + ϕ}. (75)

By iterating (75) we see that

smin_{ϕ}(g) ⩾ smin_{ϕ}(x^{k}) + ∑_{i=1}^{rank(A)} \frac{1}{\frac{1}{s_{i}(A)^{2}} + ϕ}

=^{(70)} −\frac{k}{ϕ} + ∑_{i=1}^{rank(A)} \frac{1}{\frac{1}{s_{i}(A)^{2}} + ϕ} ⩾ −\frac{k}{ϕ} + \frac{rank(A)}{ϕ + \frac{1}{rank(A)} ∑_{i=1}^{rank(A)} \frac{1}{s_{i}(A)^{2}}} , (76)

where the last step of (76) holds true due to the convexity of the function x ↦ 1/(ϕ + x) on (0, ∞). One can check that the value of ϕ that maximizes the right hand side of (76) is

ϕ_{max} =^{def} \frac{\sqrt{k}}{\sqrt{rank(A)} − \sqrt{k}} (\frac{1}{rank(A)} ∑_{i=1}^{rank(A)} \frac{1}{s_{i}(A)^{2}} ).

The right hand side of (76) equals γ when ϕ = ϕ_{max}, so ρ_{k} ⩾ smin_{ϕ_{max}}(g) ⩾ γ, as required. □

Remark 22. The above argument actually yields a subset σ ⊆ {1, …, m} with |σ| = k such that

s_{min}(AJ_{σ})^{2} = s_{k}(AJ_{σ})^{2} ⩾ \frac{1}{m} sup \{ − \frac{k}{ϕ} + ∑_{i=1}^{rank(A)} \frac{s_{i}(A)^{2}}{1 + ϕs_{i}(A)^{2}} : ϕ ∈ (0, ∞)\}.  (77)

Indeed, continuing with the above notation, we explained why ρ_{k} ⩾ sup_{ϕ∈(0,∞)} smin_{ϕ}(g), so (77) follows from (65) and the penultimate step in (76).

The estimate (77) is more complicated than the assertion of Theorem 11, but it is sometimes significantly stronger. One such instance is the matrix A of Example 7. In that case, a somewhat tedious but straightforward computation allows one to obtain sharp estimates on the right hand side of (77), yielding bounds that coincide (up to constant factors) with those that are stated in Example 7 as a consequence of Theorem 6, while Theorem 11 yields much weaker bounds. There are also situations in which (77) yields worse bounds than those that follow from Theorem 9, e.g. when s_{1}(A) ≍ … ≍ s_{m}(A) ≍ 1 and k = (1 − ε)m the bound on ∥(AJ_{σ})^{−1}∥_{S_{∞}} that follows from (77) is O(1/ε) while in the same situation Theorem 9 yields the bound ∥(AJ_{σ})^{−1}∥_{S_{∞}} ≲ 1/\sqrt{ε}.

References

[ARS02] R. P. Anstee, L. Rónyai, and A. Sali. Shattering news. Graphs Combin., 18(1):59–73, 2002.

[Bha97] R. Bhatia. Matrix analysis, volume 169 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1997. ISBN 0-387-94846-5. doi:10.1007/978-1-4612-0653-8.

[BHKW88] K. Berman, H. Halpern, V. Kaftal, and G. Weiss. Matrix norm inequalities and the relative Dixmier property. Integral Equations Operator Theory, 11(1):28–48, 1988.

[BS88] J. Bourgain and S. J. Szarek. The Banach-Mazur distance to the cube and the Dvoretzky-Rogers factorization. Israel J. Math., 62(2):169–180, 1988.

[BSS12] J. Batson, D. A. Spielman, and N. Srivastava. Twice-Ramanujan sparsifiers. SIAM J. Comput., 41(6):1704–1721, 2012.

[BT87] J. Bourgain and L. Tzafriri. Invertibility of “large” submatrices with applications to the geometry of Banach spaces and harmonic analysis. Israel J. Math., 57(2):137–224, 1987.

[BT89] J. Bourgain and L. Tzafriri. Restricted invertibility of matrices and applications. In Analysis at Urbana, Vol. II (Urbana, IL, 1986–1987), volume 138 of London Math. Soc. Lecture Note Ser., pages 61–107. Cambridge Univ. Press, Cambridge, 1989.

[BT91] J. Bourgain and L. Tzafriri. On a problem of Kadison and Singer. J. Reine Angew. Math., 420:1–43, 1991.

[Dav79] P. J. Davis. Circulant matrices. John Wiley & Sons, New York-Chichester-Brisbane, 1979. ISBN 0-471-05771-1. A Wiley-Interscience Publication, Pure and Applied Mathematics.

[DJT95] J. Diestel, H. Jarchow, and A. Tonge. Absolutely summing operators, volume 43 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1995. ISBN 0-521-43168-9. doi:10. 1017/CBO9780511526138.

[Fan49] K. Fan. On a theorem of Weyl concerning eigenvalues of linear transformations. I. Proc. Nat. Acad. Sci. U. S. A., 35:652–655, 1949.

[Gia95] A. A. Giannopoulos. A note on the Banach-Mazur distance to the cube. In Geometric aspects of functional analysis (Israel, 1992–1994), volume 77 of Oper. Theory Adv. Appl., pages 67–73. Birkhäuser, Basel, 1995.

[Gia96] A. A. Giannopoulos. A proportional Dvoretzky-Rogers factorization result. Proc. Amer. Math. Soc., 124(1):233–241, 1996.

[Gro53] A. Grothendieck. Résumé de la théorie métrique des produits tensoriels topologiques. Bol. Soc. Mat. São Paulo, 8:1–79, 1953.

[KS12] I. Kra and S. R. Simanca. On circulant matrices. Notices Amer. Math. Soc., 59(3):368–377, 2012.

[MSS14] A. W. Marcus, D. A. Spielman, and N. Srivastava. Ramanujan graphs and the solution of the Kadison– Singer problem. In Proceedings of the 2014 International Congress of Mathematicians. Volume III, pages

363–386. 2014. Available at http://www.icm2014.org/en/vod/proceedings.

[MSS15a] A. W. Marcus, D. A. Spielman, and N. Srivastava. Interlacing families I: Bipartite Ramanujan graphs of all degrees. Ann. of Math. (2), 182(1):307–325, 2015.

[MSS15b] A. W. Marcus, D. A. Spielman, and N. Srivastava. Interlacing families II: Mixed characteristic polynomials and the Kadison-Singer problem. Ann. of Math. (2), 182(1):327–350, 2015.

[MSS16] A. W. Marcus, D. A. Spielman, and N. Srivastava. Interlacing families III: Improved restricted invertibility estimates, 2016. In preparation.

[Nao12] A. Naor. Sparse quadratic forms and their geometric applications [following Batson, Spielman and Srivastava]. Astérisque, (348):Exp. No. 1033, viii, 189–217, 2012. Séminaire Bourbaki: Vol. 2010/2011. Exposés 1027–1042.

[Paj85] A. Pajor. Sous-espaces l_{1}^{n} des espaces de Banach, volume 16 of Travaux en Cours [Works in Progress]. Hermann, Paris, 1985. ISBN 2-7056-6021-6. With an introduction by Gilles Pisier.

[Pie67] A. Pietsch. Absolut p-summierende Abbildungen in normierten Räumen. Studia Math., 28:333–353, 1966/1967.

[Pis86] G. Pisier. Factorization of linear operators and geometry of Banach spaces, volume 60 of CBMS Regional Conference Series in Mathematics. Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1986. ISBN 0-8218-0710-2.

[Sau72] N. Sauer. On the density of families of sets. J. Combinatorial Theory Ser. A, 13:145–147, 1972.

[She72] S. Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific J. Math., 41:247–261, 1972.

[SS12] D. A. Spielman and N. Srivastava. An elementary proof of the restricted invertibility theorem. Israel J. Math., 190:83–91, 2012.

[ST89] S. J. Szarek and M. Talagrand. An “isomorphic” version of the Sauer-Shelah lemma and the Banach-Mazur distance to the cube. In Geometric aspects of functional analysis (1987–88), volume 1376 of Lecture Notes in Math., pages 105–112. Springer, Berlin, 1989. doi:10.1007/BFb0090050.

[Stø13] E. Størmer. Positive linear maps of operator algebras. Springer Monographs in Mathematics. Springer,

Heidelberg, 2013. ISBN 978-3-642-34368-1; 978-3-642-34369-8. doi:10.1007/978-3-642-34369-8.

[SV13] N. Srivastava and R. Vershynin. Covariance estimation for distributions with 2+ε moments. Ann. Probab., 41(5):3081–3111, 2013.

[Sza91] S. J. Szarek. On the geometry of the Banach-Mazur compactum. In Functional analysis (Austin, TX, 1987/1989), volume 1470 of Lecture Notes in Math., pages 48–59. Springer, Berlin, 1991. doi:10.1007/ BFb0090211.

[TJ89] N. Tomczak-Jaegermann. Banach-Mazur distances and finite-dimensional operator ideals, volume 38 of Pitman Monographs and Surveys in Pure and Applied Mathematics. Longman Scientific & Technical, Harlow; copublished in the United States with John Wiley & Sons, Inc., New York, 1989. ISBN 0-582-01374-7.

[Tro09] J. A. Tropp. Column subset selection, matrix factorization, and eigenvalue optimization. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 978–986. SIAM, Philadelphia, PA, 2009.

[Ver01] R. Vershynin. John’s decompositions: selecting a large part. Israel J. Math., 122:253–277, 2001.

[You14] P. Youssef. Restricted invertibility and the Banach-Mazur distance to the cube. Mathematika, 60(1):201– 218, 2014.

Mathematics Department, Princeton University, Fine Hall, Washington Road, Princeton, NJ 08544-1000, USA

   E-mail address: naor@math.princeton.edu

Laboratoire de Probabilités et de Modèles Aléatoires, Université Paris-Diderot, 5 rue Thomas Mann 75205, Paris CEDEX 13, France

   E-mail address: youssef@math.univ-paris-diderot.fr