Analysis of the equivalence relationship between [Formula: see text] -minimization and [Formula: see text] -minimization

In signal processing theory, [Formula: see text] -minimization is an important mathematical model. Unfortunately, [Formula: see text] -minimization is actually NP-hard. The most widely studied approach to this NP-hard problem is based on solving [Formula: see text] -minimization ([Formula: see text] ). In this paper, we present an analytic expression of [Formula: see text] , which is formulated by the dimension of the matrix [Formula: see text] , the eigenvalue of the matrix [Formula: see text] , and the vector [Formula: see text] , such that every k-sparse vector [Formula: see text] can be exactly recovered via [Formula: see text] -minimization whenever [Formula: see text] , that is, [Formula: see text] -minimization is equivalent to [Formula: see text] -minimization whenever [Formula: see text] . 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.