Complexity of Unconstrained L_2-L_p Minimization

1 Introduction

• The model targets least-squares solutions with fewer nonzero entries, especially for underdetermined systems, while L0 regularization is difficult because of its discrete structure.The L2-Lp formulation has been studied in variable selection and sparse least-squares fitting for high-dimensional data.Source: §1 · pp. 1–2
• Although practical methods report encouraging computational results, they may not find a global minimizer, and no globally convergent algorithm guarantees one.The L2-Lp problem is nonconvex and non-Lipschitz for 0 < p < 1.Source: §1 · pp. 2–3
• Finding a global minimizer is strongly NP-hard for L2-Lp when 0 ≤ p < 1 and λ > 0, and the hardness extends to Lq-Lp for q ≥ 1.The paper identifies the computational complexity as an open question before establishing this result.Source: §1 · p. 2
• A sufficient choice of λ ensures desired sparsity for global or local minimizers when their objective value is below that of the all-zero solution.Under the condition, a local optimum is a sparse estimator for the original problem.Source: §1 · p. 2
• The Lq-Lp problem remains strongly NP-hard in its smoothed, Lipschitz-continuous form, so smoothing provides no computational-complexity advantage.The smoothed result applies for 0 < p < 1, q ≥ 1, λ > 0, and ε > 0.Source: §1 · p. 3
• For least-squares solutions with a targeted number of nonzeros, a local minimizer is likely to accomplish the same objective as a global minimizer.The paper also reports consistency with statistical findings and more specific bounds for choosing regularization parameters.Source: §1 · p. 3

2 Choosing the parameter λ for sparsity

• For sparse least-squares fitting, the approach controls minimizer support through λ, then fits using only variables retained in the minimizer.The aim is to keep the support at most k while avoiding the all-zero solution.Source: §2 · p. 3
• If λ ≥ β(k), every minimizer has fewer than k nonzero entries for k ≥ 2.The bound is a sufficient condition for the desired sparsity.Source: §2 · p. 3
• If λ ≥ β(1), the zero vector is the unique global minimizer.The paper identifies β(1) as a specific threshold for uniqueness.Source: §2 · pp. 3–4
• If Ax = b has a solution xc and λ ≤ ∥b∥2^p for some xc, every minimizer has at least one nonzero entry.Source: §2 · p. 3
• For small k, the authors suggest enumerating supports of size at most k, which they say can be done in strongly polynomial time in the problem dimensions.They suggest this may be preferable to choosing λ ≥ β(k) when k is a small constant such as 1 to 3.Source: §2 · p. 4
• If λ ≥ γ(k), any local minimizer with objective value at most fp(0) has fewer than k nonzero entries for k ≥ 2.Source: §2 · p. 4
• At k = 2, β(2) = 1; with λ = 1, every minimizer in the example has one nonzero entry, while λ ≥ 81/4 makes zero unique.Source: §2 · p. 5
• In the example, a positive third derivative rules out two nonzero first- and second-order candidates as local minima, supporting zero as the unique global minimizer.Source: §2 · p. 5

• The constrained Lp problem's hardness does not transfer directly: quadratic penalties are not exact, and constrained local minimizers need not be stationary points of L2-Lp.The section also notes that no λ > 0 makes a feasible solution of the constrained problem satisfy the first-order necessary condition for L2-Lp.Source: §3 · p. 6
• Theorem 3 first establishes NP-hardness for 0 ≤ p < 1, q ≥ 1, and λ > 0; the proof strategy then extends the result to strong NP-hardness.The section describes this two-stage proof approach explicitly.Source: §3 · p. 6
• The scalar function used in the reduction has a unique minimizer z*(p, q) on (0, 1], with minimum value c(p, q) < 1.Source: §3 · p. 6
• The reduction makes the constructed objective attain its lower bound exactly when the original partition instance has an equitable partition.The lower bound is n c(p, q), and equality is equivalent to an equitable partition.Source: §3 · pp. 7–8
• Theorem 5 states that minimization problem (5) is strongly NP-hard for any given 0 ≤ p < 1, q ≥ 1, and λ > 0.The proof gives a polynomial-time reduction from strongly NP-hard 3-partition.Source: §3 · p. 8
• The smoothed minimization problem is strongly NP-hard for every 0 < p < 1, q ≥ 1, λ > 0, and ǫ > 0.The reduction again uses 3-partition and characterizes solvability by attaining the constructed lower bound.Source: §3 · pp. 8–9

• Choosing λ ≥ γ(k), rather than λ ≥ β(k), guarantees the desired sparsity of a local minimizer, while either bound is proposed for the bridge-estimator setting.The section motivates the local-minimizer result after establishing the difficulty of finding a global minimizer.Source: §4 · pp. 9–10
• β(k) = k^-3/4(8m)^1/4||b||^3/2 and γ(k) = k^-1/2(16m)^1/4||b||^3/2.Source: §4 · p. 9
• For constant k, β(k) and γ(k) have the same order in m and ||b||, and a local minimizer in objective level set fp(0) suffices for the β(k) sparsity guarantee.The section reports no significant guaranteed sparsity difference between local and global minimizers in this case.Source: §4 · p. 9
• When k increases with m, a global minimizer is likely to be sparser than a local minimizer, with β(k)/γ(k) = O(k^-1/4).Source: §4 · p. 9
• Under λ = λm equal to β(k) or γ(k), any minimizer is likely to have fewer than k nonzero entries, and either choice could support consistency and oracle efficiency.Source: §4 · p. 10