The sparse linear reconstruction problem is a core problem in signal processing which aims to recover sparse solutions to linear systems. The original problem regularized by the total number of nonzero components (also known as \(L_0\) regularization) is well-known to be NP-hard. The relaxation of the \(L_0\) regularization by using the \(L_1\) norm offers a convex reformulation, but is only exact under certain conditions (e.g., restricted isometry property) which might be NP-hard to verify. To overcome the computational hardness of the \(L_0\) regularization problem while providing tighter results than the \(L_1\) relaxation, several alternate optimization problems have been proposed to find sparse solutions. One such problem is the \(L_1-L_2\) minimization problem, which is to minimize the difference of the \(L_1\) and \(L_2\) norms subject to linear constraints. This paper proves that solving the \(L_1-L_2\) minimization problem is NP-hard. Specifically, we prove that it is NP-hard to minimize the \(L_1-L_2\) regularization function subject to linear constraints. Moreover, it is also NP-hard to solve the unconstrained formulation that minimizes the sum of a least squares term and the \(L_1-L_2\) regularization function. Furthermore, restricting the feasible set to a smaller one by adding nonnegative constraints does not change the NP-hardness nature of the problems.
