Although the Fourier transform has been a fundamental tool in analysis for over 100 years, it has a serious deficit for signal decomposition in that it hides in its phases the moment of emission and the duration of a signal. What was needed was a localized time-frequency representation that had this information encoded in it. This gap was filled in 1946 by physicist Dennis Gabor. He was interested in signal decomposition. The traditional method of approaching this problem was to decompose the signal into orthogonal components, typically sine and cosine functions---this is the methodology of Fourier analysis---and then to identify which components harbor the noise and then eliminate them. The trouble with this technique is that noise is typically not a sine function nor a cosine function; rather it is a spike rather akin to a Dirac delta mass---see Figure 1. So the problem comes down to representing a Dirac mass as a sum of sines and cosines. That process is by nature inefficient and unnatural.

Figure 1

Gabor wanted to replace the standard orthogonal basis with a basis which is localized in time and frequency. He was inspired by the concept of sheet music. In Gabor's view, music consists of just one note---but that note gets adjusted in frequency and shifted in time. See Figure 2.

Figure 2

The upshot of the point of view just described is that we require a special note on which to build everything else. In wavelet theory, and by osmosis in the theory of frames, this special function is called the {\it motherfunction}. We denote this special function by g. Then adjusting frequency and shifting in time corresponds to considering the "basis"

{ e^{2π i j t} g(t - k) }

for j,k ∈ Z. Now let L²(R) denote the square-integrable functions on R equipped with the inner product

⟨ h, k ⟩ = ∫ h(x) k^*(x) dx ,

where * denotes complex conjugation. Given any L² function f (this f represents the signal), we wish to consider the sequence of scalars given by

a_jk = { ⟨ f(t), e^{2π i j t} g(t - k) ⟩ } .

If the motherfunction is chosen propitiously, then certain of the a_jk will represent the undesired noise in the signal. The filter will discard those terms, and then reassemble the remaining terms into a cleaned-up function f⁺. In order for this program to be effective, it must be the case that the process of assigning the sequence {a_jk} to the function f is one-to-one. It is not known precisely which conditions on g will guarantee this to happen.

Figure 3

In fact Gabor believed that choosing g to be the Gaussian g(x) = e^-x2/2 (Figure 3) will guarantee the univalence that we need. There are both mathematical and physical grounds for this idea. It was only in the early 1980s that Balian and Low showed this belief to be false. Interestingly, the Gaussian is still used in applications as a motherfunction just because the difficulties that arise only occur with high frequencies which tend to have no practical significance. In 1952, Duffin and Schaeffer were working on some very deep problems in non-harmonic Fourier series. As a tool, they introduced the notion of a "frame". This concept eventually gave a mathematical foundation to Gabor theory. That is, the indicated transform is univalent if and only if the "basis functions" form a frame. For many years frame theory was confined to signal processing. Today, frames have found application in dozens of areas of research including internet coding, wireless communication, communications, sampling theory, distributed processing, quantum information theory and much more.

Now let us provide a somewhat more general consideration of frames. We work in the Hilbert space of square integrable functions on the real line. Rather than treat the special collection of functions e^{2π i j t} g(t - k) } that were generated from the single motherfunction g, let us instead consider a collection {f_j} of functions. Given a square-integrable function f, we write

a_j = ⟨ f, f_j ⟩ .

We say that the collection {f_j} forms a frame if there are positive constants A and B such that

A ∫ |f(x)|² dx ≤ ∑_j |⟨ f,f_j ⟩ | ² ≤ B ∫ |f(x)|² dx .

It is important to realize here that, in practice, we want our frames to have built-in redundancy. We usually do not choose the f_j to be an orthonormal basis for the square integrable functions, nor do we choose them to be any basis at all. In practice a frame has more functions in it than a standard bare-bones basis.

The Kadison-Singer problem, which is the focus of this AIM workshop, was first formulated in a paper published in 1959 by Kadison and Singer. The problem arose in the context of mathematical physics. This problem was believed to be a specialized result in one area of mathematics---namely C^*-algebras. Recently (to the surprise of the scientific community), it was shown that the Kadison-Singer Problem is equivalent to fundamental unsolved problems in a dozen areas of research in pure mathematics, applied mathematics and even engineering. So, for many years, people in these areas were all working on the same problem without even knowing it and hence different working groups had little intercommunication. The AIM workshop is the first gathering of people from these many different areas. A good deal of their efforts during the week were devoted to tooling up and finding a common vocabulary so that they could attack these problems together.

Several formulations of the Kadison-Singer problem (and, according to a recent paper of Casazza and Tremain, there are over 50 formulations in total) are inspired by the ideas of Gabor and the theory of frames. Two of these equivalent formulations have become known as the R_\epsilon-conjecture and the Feichtinger Conjecture. We continue to work in the square-integrable functions on the line. We say that {X_j} is a Riesz basic sequence if there are positive constants C, D such that, for any sequence {a_j} of complex numbers,

C ∑_j=1 ^∞ |a_j|² ≤ ∫ | ∑ _j a_j X_j |² dx^1/2 ≤ D ∑_j=1 ^∞ |a_j|² . So a Riesz basic sequence is the isomorphic image of an orthonormal basis in L².

The R_ε conjecture posits that, given a Riesz basic sequence {X_j}, and given an ε > 0, there is a finite partition Z = ∪_j A_j such that, for each j, and for each sequence {a_n} _{n ∈ Aj},

∫ | ∑_{n ∈ Aj} a_n X_n |² dx ≤ (1 + ε) ∑_{n ∈ Aj}} |a_n|² .

Part of this conjecture used to be that there was a dual inequality on the left. But Casazza and his collaborators have shown that that inequality follows from the one on the right, and vice-versa. A problem in Gabor theory asks whether every Gabor frame can be decomposed into a finite number of Riesz basic sequences. The problem was later generalized to arbitrary (bounded) frames and today is known as the Feichtinger Conjecture.

An interesting feature of the history of the Kadison-Singer problem is this. It went through a quiet period from about 1965 to 1980, just because everyone realized how difficult the question was. Around 1980 Joel Anderson brought the subject back to life by introducing the idea of paving. The new question is as follows: Let ε > 0. Does there exist an r ∈ N so that, for all n x n matrices A, there is a partition (A_j)_j=1^r of {1, 2, … , n} so that (for a basis e₁, …, e_n) the projection operators Q_Aj(∑_{i = 1}ⁿ a_i e_i) = ∑_{i ∈ Aj} a_i e_i satisfy ||Q_Aj A Q_Aj || ≤ ε for each j = 1, …, r? The philosophical connection with Kadison-Singer (especially with the R_ε conjecture) is clear. Workshop participant Gary Weiss fascinated the group with his blend of mathematical analysis and computer calculations of pavings.

Part of the fascination of the Kadison-Singer problem is that it has so many applications in mathematics and science. As an instance, Casazza and his collaborators recently conducted a collaboration with Siemens Corporate Research which is headquartered in Germany. Siemens is interested in the classical "cocktail party problem". The problem is that, at a cocktail party, there are twenty or more conversations going on in the same room. How can one pick out one particular conversation clearly? Of course human beings learn how to do this through experience, and voice recognition, and by filtering out unwanted conversations. This is all done subconsciously and intuitively. But how can we teach a machine to do it? This is a very complex problem which has a multitude of parts to it. One part of the problem involved a very old conjecture of the speech processing community: "Signal reconstruction should be independent of phase". It turns out that this question comes down to showing that, given a frame {f_j}, one can recover the original function from

∑_j | ⟨f, f_j ⟩| . (**)

We say in these circumsances that the problem is "phase free". For it is standard Fourier analysis that one can recover f from an expression like that on the right of (**) without absolute values. The problem is, if the frame is suffiently redundant, can one recover f from the expression on the right of (**) as written---with the absolute values included?

Casazza and his collaborators showed that this could be done. It is still an open problem---and a difficult one that may turn out to be NP-Complete---to determine how redundant the frame must be in order to make these assertions true in the sense of producing efficient algorithms for the reconstruction. It has been shown that doing signal reconstruction without phase requires giving an "effective solution" of the Kadison-Singer Problem for the particular frame under consideration. Thus a whole new field of inquiry, about complexity of frames, has been opened up by studies of Kadison-Singer. This week's workshop explored the ideas presented here from a variety of different points of view, and created new links among the different fields in which the question has been investigated.