Frame theory concerns redundant representations in a Hilbert space. A frame [16] is a sequence {ϕ i } i∈I in a Hilbert space H for which there exist α, β ∈ (0, ∞) such that
for every x ∈ H. If every ϕ i has unit norm, then we say the frame is unit norm, and if α = β, we say the frame is tight [12]. In the special case where H = R d , a frame is simply a spanning set, but unit norm tight frames are still interesting and useful [5,27]. For example, equiangular tight frames are unit norm tight frames with the additional property that | ϕ i , ϕ j | is constant over the choice of pair {i, j}. Equiangular tight frames are important because they necessarily span optimally packed lines, which in turn find applications in multiple description coding [33], digital fingerprinting [28], compressed sensing [2], and quantum state tomography [30]; see [18] for a survey.
Various applications demand control over the singular values of subensembles of frames. In quantum physics, Weaver's conjecture [38] (equivalent to the Kadison-Singer problem [24,10], and recently resolved in [25]) concerns the existence of subensembles of unit norm tight frames with appropriately small spectral norm. Compressed sensing [9,14] has spurred the pursuit of explicit frames with the property that every subensemble is well conditioned [13,6,2], or at least that most subensembles are well conditioned [35,8]. In this vein, Gurevich and Hadani [19] established that random subensembles of incoherent ensembles satisfy Wigner's semicircle law when the subensemble size is a vanishing fraction of the full ensemble size. Motivated by applications in erasure-robust analog coding, Haikin, Zamir and Gavish [22,21] recently considered the case in which this fraction is fixed. Of particular interest are random subensembles of equiangular tight frames, and in this paper, we consider equiangular tight frames comprised of 2d vectors in R d , which correspond to symmetric conference matrices. (Note that such frames have already received some attention in the context of compressed sensing [2,3].)
An n × n matrix S is said to be a conference matrix if (i) S ii = 0 for every i ∈ [n],
(ii) S ij ∈ {±1} for every i, j ∈ [n] with i = j, and
(iii) S S = (n -1)I.
A symmetric conference matrix of order n exists whenever n -1 ≡ 1 mod 4 is a prime power (by a Paley-based construction), and only if n ≡ 2 mod 4 and n -1 is a sum of two squares [23]. Explicitly, the Paley conference matrices are obtained by building a circulant matrix from the Legendre symbol and then padding with ones, for example:
where "±" denotes ±1. One may verify that the above example satisfies S 2 = 5I. For every n × n symmetric conference matrix S, it holds that I + 1 √ n-1 S is the Gram matrix of an equiangular tight frame consisting of n vectors in R n/2 [33]. In particular, the equiangular tight frames that arise from the Paley conference matrices are known as Paley equiangular tight frames. In what follows, we consider random principal submatrices of symmetric conference matrices with the understanding that they may be identified with the Gram matrix of a random subensemble of the corresponding equiangular tight frame.
Given an n × n symmetric matrix Z with eigenvalues λ 1 ≤ • • • ≤ λ n , we let µ Z denote the uniform probability measure over the spectrum of Z (counted with multiplicity):
This is known as the empirical spectral distribution of Z. If Z is a random matrix, then its empirical spectral distribution µ Z is a random measure. We say a sequence {ζ i } ∞ i=1 of random measures converges weakly almost surely to a non-random measure µ if for every bounded continuous function f : R → R, it holds that the random variable R f (x)dζ i (x) converges to R f (x)dµ(x) almost surely. We are interested in random matrices of a particular form. Let I denote a random subset of [n] such that the events {1 ∈ I}, . . . , {n ∈ I} have probability p and are independent. Then for any fixed n × n matrix A, we write X ∼ Sub(A, p) to denote the (random) principal submatrix of A with rows and columns indexed by I. For instance, take S from (1), put p = 1/3, and draw X ∼ Sub(S, p). Then the random index subset I ⊆ {1, . . . , 6} equals {2, 4} with probability p 2 (1p) 4 = 16/729, in which case X = [ 0 - -0 ]. Note that the size of the random matrix X is a random variable with binomial distribution.
Following [15], we define the Kesten-McKay distribution with parameter v ≥ 2 by
Recall that a lacunary sequence is a set {n i : i ∈ N} of natural numbers for which there exists λ > 1 such that n i+1 ≥ λn i for every i. We are now ready to state our main result; see Figure 1 for an illustration.
Theorem 1. Fix p ∈ (0, 1 2 ), take any lacunary sequence L for which there exists a sequence {S n } n∈L of symmetric conference matrices of increasing size n, and consider the corresponding random matrices X n ∼ Sub(S n , p). Then the empirical spectral distribution of 1 p √ n X n converges weakly almost surely to the Kesten-McKay distribution with parameter v = 1/p. We note that Theorem 1 is the first proven instance of an assortment of conjectures posed by Haikin, Zamir and Gavish in [22]. In general, we expect random submatrices of the Gram matrix of an equiangular tight frame of n vectors in C d to have empirical spectral distribution corresponding to the Wachter distribution [37] (also known as the MANOVA distribution) with parameters determined by both the sample probability p and the redundancy n d . As partial progress toward proving these conjectures, Haikin, Zamir and Gavish [21] demonstrated that for any sequence of equiangular tight frames of any fixed redundancy, the first four moments converge in expectation to the corresponding Wachter moments. In her masters thesis [20], Haikin made additional combinatorial observations to facilitate an eventual proof by the method of moments. The Kesten-McKay distribution is a special case of the Wachter distribution, and as illustrated in [15], its moments are far less complicated. This is our reason for focusing on the redundancy-2 case, and we credit our success to the relative simplicity of these moments.
While the hypothesis p < 1 2 in Theorem 1 may seem artificial at first glance, this constraint appears in the original Haikin-Zamir-Gavish conjectures [22], and for good reason. In terms of the equiangular tight frame Φ ∈ R n/2×n such that Φ Φ = I + 1 √ n-1 S, this restriction biases I to be typically smaller than the dimension n 2 so that the submatrix Φ I of columns indexed by I has a tall, skinny aspect ratio. When |I| > n 2 , then we expect a different spectral behavior since the submatrix Φ I now has a nontrivial nullspace. In this case of large I, if we let S I denote the submatrix of S with rows and columns indexed by I, then it is straightforward to show that the eigenvalues of S I are precisely the eigenvalues of S I c , though with an additional |I| -n 2 eigenvalues equal to each of ± √ n -1. Indeed, this follows from the facts that (i) the eigenvalues of A A are identical to the eigenvalues of AA modulo additional eigenvalues equal to 0, and (ii)
As an alternative method of drawing the random index subset I, one might be inclined to fix k and draw I uniformly from the subsets of [n] of order k. We suspect that the same convergence holds for this model by taking k = p/n , say; in fact, this might be provable from Theorem 1 by a perturbation argument. We instead focus on the model used n X along with a suitably scaled version of the Kesten-McKay density for v = 1/p. The similarity between these distributions was first observed by Haikin, Zamir and Gavish [22]. Our main result (Theorem 1) explains this phenomenon. in the original Haikin-Zamir-Gavish conjectures, and our proof makes use of the fact that {i ∈ I} is independent of {j ∈ I} for i = j in this model. One might also make progress on this problem by using a transform method instead of the method of moments. In fact, such techniques have proven effective in demonstrating that random submatrices of complex Hadamard matrices satisfy a Wachter law [36,17,1]. As an adjacent pursuit, there has been some work on constructing explicit matrices that satisfy Wigner's semicircle law [31,32], and it would be interesting to transfer these ideas to our setting.
In the next section, we prove Theorem 1 using the method of moments, saving the more technical portions for Section 3.
Given x ∈ R n , let diag(x) denote the n × n diagonal matrix whose diagonal entries are the entries of x. Given Z ∈ R m×n , let Z 2→2 denote the induced 2-norm of Z (i.e., the largest singular value of Z), and let Z S p denote the Schatten p-norm of Z (i.e., the p-norm of the singular values of Z). Throughout this paper, we will investigate how quantities relate as n → ∞. For example, suppose we are interested in a quantity f (n, θ) ≥ 0 that depends on both n ∈ N and some additional parameters θ ∈ R m . Then we write f
Our proof makes use of a standard sufficient condition for the almost sure weak convergence of random measures, namely, Proposition 2 below. We say that a probability measure µ is (a, b)-subgaussian if µ([-t, t] c ) ≤ ae -bt 2 for every t > 0. A probability measure is called subgaussian if it is (a, b)-subgaussian for some a, b > 0. A sequence of probability measures is said to be uniformly subgaussian if there exists a, b > 0 for which every probability measure in the sequence is (a, b)-subgaussian.
i=1 be a sequence of random probability measures that are almost surely uniformly subgaussian, and let µ be a non-random subgaussian probability measure. Suppose that for every k ∈ N, it holds that
Then ζ i converges weakly almost surely to µ.
The proof of Proposition 2 is standard (cf. Exercise 2.4.6 in [34]): use Chebyshev's inequality and the Borel-Cantelli lemma to show
almost surely for each k ∈ N, and then apply the moment continuity theorem to points in the convergence event. As we will see, verifying hypothesis (i) in our case reduces to a combinatorics problem, whereas hypothesis (ii) can be treated separately with the help of Talagrand concentration: Proposition 3 (Talagrand concentration, Theorem 2.1.13 in [34]). There exists a universal constant c > 0 for which the following holds: Suppose f : R n → R is both convex and σ-Lipschitz in • 2 , and let X be a random vector in R n with independent coordinates satisfying |X i | ≤ b almost surely. Then for every t ≥ 0, it holds that
Throughout, S n denotes an n×n symmetric conference matrix, we draw X n ∼ Sub(S n , p) and put Z n := 1 p √ n X n . We typically suppress the subscript n. While the size of Z is random, its average size is pn, and so we use 1 pn tr(Z k ) as a proxy for R x k dµ Z (x). As one might expect, this is a good approximation:
Proof. Since X is a submatrix of S, it holds that
where the last step applies the fact that N has binomial distribution. This immediately implies the desired bound on |EV -EW |. Finally, since |V |, |W | p 1 almost surely, we have
which completes the result.
As such, to demonstrate hypothesis (i) from Proposition 2 in our case, it suffices to prove
The Kesten-McKay moments are implicitly computed in [26], and are naturally expressed in terms of entries of Catalan's triangle:
Proposition 5 (Lemma 2.1 in [26]). For every v ≥ 2 and k ∈ N, it holds that
where B(n, k) denotes an entry of Borel's triangle:
To compute these limits, we first find a convenient expression for 1 n k/2+1 E tr(X k ). To this end, recall that X is the submatrix of S with index set I, and let P denote the random n × n diagonal matrix such that
It remains to show that these coefficients converge to the corresponding coefficients in (3). First, we introduce some additional notation. Taking inspiration from Bargmann invariants [4], it is convenient to write
With this, we define
∆(a(1), . . . , a(k)).
Considering (4), it therefore holds that
As such, to demonstrate (3), it suffices to determine the limit of V n (π) for every partition π of [k]. We start with a quick calculation: Lemma 6. For every π ∈ Π(k, t) with t < k/2 + 1, it holds that V n (π) → 0.
Proof. Estimate |V n (π)| using the triangle inequality to obtain a sum of
) terms, each of size at most 1.
For each t < k/2 + 1, this establishes that the coefficient of p t in (5) approaches zero, i.e., the corresponding coefficient in (3). Now we wish to tackle the limiting value of V n (π) in general. In light of the related literature [29], it comes as no surprise that V n (π) depends on whether π is a so-called crossing partition. We say a partition π of [k] is crossing if there exist A, B ∈ π with A = B for which there exist a 1 , a 2 ∈ A and b 1 , b 2 ∈ B such that a 1 < b 1 < a 2 < b 2 . Otherwise, π is said to be non-crossing. Next, for each x ∈ [k], we let π(x) denote the unique member of π such that x ∈ π(x). Consider the graph G π with vertex set π and edges given by π(x) ↔ π(x + 1) for every x ∈ [k]; here, we interpret x + 1 modulo k so that k + 1 = 1. Let EC(k, t) denote the set of non-crossing π ∈ Π(k, t) for which the edges of G π partition into simple even cycles. See Figure 2 for an example of such a partition π and its graph G π . Finally, let C n := 1 n+1 2n n denote the nth Catalan number. With these notions, we can describe the limit of each V n (π):
Lemma 7 (Key combinatorial lemma).
(ii) Suppose π ∈ EC(k, t) and the edges of G π partition into m simple cycles of sizes 2s 1 , . . . , 2s m . Then m = kt + 1 and
The proof of Lemma 7 is rather technical (involving multiple rounds of induction), and so we save it for Section 3. (Curiously, a reviewer of this paper noted that these signed products of Catalan numbers are the values of the Möbius function of the non-crossing partition lattice [29], and this observation may eventually lead to a more bijective combinatorial proof of Lemma 7.) In the meantime, we demonstrate how Lemma 7 can be applied to prove that the coefficients in (5) converge to the coefficients in (3). Recall that a Dyck path of semilength n is a path in the plane from (0, 0) to (2n, 0) consisting of n steps along the vector (1, 1), called up-steps, and n steps along the vector (1, -1), called down-steps, that never goes below the x-axis. We say a Dyck path is strict if none of the path's interior vertices reside on the x-axis. Each (strict) Dyck path determines a sequence of 2n letters from {U, D} that represent up-and down-steps in the path; this sequence is known as a (strict) Dyck word. With these notions, we may prove the following result by leveraging the fact that Borel's triangle counts so-called marked Dyck paths [7]; see Figure 2 for an illustration.
Proof. When t < k/2+1, the result follows from Lemma 6, and when k is odd, the k edges in each G π fail to partition into even simple cycles, and so the result follows from Lemma 7(i). Now suppose k is even and t ≥ k/2 + 1. For π ∈ EC(k, t), recall that the edges of G π are indexed by [k] and partitioned into simple even cycles. Define MD(π) to be the words w : [k] → {U, U , D} such that for every simple cycle in G π with edges indexed by T ⊆ [k], Notice that G π can be recovered from either marked Dyck path since a cycle is born with each un-marked up-step and dies once the Dyck path returns to its height from the birth of that cycle. By Theorem 2 in [7], marked Dyck paths are counted by entries in Borel's triangle, which explains their appearance in (3).
the restriction w| T is a strict Dyck word with all but its first up-steps marked (here, U denotes a marked up-step). Note that strict Dyck words of semi-length s are in one-to-one correspondence with Dyck words of semi-length s -1, and so there are C s-1 of them. As such, Lemma 7 implies that for every π ∈ Π(k, t), it holds that
Let MD(k, t) denote the set of marked Dyck words w : [k] → {U, U , D} with tk/2 -1 marked up-steps, none of which are at ground level. We observe that
Then equations ( 6) and ( 7) together give
where the last step applies Theorem 2 in [7].
At this point, we are in a position to verify hypothesis (i) from Proposition 2 in our case. For hypothesis (ii), we follow the approach suggested by Remark 2.4.5 in [34] of leveraging Talagrand concentration to bound the variance. First, we pass to a setting that is more amenable to analysis with Talagrand concentration. Here and throughout, for each n ∈ L, we fix an n × n matrix F such that
Var F P 2j
Proof. Define Y := 1 p √ n P SP , and observe that
Since Y commutes with P and Y P = Y , the binomial theorem gives
and so rearranging gives
The following estimate holds for any choice of random variables
Var(X i ).
The lemma follows from applying this estimate to (8) by induction on k.
Next, we establish the convexity and Lipschitz continuity required by Talagrand:
. Then f is convex and (8 k kn 1-1/2k )-Lipschitz. Proof. We adopt the shorthand notation D x := diag(x). First, f is convex since • S 2k satisfies the triangle inequality and t → t 2k is convex:
To compute a Lipschitz bound, we apply the factorization
where the last step follows from the fact that
(and similarly for v). Next, we apply the reverse triangle inequality to get
which implies the result.
Finally, we apply Talagrand concentration to obtain a variance bound:
Proof. Given the mapping f from Lemma 10, define f : R n → R in terms of subgradients by f (x) := sup
This is known as the smallest convex extension of f to R n , and it is straightforward to verify that f is convex and (8 k kn 1-1/2k )-Lipschitz with f | R = f . Let B ∈ R n have independent entries, each equal to 1 with probability p and 0 otherwise. Since B ∈ R almost surely, it holds that f (B) has the same distribution as F P 2k S 2k , and we let E denote its expectation. By Talagrand concentration (Proposition 3), there exists c > 0 such that
Combining with Lemma 9 then gives
We may now verify hypotheses (i) and (ii) from Proposition 2 in our case.
Proof of Theorem 1. Put Z n := 1 p √ n X n and µ := µ KM(1/p) . First, we modify the random measure µ Zn so that we may apply Proposition 2 to prove the result. Indeed, µ Zn fails to be a probability measure with probability (1p) n , since µ Zn = 0 when I = I n is the empty set. To rectify this, we define
Then it suffices to prove ζ n → µ weakly almost surely, since the Borel-Cantelli lemma implies 1 {In=∅} → 0 almost surely, and so for every bounded continuous f : R → R, it holds that
Conveniently, for every n ∈ L and k ∈ N, it holds that
almost surely, and so the left-hand side inherits moments from the right-hand side.
To apply Proposition 2, we first observe that
almost surely, and so {ζ n } n∈L are almost surely uniformly bounded, and therefore almost surely uniformly subgaussian. Similarly, µ is bounded and therefore subgaussian. Fix k ∈ N.
As a consequence of Lemma 8, it holds that
and so by Lemma 4, we have
As such, {ζ n } n∈L satisfies hypothesis (i) from Proposition 2. Next, Lemma 11 establishes that Var 1 pn tr(Z k n ) p,k n -1/k , and so Lemma 4 implies
Writing L = {n i : i ∈ N}, select λ > 1 such that n i+1 ≥ λn i for every i ∈ N.
As such, {ζ n } n∈L also satisfies hypothesis (ii) from Proposition 2, and so ζ n → µ weakly almost surely, as desired.
3 Proof of Lemma 7
It remains to compute, for each π ∈ Π(k, t), the limit of We begin with some basic properties of ∆. (v) If a 1 = a k-1 and a 1 = a k , then ∆(a 1 , . . . , a k ) = ∆(a 1 , . . . , a k-2 ).
Proof. First, (i) follows from the fact that S is symmetric with off-diagonal entries in {±1}. Next, (ii) follows from the fact that the diagonal entries of S are 0. Recalling the definition of ∆, then (iii) follows from commutativity. Next suppose a k-1 = a 1 . Then
and (iv) follows since b∈[n] S a k-1 b S ba 1 is the (a k-1 , a 1 ) entry of S 2 = (n -1)I. Finally, in the case where a 1 = a k-1 , we have
Let π be a partition of [k]. Recall that for j ∈ [k], we let π(j) denote the block of π containing j. We extend this notation to any integer j by considering π(j) to be the block of π containing a representative of j modulo k. For convenience, we record the following immediate consequence of Lemma 12(iii).
Lemma 13. Let π be a partition of [k] and fix j ∈ Z. Define π to be the partition of
To establish Lemma 7(i), we will show separately that V n (π) → 0 for every crossing partition π ∈ Π(k, t) and that V n (π) → 0 for every non-crossing partition π ∈ Π(k, t) such that G π contains an odd cycle. Lemma 14. Let π ∈ Π(k, t) be a crossing partition. Then V n (π) → 0.
Proof. For π ∈ Π(k, t) to be a crossing partition, it must hold that t ≥ 2 and k ≥ 4. Observe that the case t = 2 follows immediately from Lemma 6 since k ≥ 4. Now consider t > 2 and suppose the lemma has been established for every crossing partition on t -1 blocks. By Lemma 6, we may further suppose that k satisfies t ≥ k/2 + 1. Then for π ∈ Π(k, t), the pigeonhole principle guarantees that π contains a singleton block {j} ∈ π. By Lemma 13, we may assume {k} ∈ π. We proceed in cases:
Case I: π(1) = π(k -1). We may apply Lemma 12(v) to obtain
The restriction of π \ {k} to [k -2] results in a crossing partition π of [k -2] into t -1 blocks. Moreover, the above expression for V n (π) implies
and so our induction hypothesis provides V n (π) → 0.
Case II: π(1) = π(k-1). Writing out π = {B 1 , . . . , B t-1 , {k}}, we choose representatives j 1 , . . . , j t-1 ∈ [k -1] with π(j i ) = B i . Then by Lemma 12(iv), we have
∆(a(1), . . . , a(k -1), a(j i )).
For i, j ∈ [t -1], we define new blocks
and the corresponding crossing partition
Since each V n (π i ) → 0 by our induction hypothesis, we see V n (π) → 0 as well.
For non-crossing partitions, we will study the structure of the graph G π for π ∈ Π(k, t), which we recall has vertex set π and edges π(j) ↔ π(j + 1) for all j ∈ [k]. Observe that if G π has a loop, then π(j) = π(j + 1) for some j ∈ [k], and so V n (π) = 0 by Lemma 12(ii). For this reason, we direct our attention to loop-free partitions π, that is, partitions π for which G π is loop-free.
Given a loop-free graph G on vertices V with edges E, we say v ∈ V is a cut vertex if the induced subgraph of G on V \ {v} is disconnected. A graph with no cut vertices is called biconnected, and the biconnected components of a graph are its maximal biconnected subgraphs. When the biconnected components of G are all simple cycles, we call G a cactus. A reviewer of this paper noted that cactus graphs also emerge in the context of traffic freeness [11], but at the time of this writing, we have not fully investigated how deep this connection is. Lemma 15. If π ∈ Π(k, t) is a loop-free non-crossing partition, then t ≥ k/2 + 1 and G π is a cactus whose edges partition into kt + 1 simple cycles.
Proof. First, suppose G π is a cactus whose edges partition into kt + 1 simple cycles. Since G π has no loops, the number of cycles is at least at least half the number of edges, that is, kt + 1 ≥ k/2. Rearranging then gives t ≥ k/2 + 1. It remains to verify that G π is, indeed, a cactus whose edges partition into kt + 1 simple cycles.
Fixing k, we proceed by induction on kt. If π ∈ Π(k, k), then G π is itself a simple cycle and hence a cactus. For kt > 0, we now consider a loop-free non-crossing partition π ∈ Π(k, t). By the pigeonhole principle, we may select B ∈ π such that B contains at least Observe that our cycle {B 1 , . . . , B } in G π of length corresponds to the two simple cycles in G π i of {B i 2 , . . . , B i i } and {B i i , B i i+1 , . . . , B i } with lengths i -1 andi + 1 and share the cut vertex B i i . Moreover, all other simple cycles are identical between the two graphs. If is odd, then for each i ∈ [3, -1], either i -1 ori + 1 is odd, and so G π i must have an odd cycle. Since each π i has t -1 blocks and an odd cycle, we can apply our induction hypothesis to conclude that each V n (π i ) → 0 so that V n (π) → 0, as desired by (i). Suppose instead that is even, but G π has an odd cycle. This odd cycle is also contained in each G π i for i ∈ [3, -1], and again we can apply our induction hypothesis to conclude that V n (π) → 0, thereby establishing (i).
Finally, for (ii), suppose that is even and that the edges of G π partition into m cycles of lengths 2s 1 , . . . , 2s m with 2s m = . Notice that if i -1 is odd, then G π i contains an odd cycle, and V n (π i ) → 0. Since the contribution of these terms is negligible, we must compute the limit of
The cycles of lengths 2s 1 , . . . , 2s m-1 are common to both G π and G π 2i+1 , while the cycle of length = 2s m in G π corresponds to two cycles of length 2i and -2i in G π 2i+1 . Applying our induction hypothesis, we have
Reindexing and applying the convolution identity for Catalan numbers, we have Hence, V n (π) → (-1) k/2-m • C s 1 -1 • • • C sm-1 , thereby establishing (ii).
Proof of Lemma 7. To prove (i), consider π ∈ Π(k, t)\EC(k, t). Then either π is crossing, G π contains a loop, or G π contains an odd cycle. If π is crossing, then V n (π) → 0 by Lemma 14. If G π contains a loop, then V n (π) = 0 by Lemma 12(ii). If π is loop-free and non-crossing but G π contains an odd cycle, then V n (π) → 0 by Lemma 16(i). This establishes (i). Finally, (ii) follows from applying both Lemmas 15 and 16(ii).