Analysis of the equivalence relationship between ... formula ...-minimization and ... formula ...-minimization

摘要

In signal processing theory, l0-minimization is an important mathematical model. Unfortunately, l0-minimization is actually NP-hard. The most widely studied approach to this NP-hard problem is based on solving lp-minimization (0  p ≤ 1). In this paper, we present an analytic expression of p^∗(A, b), which is formulated by the dimension of the matrix A ∈ ℝ^m×n, the eigenvalue of the matrix A^TA, and the vector b ∈ ℝ^m, such that every k-sparse vector x ∈ ℝⁿ can be exactly recovered via lp-minimization whenever 0  p  p^∗(A, b), that is, lp-minimization is equivalent to l0-minimization whenever 0  p  p^∗(A, b). The superiority of our results is that the analytic expression and each its part can be easily calculated. Finally, we give two examples to confirm the validity of our conclusions.