A comparison of typical ℓp minimization algorithms

Recently, compressed sensing has been widely applied to various areas such as signal processing, machine learning, and pattern recognition. To find the sparse representation of a vector w.r.t. a dictionary, an ℓ1ℓ1 minimization problem, which is convex, is usually solved in order to overcome the computational difficulty. However, to guarantee that the ℓ1ℓ1 minimizer is close to the sparsest solution, strong incoherence conditions should be imposed. In comparison, nonconvex minimization problems such as those with the ℓp(0