ABSTRACT
The 1-minimization method cannot always solve an 0-minimization problem. In this chapter, we first discuss the condition under which the 0-and 1minimization problems are equivalent. This condition indicates that the uniqueness of the solution to an 0-minimization problem cannot guarantee that the problem can be solved by 1-minimization, and the multiplicity of the solutions to an 0-minimization problem cannot also prevent the problem from being solved by 1-minimization. It is the RSP of AT at a solution of the 0-minimization problem that determines whether the 0-minimization problem can be solved by 1-minimization. We also discuss the equivalence of 0minimization and weighted 1-minimization, and we prove that there exists a weight such that the solution of weighted 1-minimization coincides with that of 0-minimization. More importantly, we introduce the RSP-based uniform and non-uniform recovery theories for sparse vectors. The so-called RSP of order k of AT turns out to be a necessary and sufficient condition for every k-sparse vector to be exactly recovered by 1-minimization. As a result, this condition ensures strong equivalence between 0-and 1-minimization problems.
