Sparse Optimization Theory and Methods

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 ...