Thanh T Nguyen
email: thi-thanh.nguyen@univ-lorraine.fr

Charles Soussen
email: charles.soussen@centralesupelec.fr

Jérôme Idier
email: jerome.idier@ls2n.fr

El-Hadi Djermoune
email: el-hadi.djermoune@univ-lorraine.fr

NP-hardness of 0 minimization problems: revision and extension to the non-negative setting

Sparse approximation arises in many applications and often leads to a constrained or penalized 0 minimization problem, which was proved to be NP-hard. This paper proposes a revision of existing analyses of NPhardness of the penalized 0 problem and it introduces a new proof adapted from Natarajan's construction (1995). Moreover, we prove that 0 minimization problems with nonnegativity constraints are also NP-hard.

I. INTRODUCTION

Sparse approximation appears in a wide range of applications, especially in signal processing, image processing and compressed sensing [START_REF] Elad | Sparse and redundant representations: From theory to applications in signal and image processing[END_REF]. Given a signal data y ∈ R m and a dictionary A of size m×n, the aim is to find a signal x ∈ R n that gives the best approximation y ≈ Ax and has the fewest non-zero coefficients (i.e., sparsest solution). This task leads to solving one of the following constrained or penalized 0 minimization problems:

min y-Ax 2≤ x 0 ( 0 C) min x 0≤K y -Ax 2 2 ( 0 C ) min x y -Ax 2 2 + λ x 0 ( 0 P )
in which , K and λ are positive quantities related to the noise standard deviation, the sparsity level and regularization strength, respectively. Letters C and P respectively indicate that the problem is constrained or penalized. Depending on application, the appropriate statement will be addressed. It is noteworthy that n and K often depend on m when one considers the size of problem. ( 0 C) and ( 0 C ) are well known to be NP-hard [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF][START_REF] Davis | Adaptive greedy approximations[END_REF]. The NPhardness of ( 0 P ) was claimed to be a particular case of more general complexity analyses in [START_REF] Chen | Complexity of unconstrained l2-lp minimization[END_REF][START_REF] Huo | Complexity of penalized likelihood estimation[END_REF]. However, we point out that these complexity analyses do not rigorously apply to ( 0 P ) as claimed. In this paper, we justify the complexity analyses in [START_REF] Chen | Complexity of unconstrained l2-lp minimization[END_REF][START_REF] Huo | Complexity of penalized likelihood estimation[END_REF] do not apply to problem ( 0 P ), and we provide a new proof for the NP-hardness of ( 0 P ) adapted from Natarajan's construction [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF].

In several applications such as geoscience and remote sensing [START_REF] Iordache | Sparse unmixing of hyperspectral data[END_REF][START_REF] Esser | A method for finding structured sparse solutions to nonnegative least squares problems with applications[END_REF], audio [START_REF] Virtanen | Active-set Newton algorithm for overcomplete non-negative representations of audio[END_REF], chemometrics [START_REF] Bro | A fast non-negativity-constrained least squares algorithm[END_REF] and computed tomography [START_REF] Petra | Average case recovery analysis of tomographic compressive sensing[END_REF], the signal or image of interest is nonnegative. In such contexts, one often addresses a minimization problem with both sparsity and non-negativity constraints [START_REF] Petra | Average case recovery analysis of tomographic compressive sensing[END_REF][START_REF] Hoyer | Non-negative matrix factorization with sparseness constraints[END_REF][START_REF] Rapin | Sparse and nonnegative BSS for noisy data[END_REF]. Adding non-negativity constraints to 0 minimization problems yields the following problems:

min x≥0, y-Ax 2≤ x 0 ( 0 C+) min x≥0, x 0 ≤K y -Ax 2 2 ( 0 C +) min x≥0 y -Ax 2 2 + λ x 0 ( 0 P +)
Several papers address non-negative 0 minimization problems in the literature (see, e.g., [START_REF] Bruckstein | On the uniqueness of nonnegative sparse solutions to underdetermined systems of equation[END_REF][START_REF] Peharz | Sparse nonnegative matrix factorization with l0 constraints[END_REF][START_REF] Yaghoobi | Fast non-negative orthogonal matching pursuit[END_REF][START_REF] Wang | Cone-based joint sparse modelling for hyperspectral image classification[END_REF]). However, to the best of our knowledge, the complexity of these problems has not been addressed yet, the question of their NPhardness being still open. Here we show that these problems are NP-hard and the proof can be derived from the NP-hardness of 0 minimization problems. The rest of paper is organized as follows. In Section II, we discuss the issues related to NP-hardness of ( 0 P ) in existing analyses and we present our proof. In Section III, we discuss about the NP-hardness of non-negative 0 minimization problems. We draw some conclusions in Section IV.

II. HARDNESS OF 0 MINIMIZATION PROBLEMS

A. Background on constrained 0 minimization problems

Let us recall that an NP-complete problem is a problem in NP to which any other problem in NP can be reduced in polynomial time. Thus NP-complete problems are identified as the hardest problems in NP. An NPcomplete problem is strongly NP-complete if it remains NP-complete when all of its numerical parameters are bounded by a polynomial in the length of the input. NP-hard problems are at least as hard as NP-complete problems. However, NP-hard problems do not need to be in NP and do not need to be decision problems. Formally, a problem is NP-hard (respectively, strongly NP-hard) if a NP-complete (respectively, strongly NPcomplete) problem can be reduced in polynomial time to it. The reader is referred to [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF][START_REF] Leeuwen | Handbook of theoretical computer science[END_REF] for more information on this topic.

In the literature, problem ( 0 C), called SAS in [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF], is well known to be NP-hard [2, Theorem 1]. The NPhardness of ( 0 C) is a valuable extension of an earlier result: the problem of minimum weight solution to linear equations (equivalent to ( 0 C) with = 0) is NP-hard [17, p. 246]. Davis et al. proved that ( 0 C ), called M -optimal approximation in [START_REF] Davis | Adaptive greedy approximations[END_REF], is NP-hard for any K < m [3, Theorem 2.1]. Both analyses of Natarajan and Davis were made by a polynomial time reduction from the "exact cover by 3-sets" problem 1 which is known to be NPcomplete [17, p. 221].

B. Existing analyses on penalized 0 minimization

In [START_REF] Chen | Complexity of unconstrained l2-lp minimization[END_REF][START_REF] Huo | Complexity of penalized likelihood estimation[END_REF], the NP-hardness of ( 0 P ) is deduced as a particular case of more general complexity analyses. However, it turns out that the latter do not apply to ( 0 P ), as explained hereafter. Chen et al. [START_REF] Chen | Complexity of unconstrained l2-lp minimization[END_REF] address the unconstrained qp minimization problem, defined by:

min x y -Ax q q + λ x p p ( q -p )
where λ > 0, q ≥ 1 and 0 ≤ p < 1. The authors showed that problem ( qp ) is NP-hard with any λ > 0, q ≥ 1 and 0 ≤ p < 1 [4, Theorem 3]. Obviously, ( 0 P ) is the case where q = 2 and p = 0. The proof was done by i) introducing an invertible transformation which scales any instance of problem ( qp ) to the problem ( qp ) with λ = 1/2, and ii) establishing a polynomial time reduction from the partition problem which is known to be NP-complete [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF] to the problem ( qp ) with λ = 1/2.

In other words, they showed that problem ( qp ) with λ = 1/2 is NP-hard and, because there exists an invertible transformation from any problem ( qp ) to the one with λ = 1/2, every problem ( qp ) is NP-hard. Similarly, they showed that ( qp ) is strongly NP-hard [4, Theorem 5] by a reduction from the 3-partition problem which is known to be strongly NP-hard [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. The invertible transform used in [START_REF] Chen | Complexity of unconstrained l2-lp minimization[END_REF] is defined by:

x = (2λ) 1/p x, Ã = (2λ) -1/p A. (1)
Unfortunately, (1) is not well-defined when p = 0. Therefore, [4, Theorems 3 and 5] do not apply to ( 0 P ) when λ = 1/2. Using a different approach, Huo and Chen's paper [START_REF] Huo | Complexity of penalized likelihood estimation[END_REF] addresses the penalized least-squares problem defined by:

min x y -Ax 2 2 + λ n i=1 φ(|x i |), (PLS)
where φ is a penalty function mapping non-negative values to non-negative values. The authors showed that (PLS) is NP-hard if the penalty function φ satisfies the following four conditions [5, Theorem 3.1]: C1. φ(0) = 0 and ∀ 0 ≤ τ 1 < τ 2 , φ(τ 1 ) ≤ φ(τ 2 ). C2. There exists τ 0 > 0 and a constant d > 0 such that

φ(τ ) ≥ φ(τ 0 ) -d(τ 0 -τ ) 2
1 The latter problem, denoted by X3C in [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF][START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF], is stated as follows: Given a set S and a collection C of 3-element subsets of S (called triplets), is there a subcollection of disjoint triplets that exactly covers S?

for every 0 ≤ τ < τ 0 . C3. For the aforementioned τ

0 , if τ 1 , τ 2 < τ 0 then φ(τ 1 ) + φ(τ 2 ) ≥ φ(τ 1 + τ 2 ). C4. For every 0 ≤ τ < τ 0 , φ(τ ) + φ(τ 0 -τ ) > φ(τ 0 ). (2)
The proof of [5, Theorem 3.1] is by a reduction from the NP-complete problem X3C to the decision version of (PLS); this leads to the NP-completeness of the decision version of (PLS) and so the NP-hardness of (PLS) [5, Appendix 1]. The authors claimed that the 0 penalty function satisfies conditions C1-C4 for τ 0 = d = 1. Therefore, the (PLS) problem with the 0 penalty function is NP-hard [5, Corollary 3.2]. Unfortunately, it turns out that the 0 penalty does not fulfill condition C4 as claimed. Indeed, for τ = 0 the strict inequality (2) becomes φ(0) > 0. Besides, in the proof [5, Appendix 1], the inputs of the decision problem are not guaranteed to have rational values. This might also violate the polynomiality of the reduction. Therefore, [5, Theorem 3.1] does not apply to ( 0 P ).

In [START_REF] Huo | Complexity of penalized likelihood estimation[END_REF], the authors also mention an alternate proof of NP-hardness of ( 0 P ) from Huo and Ni's earlier paper [START_REF] Huo | When do stepwise algorithms meet subset selection criteria?[END_REF] as a special case of their results. In this proof [START_REF] Huo | When do stepwise algorithms meet subset selection criteria?[END_REF]Appendix A.1], the relation between ( 0 P ) and ( 0 C) is established using the principle of Lagrange multiplier. More precisely, the authors introduce an instance of ( 0 C) in which is defined from the minimizer of ( 0 P ) and argue that solving ( 0 P ) is equivalent to solving the mentioned instance of ( 0 C), which is known to be NP-hard [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF]. There are a number of issues in the NP-hardness proof in [START_REF] Huo | When do stepwise algorithms meet subset selection criteria?[END_REF]. For instance, the proposed transformation between ( 0 P ) and ( 0 C) is not a polynomial time reduction. Besides, it is well known that ( 0 P ) and ( 0 C) are not equivalent [START_REF] Nikolova | Description of the minimizers of least squares regularized with 0 norm. Uniqueness of the global minimizer[END_REF].

C. New analysis on penalized 0 minimization problems

To prove that a problem T is NP-hard, one must establish a polynomial time reduction (briefly called reduction hereafter) from some known NP-hard or NP-complete problem to T [START_REF] Leeuwen | Handbook of theoretical computer science[END_REF]. Roughly speaking, the reduction from a problem T1 to another problem T2 implies that T1 is not harder than T2. Therefore, if there exists a reduction from T1 to T2 and if T1 is NP-hard, T2 must be NP-hard too. The NP-hardness proofs in [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF] and [START_REF] Davis | Adaptive greedy approximations[END_REF] use this principle. As an adaptation of Natarajan's construction, we prove the NP-hardness of ( 0 P ) using the same principle as follows.

Theorem II.1. Problem ( 0 P ) is NP-hard for 0 < λ < 3.

The proof is by a reduction from the known NPcomplete problem X3C to ( 0 P ). The proof contains three steps: (1) Construct an instance of ( 0 P ) from a given instance of X3C; (2) Construct a solution of ( 0 P ) from a solution of X3C; (3) Construct a solution of X3C from a solution of ( 0 P ).

1) Construction of an instance of ( 0 P ) from a given instance of X3C: Given an instance of X3C: S = {s 1 , s 2 , ..., s m } is a set of m elements. C is a collection of n triplets c j , 1 ≤ j ≤ n. Without loss of generality we can assume that m is a multiple of 3 since otherwise there is trivially no exact cover so no solution of X3C.

We now construct an instance of ( 0 P ). Let y =

[1, 1, ..., 1] T ∈ R m . Let A = (a ij ) 1≤i≤m,1≤j≤n where a ij = 1 if s i ∈ c j and a ij = 0 otherwise. Let λ ∈ Q, 0 < λ < 3. Let F (x) := y -Ax 2 2 + λ x 0 . (3)
2) Construction of a solution of ( 0 P ) from a solution of X3C: Assume that there is a subcollection of disjoint triplets Ĉ which exactly covers S. Let x * = [x * 1 , x * 2 , ..., x * n ] T where x * j = 1 if c j ∈ Ĉ and x * j = 0 otherwise. We will prove that x * is a solution of ( 0 P ).

Since Ĉ exactly covers S, | Ĉ| = m/3 and y = Ax * . Thus, x * 0 = m/3 and

F (x * ) = 0 + λ m 3 = λ m 3 .
Suppose that there exists x such that

F (x) < F (x * ) = λ m 3 . ( 4
)
Let us show that this leads to a contradiction. Since F (x) ≥ λ x 0 , from (4) we have x 0 < m/3. Therefore, we can rewrite x 0 = m/3 -q for some q ∈ N, 1 ≤ q < m/3. Note that Ax has m entries. Since the number of non-zero entries of Ax identifies with the number of elements s i recovered by the subcollection corresponding to x, this number cannot exceed 3 x 0 = m -3q. As a result, the number of zero entries of Ax must be between 3q and m. Since y is the all-one vector, y -Ax has at least 3q entries valued 1, which implies

y -Ax 2 2 ≥ 3q. (5)
Hence,

F (x) ≥ 3q + λ m 3 -q = λ m 3 + (3 -λ)q > λ m 3 , (6)
which contradicts (4). Therefore, x * is a solution of ( 0 P ).

3) Construction of a solution of X3C from a solution of ( 0 P ): Assume that x * is a solution of ( 0 P ). We will consider four cases as follows.

a) Case x * 0 > m/3: We deduce that X3C has no solution. Indeed, assume that Ĉ is an exact cover for S. Define x = [x 1 , x 2 , ..., x n ] T where x j = 1 if c j ∈ Ĉ and x i = 0 otherwise. Then we have

F (x) = λ m 3 < λ x * 0 ≤ F (x * )
which contradicts the fact that x * is a solution of ( 0 P ). b) Case x * 0 < m/3: We deduce that X3C has no solution. Indeed, assume that Ĉ is an exact cover for S. Let x = [x 1 , x 2 , ..., x n ] T where x j = 1 if c j ∈ Ĉ and x i = 0 otherwise. Then we have F (x) = λ m 3 . Since x * 0 < m/3, we can write x * 0 = m/3 -q for some q ∈ N and 1 ≤ q < m/3. Similar to (6), we have

F (x * ) > λ m 3 . Since F (x) = λ m 3
, we obtain F (x * ) > F (x) which contradicts the fact that x * is a solution of ( 0 P ). c) Case where x * 0 = m/3 and y = Ax * : We deduce that X3C has no solution. Indeed, assume that Ĉ is an exact cover for S. Define x = [x 1 , x 2 , ..., x n ] T where x j = 1 if c j ∈ Ĉ and x i = 0 otherwise. Then we have

F (x) = λ m 3 < y -Ax * 2 2 + λ x * 0 = F (x * )
which contradicts the fact that x * is a solution of ( 0 P ). d) Case where x * 0 = m/3 and y = Ax * : Let Ĉ be the collection of triplets c j such that the j th entry of x * is non-zero. Obviously, Ĉ is an exact cover for S so a solution of X3C.

Thus Theorem II.1 is proved.

It is notable that the proof above is also valid when F (x) := y -Ax p p + λ x 0 for any p ≥ 1. Indeed, one only needs to check whether (5) still holds when the 2 norm is replaced by the p norm with p ≥ 1. This is the case since y -Ax has at least 3q entries equal to 1. Therefore, we have the following generalization of Theorem II.1.

Theorem II.2. Problem min x y -Ax p p +λ x 0 is NPhard for p ≥ 1 and 0 < λ < 3.

III. HARDNESS OF NON-NEGATIVE 0 MINIMIZATION

PROBLEMS

The NP-hardness of non-negative 0 minimization problems is a consequence of NP-hard proofs of ( 0 C) [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF], ( 0 C ) [START_REF] Davis | Adaptive greedy approximations[END_REF] and ( 0 P ) (Theorem II.1). Indeed, all these proofs consist in a reduction from X3C and the solution that established equivalence is binary. Therefore, the additional non-negativity constraints do not change the validity of these proofs. In other words, one can repeat the same proofs as in [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF][START_REF] Davis | Adaptive greedy approximations[END_REF] and that of Theorem II.1 for the corresponding non-negative 0 minimization problems ( 0 C+), ( 0 C +) and ( 0 P +). Another way to prove the NP-hardness of non-negative 0 minimization problems is by a reduction from the corresponding 0 minimization problems which are known to be NP-hard. In this reduction, the instance of non-negative problems is defined by

ỹ = y, Ã = [A, -A], x = x + x -
where x + = max{x, 0}, x -= max{-x, 0}. Naturally, by this construction, one gets x ≥ 0, x 0 = x 0 and Ãx = Ax. The proofs (skipped for brevity) contain three steps similar to that of Theorem II.1. Therefore, we can state the following theorem without proof.

Theorem III.1. ( 0 C+), ( 0 C +) are NP-hard. The same for ( 0 P +) with 0 < λ < 3.

In the same spirit and using the same argument as at the end of Section II-C one can directly extend Theorem II.2 to the non-negative setting.

Theorem III.2. Problem min x≥0 y -Ax p p + λ x 0 is NP-hard for p ≥ 1 and 0 < λ < 3.

IV. CONCLUSION

NP-hardness of penalized 0 minimization problems cannot be deduced from previous complexity analyses, as stated in [START_REF] Chen | Complexity of unconstrained l2-lp minimization[END_REF][START_REF] Huo | Complexity of penalized likelihood estimation[END_REF]. Here, we introduced a new proof of NP-hardness of penalized 0 minimization problems when the regularization parameter λ is smaller than 3, by an adaptation of Natarajan's construction [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF], while the case λ ≥ 3 is still open. Besides, we showed that the 0 minimization problems with non-negative constraints are also NP-hard.

This work can be extended in several directions. For instance, researchers interested in what makes NP-hard problems even harder might be interested in the strong NPhardness of the aforementioned optimization problems. As it is widely believed that X3C is strongly NP-complete, one might easily deduce the strong NP-hardness of ( 0 C), ( 0 C ) and other problems which are reduced from X3C. However, to the best of our knowledge, X3C is only proved to be NP-complete [17, pp. 53, 221] and the strong NPcompleteness has not been rigorously shown yet. Therefore, we believe that the question of strong NP-hardness of (non-negative) 0 minimization problems is not trivial and needs more work in future.

Besides, as (non-negative) 0 minimization problems are NP-hard, it would be interesting to know if the associated decision problems are in NP (so being NP-complete). Let us consider the decision problem associated with ( 0 C): given y ∈ Q m , A ∈ Q m×n , a positive rational number and a positive integer K, does there exist x ∈ R n such that y -Ax 2 ≤ and x 0 ≤ K? This decision problem should be in NP since if one can guess a rational solution x, it can be verified in polynomial time if y -Ax 2 ≤ and x 0 ≤ K. Similarly, we conjecture that the decision version of other optimization problems mentioned in the paper are in NP as well.

Another perspective is the approximability of aforementioned NP-hard problems. The hardness of approximating ( 0 C) was discussed in [START_REF] Amaldi | On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems[END_REF][START_REF] Tillmann | On the computational intractability of exact and approximate dictionary learning[END_REF]. It was shown that approximating ( 0 C) to within a factor of (1-α) ln(n), 0 < α < 1 is NP-hard [START_REF] Tillmann | On the computational intractability of exact and approximate dictionary learning[END_REF]. Examining whether similar results can be obtained on other NP-hard problems presented in the paper would require more involved theoretical analysis, which is left for future work.

V. ACKNOWLEDGMENT

The authors would like to thank M. Mongeau (ENAC, Toulouse) for helpful discussions and two anonymous reviewers for constructive and valuable comments.

This work was supported by the project ANR BECOSE (ANR-15-CE23-0021).

This work was carried out in part while T. T. Nguyen was visiting L2S during the academic years 2017-2019.