On equivalence of ℓ1 norm based basic sparse representation problems

The ℓ1 norm regularization problem, the ℓ1 norm minimization problem and the ℓ1 norm constraint problem are known collectively as the ℓ1 norm based Basic Sparse Representation Problems (BSRPs), and have been popular basic models in the field of signal processing and machine learning. The equivalence of the above three problems is one of the crucial bases for the corresponding algorithms design. However, to the best our knowledge, this equivalence issue has not been addressed appropriately in the existing literature. In this paper, we will give a rigorous proof of the equivalence of the three ℓ1 norm based BSRPs in the case when the dictionary is an overcomplete and row full rank matrix.