Sparse Optimization Theory and Methods

Yun-Bin Zhao

• Publisher: CRC Press
• Year: 2018
• ISBN:
  9781351624145
• Edition: 1
• Topic: Business
• Subtopic: Operations
• Index: Business

Seeking sparse solutions of underdetermined linear systems is required in many areas of engineering and science such as signal and image processing. The efficient sparse representation becomes central in various big or high-dimensional data processing, yielding fruitful theoretical and realistic results in these fields. The mathematical optimization plays a fundamentally important role in the development of these results and acts as the mainstream numerical algorithms for the sparsity-seeking problems arising from big-data processing, compressed sensing, statistical learning, computer vision, and so on. This has attracted the interest of many researchers at the interface of engineering, mathematics and computer science.

Sparse Optimization Theory and Methods presents the state of the art in theory and algorithms for signal recovery under the sparsity assumption. The up-to-date uniqueness conditions for the sparsest solution of underdertemined linear systems are described. The results for sparse signal recovery under the matrix property called range space property (RSP) are introduced, which is a deep and mild condition for the sparse signal to be recovered by convex optimization methods. This framework is generalized to 1-bit compressed sensing, leading to a novel sign recovery theory in this area. Two efficient sparsity-seeking algorithms, reweighted l1-minimization in primal space and the algorithm based on complementary slackness property, are presented. The theoretical efficiency of these algorithms is rigorously analysed in this book. Under the RSP assumption, the author also provides a novel and unified stability analysis for several popular optimization methods for sparse signal recovery, including l1-mininization, Dantzig selector and LASSO. This book incorporates recent development and the author's latest research in the field that have not appeared in other books.

Chapter 1

Uniqueness of the Sparsest Solution of Linear Systems

1.1 Introduction

Let x ∈ ℝⁿ be an unknown vector which cannot be measured directly. To recover (reconstruct) such a vector, an obvious step is to take linear measurements of the form y := Ax, where A is a given measurement matrix. Then, solve such a system of linear equations to obtain a solution x̂. When the number of measurements is large enough, the reconstructed solution x̂ would be equal to x, leading to the success of recovery of x. Compressed sensing is using a small number of measurements (as small as possible) to recover a wide range of signals. To expect the number of measurements being lower than the signal length, the measurement matrix A ∈ ℝ^m×n (also called sensing matrix) should have less rows than columns, i.e., m < n. This renders the linear system y = Az underdetermined in the sense that it has infinitely many solutions. In this case, x is not a unique vector complying with the same measurement vector y, and hence it is generally impossible to recover the vector x from the linear measurements y := Ax unless further information on x is available.

Practical signals are usually structured, and the most useful signal structure is sparsity. Thus, a fundamental hypothesis in compressed sensing is that the unkno...