The Kadison–Singer Problem in mathematics and engineering

2. Kadison–Singer in Operator Theory

A significant advance on KS was made by Anderson (4) in 1979 when he reformulated KS into what is now known as the Paving Conjecture (lemma 5 of ref. 1 shows a connection between KS and Paving).

Paving Conjecture (PC).

For ε >0, there is a natural number r so that for every natural number n and every linear operator T on l₂ⁿ whose matrix has zero diagonal, we can find a partition (i.e., a paving) {A_j}_j=1^r of {1, …, n}, so that

It is important that r not depend on n in PC. PC has an equivalent formulation for operators on ℓ₂. We will say that an arbitrary operator T satisfies PC if T − D(T) satisfies PC where D(T) is the diagonal of T. It is known that the class of operators satisfying PC (the “pavable operators”) is a closed subspace of B(ℓ₂). Also, to verify PC we only need to verify it for any one the following classes of operators (3, 5). (i) unitary operators, (ii) positive operators, (iii) orthogonal projections, (iv) Gram operators of the form T*T = (〈f _i, f _j〉)_i,j∈I where ∥f _i∥ = 1 and Te_i = f_i is a bounded operator. The only large classes of operators which have been shown to be pavable are “diagonally dominant” matrices (6–8) and matrices with all entries real and positive (9, 10).

Remark 2.1:

There are standard methods for turning our finite dimensional conjectures into infinite dimensional ones and vice versa (see ref. 11, proposition 2.1 and the proof of theorem 2.2 or ref. 3). In particular, we can replace ℓ₂ ⁿ in PC by ℓ₂ and get an equivalent conjecture (3).

In ref. 5 it was shown that the following conjecture implies KS.

Conjecture 2.2.

There exist 0 < ε, δ < 1 with the following property: for any orthogonal projection P on ℓ₂ ⁿ with δ(P) ≤ δ, there is a diagonal projection Q such that ∥QPQ∥ ≤ 1 − ε and ∥(I − Q) P(I − Q)∥ ≤ 1 − ε.

It is important that ε, δ are independent of n in Conjecture 2.2. It is unknown whether KS implies Conjecture 2.2. Recently, Weaver (12) showed that a slight weakening of this will produce a conjecture equivalent to KS.

Conjecture 2.3.

There exist universal constants 0 < δ, ε < 1 and r ∈ ℕ so that for all n and all orthogonal projections P on ℓ₂ ⁿ with δ(P) ≤ δ, there is a paving {A_j}_j=1 ^r of {1, 2, …, n} so that ∥Q_AjPQ_Aj∥ ≤ 1 − ε, for all j = 1, 2, …, r.

This conjecture needs some explanation since there is nothing in ref. 12 that looks anything like Conjecture 2.3. In ref. 12, Weaver introduces what he calls “Conjecture KS_r”. A careful examination of the proof of theorem 1 of ref. 12 reveals that Weaver shows Conjecture KS_r implies Conjecture 2.3, which in turn implies KS, which (after the theorem is proved) is equivalent to KS_r.

3. Kadison–Singer in Hilbert Space Theory

In this section, we will see that KS is actually a fundamental result concerning inner products. Recall that a family of vectors {f_i}_i∈I is a “Riesz basic sequence” in a Hilbert space ℍ if there are constants A, B > 0 so that for all scalars {a_i}_i∈I we have We call , the “lower and upper Riesz basis bounds” for {f_i}_i∈I. If ε > 0 and A = 1 − ε, B = 1 + ε we call {f_i}_i∈I an “ε-Riesz basic sequence.” If ∥f_i∥ = 1 for all i ∈ I this is a “unit norm” Riesz basic sequence. A natural question is whether we can improve the Riesz basis bounds for a unit norm Riesz basic sequence by partitioning the sequence into subsets. This conjecture was first stated by P.G.C. and R. Vershynin (unpublished work), where it was shown that KS implies the conjecture.

Conjecture 3.1 (R_ε-Conjecture).

For every ε > 0, every unit norm Riesz basic sequence is a finite union of ε-Riesz basic sequences.

We will now show that KS is equivalent to the R_ε-Conjecture.

Theorem 3.2.

The following are equivalent.

1. The Kadison–Singer Problem.

2. If T : ℓ₂ → ℓ₂ is a bounded linear operator with ∥Te_i∥ = 1 for all i ∈ I, then for every ε > 0, {Te_i}_i∈I is a finite union of ε-Riesz basic sequences.

3. The R_ε-Conjecture.

Proof:

(1) ⇒ (2): Fix ε > 0. Given T as in (2), let S = T*T. Since S has ones on its diagonal, by the (infinite form of the) Paving Conjecture there is a r = r(ε, ∥T∥) and a partition {A_j}_j=1 ^r of I with so that for every j = 1, 2, …, r we have where δ = ε/(∥S∥ + 1). Now, for all f = Σ_i∈I a_ie_i we have Similarly, ∥Σ_i∈Aj a_iTe_i∥² ≤ (1 + ε) Σ_i∈Aj |a_i|².

(2) ⇒ (3): This is obvious.

(3) ⇒ (1): Let T ∈ B (ℓ₂) with Te_i = f_i and ∥f_i∥ = 1 for all i ∈ I. We need to show that the Gram operator G of {f_i}_i∈I is pavable. Fix 0 < δ < 1 and let ε > 0. Let g_i = f_i ⊕ δe_i ∈ ℓ₂ ⊕ ℓ₂. Then ∥g_i∥ = 1 for all i ∈ I and for all scalars {a_i}_i∈I So {g_i}_i∈I is a unit norm Riesz basic sequence and 〈g_i, g_k〉 = (1 − δ²)〈f_i, f_k〉 for all i ≠ k ∈ I. By the R _ε-Conjecture, there is a partition {A_j}_j=1 ^r so that for all j = 1, 2, …, r and all f = Σ_i∈I a_ie_i, Subtracting Σi∈A_j |a_i|² through the inequality yields That is, Since QA_j (G − D(G))QA_j is a self-adjoint operator, we have (1 − δ²)∥QA_j (G − D(G))QA_j∥ ≤ ε. That is, (1 − δ²)G (and hence G) is pavable.

Remark 3.3:

The proof of (3) ⇒ (1) of Theorem 3.2illustrates a standard method for turning conjectures about unit norm Riesz basic sequences {g_i}_i∈I into conjectures about unit norm families {f_i}_i∈I with T ∈ B(ℓ₂ (I)) and Te_i = f_i. Namely, given {f_i}_i∈I and 0 < δ < 1 let g_i = f_i ⊕ δe_i ∈ ℓ₂ (I) ⊕ ℓ₂ (I). Then {g_i}_i∈I is a unit norm Riesz basic sequence and for δ small enough, g_i is close enough to f_i to pass inequalities from {g_i}_i∈I to {f_i}_i∈I.

It follows from Remark 2.1 that (2) of Theorem 3.2 has a finite dimensional equivalent:

Conjecture 3.4.

For every ε > 0 and every T ∈ B(ℓ₂ⁿ) with ∥Te_i∥ = 1 for i = 1, 2, …, n there is an r = r(ε, ∥T∥) and a partition {A_j}_j=1^r of {1, 2, …, n} so that for all j = 1, 2, …, r and all scalars {a_i}_i∈Aj we have

By Remark 3.3, we can reformulate Conjecture 3.4 into a statement about unit norm Riesz basic sequences.

One advantage of the R_ε -Conjecture is that it can be shown to students right at the beginning of a course in Hilbert spaces. We note that this conjecture fails for equivalent norms on a Hilbert space. For example, if we renorm ℓ₂ by: |{a_i}| = ∥a_i∥_ℓ2 + sup_i|a_i| then the R_ε-Conjecture fails for this equivalent norm. To see this let f_i = e_2i + e _2i+1/( + 1) where {e_i}_i∈ℕ is the unit vector basis of ℓ₂. This family is now a unit norm Riesz basic sequence, but no infinite subset satisfies the R _ε-Conjecture. To check this let J ⊂ ℕ with |J| = n and a_i = 1/ for i ∈ J. Then Since the norm above is bounded away from one for n ≥ 2, we cannot satisfy the requirements of the R _ε-Conjecture. It follows that a positive solution to KS would imply a fundamental new result concerning “inner products,” not just norms. Actually, the R _ε-Conjecture is way too strong for proving KS. As we will see, either the upper or the lower inequalities are sufficient for proving KS, and for each of these we only need a universal constant instead of 1 − ε or 1 + ε.

4. Kadison–Singer in Banach Space Theory

In 1987, Bourgain and Tzafriri (13) proved a fundamental result in Banach space theory known as the “restricted invertibility principle.” This theorem gave rise to a problem in the area that has received a great deal of attention (3, 14).

Bourgain–Tzafriri Conjecture (BT).

There is a universal constant A > 0 so that for every B > 1 there is a natural number r = r(B) satisfying: For any natural number n, if T ∈ B(ℓ₂ⁿ) is a linear operator with ∥T∥ ≤ B and ∥Te_i∥ = 1 for all i = 1, 2, …, n, then there is a partition {A_j}_j=1^r of {1, 2, …, n} so that for all j = 1, 2, …, r and all choices of scalars {a_i}_i∈Aj we have

It had been “folklore” for years that KS and BT must be equivalent. But no one was quite able to give a formal proof of this fact. Recently P.G.C. and R. Vershynin (unpublished work) gave a formal proof of the equivalence of KS and BT. Sometimes BT is called “strong BT,” since there is a weakening of it called “weak BT.” In weak BT we allow A to depend on the norm of the operator T. A significant amount of effort has been invested in trying to show that strong and weak BT are equivalent (3, 6, 11). In ref. 11 it was shown that weak BT is equivalent to the Feichtinger Conjecture (see Section 5). We will now end this search by showing that all these conjectures are equivalent to KS. First, we state another conjecture that is formally weaker than weak BT.

Conjecture 4.1.

There exists a constant A > 0 and a natural number r so that for all natural numbers n and all T : ℓ₂ⁿ → ℓ₂ⁿ with ∥Te_i∥ = 1 for all i = 1, 2, …, n and ∥T∥ ≤ 2, there is a partition {A_j}_j=1^r of {1, 2, …, n} so that for all j = 1, 2, …, r and all scalars {a_i}_i∈Aj we have

Now we establish the equivalence of weak BT and KS.

Proof:

Since KS implies the R _ε-Conjecture implies weak BT implies Conjecture 4.1, we just need to show that Conjecture 4.1 implies Conjecture 2.3. So choose r, A satisfying Conjecture 4.1. Fix 0 < δ ≤ ¾ and let P be an orthogonal projection on ℓ₂ ⁿ with δ(P) ≤ δ (notation from Section 1). Now, 〈Pe_i, e_i〉 = ∥Pe_i∥² ≤ δ implies ∥(I − P)e_i∥² ≥ 1 − δ ≥ ½. Define T : ℓ₂ ⁿ → ℓ₂ ⁿ by Te_i = (I − P)e_i/∥(I − P)e_i∥. For any scalars {a_i}_i=1 ⁿ we have So ∥Te_i∥ = 1 and ∥T∥ ≤ 2. By Conjecture 4.1, there is a partition {A_j}_j=1 ^r of {1, 2, …, n} so that for all j = 1, 2, …, r and all scalars {a_i}_i∈Aj, we have Hence, It follows that for all scalars {a_i}_i∈Aj Now, for all f = Σ_i=1 ⁿ a_ie_i we have Thus, So Conjecture 2.3 holds.□

Finally, let us note that Remark 3.3 and BT imply that KS is equivalent to just the lower inequality in the R _ε -Conjecture and even without the lower constant having to be close to one.

5. Kadison–Singer in Frame Theory

A family {f_i}_i∈I of elements of a (finite or infinite dimensional) Hilbert space ℍ is called a “frame” for ℍ if there are constants 0 < A ≤ B < ∞ (called the “lower and upper frame bounds,” respectively) so that for all f ∈ ℍ If we only have the right-hand inequality in Eq. 5.1 we call {f_i}_i∈I a “Bessel sequence with Bessel bound B.” If A = B we call this a “A-tight frame” and if A = B = 1 it is called a “Parseval frame.” If all the frame elements have the same norm this is an “equal norm” frame, and if the frame elements have norm 1 it is a “unit norm frame.” The numbers {〈f, f_i〉}_i∈I are the “frame coefficients” of the vector f ∈ ℍ. If {f_i}_i∈I is a Bessel sequence, the “synthesis operator” for {f_i}_i∈I is the bounded linear operator T : ℓ₂ (I) → ℍ given by T(e_i) = f_i for all i ∈ I. The “analysis operator” for {f_i}_i∈I is T* and satisfies: T*(f) = Σ_i∈I 〈f, f_i〉e_i. So for all f ∈ ℍ, ∥T*(f)∥² = Σ_i∈I |〈f, f_i〉|² and hence the smallest Bessel bound for {f_i}_i∈I equals ∥T*∥². The “frame operator” for the frame is the positive, self-adjoint invertible operator S = TT* : ℍ → ℍ satisfying Sf = Σ_i∈I 〈f, f_i〉f_i, for all f ∈ ℍ. “Reconstruction” of vectors in the space is achieved via the formula: f = Σ_i∈I〈f, f_i〉S ⁻¹ f_i. A frame is Parseval if and only if S = I. In the finite-dimensional case, if {g_j}_j=1 ⁿ is an orthonormal basis of ℓ₂ ⁿ consisting of eigenvectors for S with respective eigenvalues {λ_j}_j=1 ⁿ, then for every 1 ≤ j ≤ n, Σ_i∈I|〈f_i, g_j〉|² = λ_j. In particular, Σ_i∈I ∥f_i∥² = trace S (= n if {f_i}_i∈I is a Parseval frame). For an introduction to frame theory, see Christensen (15).

A fundamental result in frame theory was proved independently by Naimark and Han and Larson (15, 16).

Theorem 5.1.

A family {f_i}_i∈I is a Parseval frame for a Hilbert space ℍ if and only if there is a containing Hilbert space ℍ ⊂ ℓ₂ (I) with an orthonormal basis {e_i}_i∈I so that the orthogonal projection P_H of ℓ₂ (I) onto ℍ satisfies P_H(e_i) = f_i for all i ∈ I.

Weaver (12) established an important relationship between frames and KS by showing that the following conjecture is equivalent to KS.

Conjecture 5.2.

There are universal constants B ≥ 4 and ε > and an r ∈ ℕ so that the following holds: Whenever {f_i}_i=1^M is a unit norm B-tight frame for ℓ₂ⁿ, there exists a partition {A_j}_j=1^r of {1, 2, …, M} so that for all j = 1, 2, …, r and all f ∈ ℓ₂ⁿ we have

Using Conjecture 5.2 we can show that the following conjecture is equivalent to KS.

Proof:

Since Conjecture 3.4 clearly implies Conjecture 5.3, we just need to show that Conjecture 5.3 implies Conjecture 5.2. So choose D as in Conjecture 5.3 and choose B ≥ 4 and ε > so that D ≤ B − ε. Let {f_i}_i∈I be a unit norm B tight frame for ℓ₂ ⁿ. If Te_i = f_i is the synthesis operator for this frame then ∥T∥² = ∥T*∥² = B. So by Conjecture 5.3 there is an r = r(B) and a partition {A_j}_j=1 ^r of {1, 2, …, n} so that for all j = 1, 2, …, r and all scalars {a_i}_i∈Aj So ∥TQ_Aj∥² ≤ B − ε, and for all f ∈ ℓ₂ ⁿ we have This inequality verifies that Conjecture 5.2 holds and so KS holds.

Remark 3.3 and Conjecture 5.3 show that we only need any universal upper bound in the R _ε-Conjecture to hold to get KS.

In his work on time-frequency analysis, Feichtinger (3, 11) noted that all of the Gabor frames he was using (see Section 7) had the property that they could be divided into a finite number of subsets which were Riesz basic sequences. This observation led to the conjecture:

Feichtinger Conjecture (FC).

Every bounded frame (or equivalently, every unit norm frame) is a finite union of Riesz basic sequences.

There is a significant body of work on this conjecture (3, 6–8, 11). Yet it remains open even for Gabor frames. In ref. 11 it was shown that FC is equivalent to the weak BT (and hence is implied by KS). We now know by Theorem 4.2 that FC is equivalent to KS.

6. Kadison–Singer in Harmonic Analysis

A deep and fundamental question in harmonic analysis is to understand the distribution of the norm of a function f ∈ span {e^2πint}_n∈I =: S(I) over [0, 1]. It is known (9) if [a, b] ⊂ [0, 1] and ε > 0 then there is a partition of ℤ into arithmetic progressions A_j = {nr + j}_n∈ℤ, 0 ≤ j ≤ r − 1 so that for all f ∈ S(A_j) we have What these inequalities show is that the functions in S(A_j) have their norms nearly uniformly distributed across [a, b] and [0, 1]\[a, b]. The central question is whether such a result is true for arbitrary measurable subsets of [0, 1] [but it is known that the partitions can no longer be arithmetic progressions (3, 10, 19)]. If E is a measurable subset of [0, 1] let P_E denote the orthogonal projection of L ²[0, 1] onto L ²(E). i.e. P_E(f) = f·χ_E. The fundamental question here is then

Conjecture 6.1.

If E ⊂ [0, 1] is measurable and ε > 0 is given, there is a partition {A_j}_j=1^r of ℤ so that for all j = 1, 2, …, r and all f ∈ S(A_j)

Despite harmonic analysis having some of the deepest theory in mathematics, almost nothing is known about the distribution of the norms of functions coming from the span of a finite subset of the characters: except that this question has connections to very deep questions in number theory (19). Very little progress has ever been made on Conjecture 6.1 except for a specialized result of Bourgain and Tzafriri (14). Any advance on this problem would have broad applications throughout the field.

If φ ∈ L ²(ℝ) is an essentially bounded function, we define the Töplitz operator T _φ on L ²[0, 1] by T_φ(f) = f·φ. In the 1980s much effort was put into showing that the class of Töplitz operators satisfies the Paving Conjecture [see Berman, Halpern, Kaftal and Weiss (9, 10) and references therein] during which time the uniformly pavable operators were classified, and it was shown that T _φ is pavable if φ is Riemann integrable (9). But to this day the KS problem for Toplitz operators remains a deep mystery. The next theorem helps explain why so little progress has been made on KS for Töplitz operators. Because this problem is equivalent to the deep question facing harmonic analysis stated above. To prove the theorem we will first look at the decomposition of Töplitz operators of the form P_E.

Theorem 6.3.

The following are equivalent:

1. Conjecture 6.1.

2. For every measurable E ⊂ [0, 1] the Töplitz operator P_E satisfies KS.

3. All Töplitz operators satisfy KS.

Proof:

(2) ⇔ (3): This follows from the fact that the class of pavable operators is closed and the class of Töplitz operators are contained in the closed linear span of the Töplitz operators of the form P_E. i.e. Arbitrary bounded measurable functions on [0, 1] are uniformly approximable by simple functions.

(1) ⇔ (2): By Proposition 6.2, given ε > 0, there is a partition {A_j}_j=1 ^r so that Eq. 6.1 holds if and only if for all j = 1, 2, …, r and all f ∈ L ² [0, 1], Subtracting like terms through the inequality yields that this inequality is equivalent to Since Q_Aj (P_E − D(P_E)Q_Aj is a self-adjoint operator, Eq. 6.2 is equivalent to ∥Q_Aj (P_E − D(P_E)Q_Aj∥ ≤ ε|E|. i.e. P_E is pavable.□

7. Kadison–Singer in Time-Frequency Analysis

Although the Fourier transform has been a major tool in analysis for over a century, it has a serious lacking for signal analysis in that it hides in its phases information concerning the moment of emission and duration of a signal. What was needed was a localized time-frequency representation that has this information encoded in it. In 1946, Gabor (17) filled this gap and formulated a fundamental approach to signal decomposition in terms of elementary signals. Gabor’s method has become the paradigm for signal analysis in engineering as well as its mathematical counterpart: time-frequency analysis.

To build our elementary signals, we choose a “window function” g ∈ L ²(ℝ). For x, y ∈ ℝ we define modulation by x and translation by y of g by If Λ ⊂ ℝ × ℝ and {E_xT_yg}_(x,y)∈Λ forms a frame for L ²(ℝ), we call this an (irregular) “Gabor frame.” Standard Gabor frames are the case where Λ is a lattice Λ = aℤ × bℤ where a, b > 0 and ab ≤ 1. For an introduction to time-frequency analysis we recommend the excellent book of Gröchenig (18).

It was in his work on time-frequency analysis that Feichtinger observed that all the Gabor frames he was working with could be decomposed into a finite union of Riesz basic sequences. This work led him to formulate the Feichtinger Conjecture, which we now know is equivalent to KS. There is a significant amount of literature on the Feichtinger Conjecture for Gabor frames as well as wavelet frames and frames of translates (3, 6–8, 19). It is known that Gabor frames over rational lattices (11) and Gabor frames whose window function is “localized” satisfy the Feichtinger Conjecture (6–8). But the general case has defied solution.

Translates of a single function play a fundamental role in frame theory, time-frequency analysis, sampling theory, and more (19, 20). If g ∈ L ²(ℝ), λ_n ∈ ℝ for n ∈ ℤ and {T _λn g}_n∈ℤ is a frame for its closed linear span, we call this a “frame of translates.” Although considerable effort has been invested in the Feichtinger Conjecture for frames of translates, little progress has been made. One exception is a surprising result from ref. 21.

Theorem 7.1.

Let I ⊂ ℤ be bounded below, a > 0 and g ∈ L²(ℝ). Then {T_nag}_n∈I is a frame if and only if it is a Riesz basic sequence.

A recent theorem of ours helps to explain why the Feichtinger Conjecture has been so intractible for Gabor frames, frames of translates, and wavelet frames. That is, this problem is equivalent to a variation of the deep problem facing harmonic analysis (Conjecture 6.1). The proof of this result is quite substantial and will have to wait for another time.

8. Kadison–Singer in Engineering

Frames have traditionally been used in signal processing because of their resilience to additive noise, resilience to quantization, numerical stability of reconstruction, and the fact that they give greater freedom to capture important signal characteristics (22, 23). Recently, Goyal, Kovac̆ević, and Vetterli (23) proposed using the redundancy of frames to mitigate the losses in packet-based transmission systems such as the Internet. These systems transport packets of data from a “source” to a “recipient.” These packets are sequences of information bits of a certain length surrounded by error-control, addressing and timing information that assure that the packet is delivered without errors. It accomplishes this task by not delivering the packet if it contains errors. Failures here are due primarily to buffer overflows at intermediate nodes in the network. So to most users, the behavior of a packet network is not characterized by random loss but rather by “unpredictable transport time.” This delay is due to a protocol, invisible to the user, that retransmits lost or damaged packets. Retransmission of packets takes much longer than the original transmission and in many applications retransmission of lost packets is not feasible. If a lost packet is independent of the other transmitted data, then the information is truly lost. But if there are dependencies between transmitted packets, one could have partial or complete recovery despite losses. We are thus led to consider using frames for encoding. But which frames? In this setting, when frame coefficients are lost we call them “erasures.” It was shown in ref. 24 that an equal norm frame minimizes mean-squared error in reconstruction with erasures if and only if it is tight. So a fundamental question is to identify the optimal classes of equal norm Parseval frames for doing reconstruction with erasures. Since the lower frame bound of a family of vectors determines the computational complexity of reconstruction, it is this constant that we need to control. Formally, this is a max/min problem, which looks like:

Problem 8.1.

Given natural numbers k, K find the class of equal norm Parseval frames {f_i}_i=1^Kn in ℓ₂ⁿ which maximize the minimum below:

This problem has proved to be untouchable at this time. We only have a complete solution to the problem for two erasures (25–27). It was hoped that some special cases of the problem would be more tractible and serve as a starting point for the classification because the frames we are looking for are contained in this class.

Conjecture 8.2.

There exists an ε > 0 so that for large K, for all n and all equal norm Parseval frames {f_i}_i=1^Kn for ℓ₂ⁿ, there is a J ⊂ {1, 2, …, Kn} so that both {f_i}_i∈J and {f_i}_i∈J^c have lower frame bounds at least ε.

The ideal situation would be for Conjecture 8.2 to hold for all K ≥ 2. In order for {f_i}_i∈J and {f_i}_i∈J^c to both be frames for ℓ₂ ⁿ, they at least have to span ℓ₂ ⁿ. So the first question is whether we can partition our frame into spanning sets. This fact will follow from the Rado–Horn theorem (28).

Theorem 8.3 (Rado–Horn).

Let I be a finite or countable index set and let {f_i}_i∈I be a collection of vectors in a vector space. There is a partition {A_j}_j=1^r such that for each j = 1, 2, …, r, {f_i}_i∈Aj is linearly independent if and only if for all finite J ⊂ I

The Rado–Horn Theorem will decompose our frames for us.

Proof:

If J ⊂ {1, 2, …, Kn}, let P_J be the orthogonal projection of ℓ₂ ⁿ onto span {f_i}_i∈J. Since {f_i}_i=1 ^Kn is a equal norm Parseval frame (see Section 5) Σ_i=1 ^Kn ∥f_i∥² = Kn∥f ₁∥² = n. Now, So the Rado–Horn conditions hold with constant r = K. If we divide our family of Kn vectors into K linearly independent sets, since each set cannot contain more than n-elements, it follows that each has exactly n-elements.□

If we are going to be able to erase arbitrary k-element subsets of our frame, then the frame must be a union of erasure sets. So a generalization of Conjecture 8.2, which is a class containing the class given in Problem 8.1, is:

Conjecture 8.5.

There exists ε > 0 and a natural number r so that for all large K and all equal norm Parseval frames {f_i}_i=1^Kn in ℓ₂ⁿ there is a partition {A_j}_j=1^r of {1, 2, …, Kn} so that for all j = 1, 2, …, r the Bessel bound of {f_i}_i∈Aj is ≤ 1 − ε.

No progress has been made on any of this list of problems. But before we discuss why, let us turn to another setting where these problems arise. For many years engineers have believed that it should be possible to do signal reconstruction without phase. Recently, Balan, Casazza, and Edidin (29) verified this longstanding conjecture of the signal-processing community by constructing new classes of equal norm Parseval frames. This problem comes from a fundamental problem in speech recognition technology called the “cocktail party problem.”

Cocktail Party Problem.

We have a tape recording of a group of people talking at a cocktail party. Can we recover each individual voice with all of its voice characteristics?

As we will see, the main problem here is “signal reconstruction with noisy phase.” The standard format for signal processing (i.e., removing noise from a signal) is to take a signal [i.e., a f ∈ L ²(ℝ)] and digitalize it by sending it through the fast Fourier transform (29). This procedure just computes the frame coefficients of f with respect to a Gabor frame (see Section 7), say {〈f, f_i〉}_i∈I. Next, we take the absolute values of the frame coefficients to be processed and store the phases There are countless methods for processing a signal. One of the simplest is “thresholding.” Thresholding is a process of deleting any frame coefficients whose moduli fall outside of a “threshold interval,” say [A, B] where 0 < A < B. The idea is that if our frame is chosen carefully enough then the deleted coefficients will represent the “noise” in the signal. Now it is time to reconstruct a clear signal. This reconstruction is done by passing our signal back through the inverse fast Fourier transform (i.e., we are inverting the frame operator). But to do this we need phases for our coefficients. So we take our stored X_i(f) and put them back on the processed frame coefficients, which are at this time all nonnegative real numbers. This step is where the problem arises. If the noise in the signal was actually in the phases (which occurs in speech recognition), then we just put the noise back into the signal. The way to avoid this problem is to construct frames for which reconstruction can be done directly from the absolute value of the frame coefficients and not needing the phases. This construction was done in ref. 29.

Theorem 8.6.

For a generic real frame on ℓ₂ⁿ with at least (2n − 1)-elements the mapping ± f → {|〈f, f_i〉|}_i∈I is one-to-one.

For a generic complex frame on ℓ₂ⁿ with at least (4n − 2)-elements, the mapping cf → {|〈f, f_i〉|}_i∈I, |c| = 1, is one-to-one.

“Generic” here means that the set of frames with this property is dense in the class of all frames in the Zariski topology on the Grassman manifold (29).

In the process of looking for algorithms for doing reconstruction directly from the absolute value of the frame coefficients, it was discovered in the real case (the complex case is much more complicated) that the standard algorithms failed when the vector was getting approximately half its norm from the positive frame coefficients and half from the negative coefficients (R. Balan, P.G.C., and D. Edidin, unpublished work). The algorithms behave as if one of these sets has been “erased.” The necessary conditions for reconstruction without phase in ref. 29 help explain why. These conditions imply that every vector in the space must be reconstructable from either the positive frame coefficients or the negative ones. It is also shown by Balan, P.G.C., and Edidin (unpublished work) that signal reconstruction without phase is equivalent to a (P₀) problem with additional constraints (see Formula 8.2 below). So once again we have bumped into Problem 8.1 and Conjectures 8.2 and 8.5.

Our next theorem helps to explain why all of these reconstruction problems have proved to be so difficult. Namely, because KS has come into play again.

Theorem 8.7.

(1) Conjecture 8.2 implies Conjecture 8.5.

(2)Conjecture 8.5 is equivalent to KS.

Proof:

(1) Fix ε > 0, r, K as in Conjecture 8.2. Let {f_i}_i=1 ^Kn be an equal norm Parseval frame for an n-dimensional Hilbert space ℍ_n. By Theorem 5.1 there is an orthogonal projection P on ℓ₂ ^Kn with Pe_i = f_i for all i = 1, 2, …, Kn. By Conjecture 8.2, there is a J ⊂ {1, 2, …, Kn} so that {Pe_i}_i∈J and {Pe_i}_i∈J^c both have lower frame bound ε > 0. Hence, for f ∈ ℍ_n = P(ℓ₂ ^Kn), That is, Σ_i∈J |〈f, Pe_i〉|² ≤ (1 − ε)∥f∥². So the upper frame bound of {Pe_i}_i∈J [which is the norm of the analysis operator (PQ_J)* for this frame] is ≤ 1 − ε. Since PQ_J is the synthesis operator for this frame, we have that ∥Q_JPQ_J∥ = ∥PQ_J∥² = ∥(PQ_J)*∥² ≤ 1 − ε. Similarly, ∥Q_J^cPQ_J^c∥ ≤ 1 − ε. So Conjecture 8.5 holds for r = 2.

(2) We will show that Conjecture 8.5 implies Conjecture 5.2. Choose an integer K and an r, ε > 0 with 1/ < ε. Let {f_i}_i=1 ^M be a unit norm K-tight frame for an n-dimensional Hilbert space ℍ_n. Then (see Section 5) M = Σ_i=1 ^M ∥f_i∥² = Kn. Since {1/ f_i}_i=1 ^M is an equal norm Parseval frame, by Theorem 5.1, there is an orthogonal projection P on ℓ₂ ^M with Pe_i = 1/ f_i, for i = 1, 2, …, M. By Conjecture 8.5, we have universal r, ε > 0 and a partition {A_j}_j=1 ^r of {1, 2, …, M} so that the Bessel bound ∥(PQ_Aj)*∥² for each family {f_i}_i∈Aj is ≤ 1 − ε. So for j = 1, 2, …, r and any f ∈ ℓ₂ ⁿ we have Hence, Since K ε > , we have verified Conjecture 5.2.

For the converse, choose r, δ, ε satisfying Conjecture 2.3. If {f_i}_i=1 ^Kn is an equal norm Parseval frame for an n-dimensional Hilbert space ℍ_n with 1/K ≤ δ, by Theorem 5.1 we have an orthogonal projection P on ℓ₂ ^Kn with Pe_i = f_i for i = 1, 2, …, Kn. Since δ(P) = ∥f_i∥² ≤ 1/K ≤ δ (see the proof of Proposition 8.4), by Conjecture 2.3 there is a partition {A_j}_j=1 ^r of {1, 2, …, Kn} so that for all j = 1, 2, …, r, Since ∥(PQ_Aj)*∥² is the Bessel bound for {Pe_i}_i∈Aj = {f_i}_i∈Aj, we have that Conjecture 8.5 holds.□

Theorem 8.7 yields yet another equivalent form of KS. That is, KS is equivalent to finding a quantitative version of the Rado–Horn Theorem.

Recently, a slight weakening of KS has appeared. There is currently a flury of activity surrounding sparse solutions to vastly underdetermined systems of linear equations. This topic has applications to problems in signal processing (recovering signals from highly incomplete measurements), coding theory (recovering an input vector from corrupted measurements), and much more. If A is an n × m matrix with n < m, the sparsest solution to Af = g is where ∥f∥_ℓ0 = |{i : f (i) ≠ 0}|. The problem with (P ₀) is that it is NP hard in general. This led researchers to consider the ℓ₁ version of the problem known as “basis pursuit.” where ∥f∥_ℓ1 = Σ_i=1 ^m |f(i)|. Building on the groundbreaking work of Donoho and Huo (30), it has now been shown (31–37) that there are classes of matrices for which the problems (P ₀) and (P ₁) have the same unique solutions. Since (P ₁) is a convex program, it can be solved by its classical reformulation as a linear program. A recent approach to these problems involves “restricted isometry constants” (33). If A is a matrix with column vectors {v_j}_j∈J, for all 1 ≤ S ≤ |J| we define the “S-restricted isometry constants, δ_S” to be the smallest constant so that for all T ⊂ J with |T| ≤ S and for all {a_j}_j∈T The fundamental principle here is the construction of (nearly) unit norm frames for which subsets of a fixed size are (nearly) Parseval (or better, nearly orthogonal). The conjecture related to this construction is:

Conjecture 8.8.

For every S ∈ ℕ and B and every 0 < δ < 1, there is a natural number r = r(δ, S, B) so that for every n and every unit norm B-Bessel sequence {f_i}_i=1 ^M for ℓ₂ ⁿ there is a partition {A_j}_j=1 ^r of {1, 2, …, M} so that for all j = 1, 2, …, r, {f_i}_i∈Aj is a frame sequence with S-restricted isometry constant δ_S ≤ δ.

A particularly interesting case of this arises in harmonic analysis. Let E be a measurable subset of [0, 1] of positive measure. Does the family satisfy Conjecture 8.8? It is clear the R_ε-Conjectureimplies Conjecture 8.8. The question of whether these conjectures were equivalent has been an open problem. Recently, however, it was shown (3) that Conjecture 8.8 is “formally” weaker than KS and actually it has a positive solution.