As engineering and the sciences become increasingly data- and computation-driven, the role of optimization has expanded to touch almost every stage of the data analysis pipeline, from the signal and data acquisition to modeling, analysis, and prediction.

In this chapter, we present an application of compressive sensing to a crucial problem in modern wireless (radio) communication: How can cognitive radios efficiently identify available spectrum? We will see that this problem can be cast as one of recovering the support of a sparse signal, in the presence of noise. We will see how the methods and algorithms described in this book will allow us to break theoretical limits of conventional approaches, and, once properly implemented in hardware, they can significantly advance the state of the art, by enabling better tradeoffs between energy consumption and scan time. Besides its practical importance, this application is very interesting as it is kind of dual to the situation in the magnetic resonance imaging that we studied in the preceding chapter. In MRI, the measurements are the Fourier transform of the image of interest and the sparse patterns are in the image domain; whereas for spectrum sensing, the sparse patterns are in the Fourier domain which we do not measure directly.

In the previous chapter, we saw many problems for which the goal is to find a sparse solution to an underdetermined linear system of equations y = Ax. This problem is NP-hard in general. However, we also observed that certain well-structured instances can be solved efficiently: in experiments, when y = Axo and xo was sufficiently sparse, tractable ℓ1 minimization

In this chapter, we will branch out from sparse signals to a broader class of models: the low-rank matrices. Similar to the problem of recovering sparse signals, we consider how to recover a matrix

In human perception, the role of sparse representation has been studied extensively. As we have alluded to in the Introduction, Chapter 1, investigators in neuroscience have revealed that in both low-level and mid-level human vision, many neurons in the visual pathway are selective for recognizing a variety of specific stimuli, such as color, texture, orientation, scale, and even view-tuned object images [OF97, Ser06]. Considering these neurons to form an overcomplete dictionary of base signal elements at each visual stage, the firing of the neurons with respect to a given input image is typically highly sparse.

In the first five chapters of this book, we introduced two main families of low-dimensional models for high-dimensional data: sparse models and low-rank models. In Chapter 5, we saw how we could combine these basic models to accommodate data matrices that are superpositions of sparse and low-rank matrices. This generalization allowed us to model richer classes of data, including data containing erroneous observations. In this chapter, we further generalize these basic models to a situation in which the object of interest consists of a superposition of a few elements from some set of “atoms” (Section 6.1). This construction is general enough to include all of the models discussed so far, as well as several other models of practical importance. With this general idea in mind, we then discuss unified approaches to studying the power of low-dimensional signal models for estimation, measured in terms of the number of measurements needed for exact recovery or recovery with sparse errors (Section 6.2). These analyses generalize and unify the ideas developed over the earlier chapters, and offer definitive results on the power of convex relaxation. Finally, in Section 6.3, we discuss limitations of convex relaxation, which in some situations will force us to consider nonconvex alternatives, to be studied in later chapters.

The problem of identifying low-dimensional structure of signals or data in high-dimensional spaces is one of the most fundamental problems that, through a long history, interweaves many engineering and mathematical fields such as system theory, pattern recognition, signal processing, machine learning, and statistics.

In this chapter, we consider a form of low-dimensional structure that arises in many applications in scientific data analysis: we consider datasets consisting of a few basic motifs, repeated at different locations in space and/or time.