Finite Frames

To date, frames have established themselves as a standard notion in applied mathematics, computer science, and engineering as a means to derive redundant, yet stable decompositions of a signal for analysis or transmission, while also promoting sparse expansions. The reconstruction procedure is then based on one of the associated dual frames, which—in the case of a Parseval frame—can be chosen to be the frame itself. In this chapter, we provide a comprehensive review of the basics of finite frame theory upon which the subsequent chapters are based. After recalling some background information on Hilbert space theory and operator theory, we introduce the notion of a frame along with some crucial properties and construction procedures. Then we discuss algorithmic aspects such as basic reconstruction algorithms and present brief introductions to diverse applications and extensions of frames. The subsequent chapters of this book will then extend key topics in many intriguing directions.

Broadly speaking, frame theory is the study of how to produce well-conditioned frame operators, often subject to nonlinear application-motivated restrictions on the frame vectors themselves. In this chapter, we focus on one particularly well-studied type of restriction: having frame vectors of prescribed lengths. We discuss two methods for iteratively constructing such frames. The first method, called Spectral Tetris, produces special examples of such frames, and only works in certain cases. The second method combines the idea behind Spectral Tetris with the classical theory of majorization; this method can build any such frame in terms of a sequence of interlacing spectra, called eigensteps.

Interesting families of finite frames often admit characterizations in terms of algebraic constraints, and thus it is not entirely surprising that powerful results in finite frame theory can be obtained by utilizing tools from algebraic geometry. In this chapter, our goal is to demonstrate the power of these techniques. First, we demonstrate that algebro-geometric ideas can be used to explicitly construct local coordinate systems that reflect intuitive degrees of freedom within spaces of finite unit norm tight frames (and more general spaces), and that optimal frames can be characterized by useful algebraic conditions. In particular, we construct locally well-defined real-analytic coordinate systems on spaces of finite unit norm tight frames, and we demonstrate that many types of optimal Parseval frames are dense and that further optimality can be discovered through embeddings that naturally arise in algebraic geometry.

The prototypical example of a tight frame, the Mercedes-Benz frame can be obtained as the orbit of a single vector under the action of the group generated by rotation by \(\frac{2\pi}{3}\), or the dihedral group of symmetries of the triangle. Many frames used in applications are constructed in this way, often as the orbit of a single vector (akin to a mother wavelet). Most notable are the harmonic frames (finite abelian groups) used in signal analysis, and the equiangular Heisenberg frames, or SIC–POVMs (discrete Heisenberg group) used in quantum information theory. Other examples include tight frames of multivariate orthogonal polynomials sharing symmetries of the weight function, and the highly symmetric tight frames which can be viewed as the vertices of highly regular polytopes. We will describe the basic theory of such group frames, and some of the constructions that have been found so far.

Gabor frames have been extensively studied in time-frequency analysis over the last 30 years. They are commonly used in science and engineering to synthesize signals from, or to decompose signals into, building blocks which are localized in time and frequency. This chapter contains a basic and self-contained introduction to Gabor frames on finite-dimensional complex vector spaces. In this setting, we give elementary proofs of the central results on Gabor frames in the greatest possible generality; that is, we consider Gabor frames corresponding to lattices in arbitrary finite Abelian groups. In the second half of this chapter, we review recent results on the geometry of Gabor systems in finite dimensions: the linear independence of subsets of its members, their mutual coherence, and the restricted isometry property for such systems. We apply these results to the recovery of sparse signals, and discuss open questions on the geometry of finite-dimensional Gabor systems.

This chapter reviews the development of finite frames as codes for erasures and additive noise. These types of errors typically occur when analog signals are transmitted in an unreliable environment. The use of frames allows one to recover the signal with controllable accuracy from part of the encoded, noisy data. While linear binary codes have a long history in information theory, frames as codes over the real or complex numbers have only been examined since the 1980s. In the encoding process, a vector in a finite-dimensional real or complex Hilbert space is mapped to the sequence of its inner products with frame vectors. An erasure occurs when part of these frame coefficients is no longer accessible after the transmission. Additive noise can arise from the encoding process, such as when coefficients are rounded, or from the transmission. This chapter covers two of the most popular recovery algorithms: blind reconstruction, where missing coefficients are set to zero, and active error correction, which aims to recover the signal perfectly based on the known coefficients. The erasures can be modeled as either having a deterministic or a random occurrence pattern. In the deterministic regime it has been customary to optimize the frame performance in the worst-case scenario. Optimality for a small number of erasures then leads to geometric conditions such as the class of equiangular tight frames. Random erasure models are often used in conjunction with performance measures based on averaged reconstruction errors, such as the mean-squared error. Frames as codes for erasures are also closely related to recent results on sparse recovery. Finally, fusion frames and packet erasures introduce an additional structure which imposes constraints on the construction of optimal frames.

Frames are a tool for providing stable and robust signal representations in a wide variety of pure and applied settings. Frame theory uses a set of frame vectors to discretely represent a signal in terms of its associated collection of frame coefficients. Dual frames and frame expansions allow one to reconstruct a signal from its frame coefficients—the use of redundant or overcomplete frames ensures that this process is robust against noise and other forms of data loss. Although frame expansions provide discrete signal decompositions, the frame coefficients generally take on a continuous range of values and must also undergo a lossy step to discretize their amplitudes so that they may be amenable to digital processing and storage. This analog-to-digital conversion step is known as quantization. We shall give a survey of quantization for the important practical case of finite frames and shall give particular emphasis to the class of Sigma-Delta algorithms and the role of noncanonical dual frame reconstruction.

Over the last decade, considerable progress has been made toward developing new signal processing methods to manage the deluge of data caused by advances in sensing, imaging, storage, and computing technologies. Most of these methods are based on a simple but fundamental observation: high-dimensional data sets are typically highly redundant and live on low-dimensional manifolds or subspaces. This means that the collected data can often be represented in a sparse or parsimonious way in a suitably selected finite frame. This observation has also led to the development of a new sensing paradigm, called compressed sensing, which shows that high-dimensional data sets can often be reconstructed, with high fidelity, from only a small number of measurements. Finite frames play a central role in the design and analysis of both sparse representations and compressed sensing methods. In this chapter, we highlight this role primarily in the context of compressed sensing for estimation, recovery, support detection, regression, and detection of sparse signals. The recurring theme is that frames with small spectral norm and/or small worst-case coherence, average coherence, or sum coherence are well suited for making measurements of sparse signals.

Filter banks are fundamental tools of signal and image processing. A filter is a linear operator which computes the inner products of an input signal with all translates of a fixed function. In a filter bank, several filters are applied to the input, and each of the resulting signals is then downsampled. Such operators are closely related to frames, which consist of equally spaced translates of a fixed set of functions. In this chapter, we highlight the rich connections between frame theory and filter banks. We begin with the algebraic properties of related operations, such as translation, convolution, downsampling, the discrete Fourier transform, and the discrete Z-transform. We then discuss how basic frame concepts, such as frame analysis and synthesis operators, carry over to the filter bank setting. The basic theory culminates with the representation of a filter bank’s synthesis operator in terms of its polyphase matrix. This polyphase representation greatly simplifies the process of constructing a filter bank frame with a given set of properties. Indeed, we use this representation to better understand the special case in which the filters are modulations of each other, namely Gabor frames.

We now know that some of the basic open problems in frame theory are equivalent to fundamental open problems in a dozen areas of research in both pure and applied mathematics, engineering, and others. These problems include the 1959 Kadison–Singer problem in C ^∗-algebras, the paving conjecture in operator theory, the Bourgain–Tzafriri conjecture in Banach space theory, the Feichtinger conjecture and the R _ϵ -conjecture in frame theory, and many more. In this chapter we will show these equivalences among others. We will also consider a slight weakening of the Kadison–Singer problem called the Sundberg problem. Then we will look at the recent advances on another deep problem in frame theory called the Paulsen problem. In particular, we will see that this problem is also equivalent to a fundamental open problem in operator theory. Namely, if a projection on a finite dimensional Hilbert space has a nearly constant diagonal, how close is it to a constant diagonal projection?

Finite frames can be viewed as mass points distributed in N-dimensional Euclidean space. As such they form a subclass of a larger and rich class of probability measures that we call probabilistic frames. We derive the basic properties of probabilistic frames, and we characterize one of their subclasses in terms of minimizers of some appropriate potential function. In addition, we survey a range of areas where probabilistic frames, albeit under different names, appear. These areas include directional statistics, the geometry of convex bodies, and the theory of t-designs.

Novel technological advances have significantly increased the demand to model applications requiring distributed processing. Frames are, however, too restrictive for such applications, wherefore it was necessary to go beyond classical frame theory. Fusion frames, which can be regarded as frames of subspaces, satisfy exactly those needs. They analyze signals by projecting them onto multidimensional subspaces, in contrast to frames which consider only one-dimensional projections. This chapter serves as an introduction to and a survey about this exciting area of research as well as a reference for the state of the art of this research field.