TL;DR
This paper investigates the computational complexity of $L_2$-$L_p$ minimization, a popular technique for sparse signal recovery and variable selection. The authors prove that finding a global minimizer for this problem is strongly NP-hard, even for smoothed versions. However, they also provide theoretical bounds that guarantee sparsity for local minimizers when regularization parameters are chosen carefully.
What Problem Does This Paper Address?
In many real-world applications, such as signal processing and machine learning, we encounter situations where we need to find a sparse solution to an underdetermined system of linear equations. This means finding a solution vector $x$ that has as few non-zero entries as possible. A common approach is to minimize an objective function that balances fitting the data (e.g., minimizing $\|Ax - b\|^2_2$) with a penalty on the number of non-zero elements in $x$.
Traditionally, the $L_0$ norm (counting non-zero elements) was used, but it's computationally intractable. The $L_1$ norm (Lasso) is a convex relaxation that is computationally tractable and has proven very successful. However, for certain applications, particularly in high-dimensional settings, the $L_1$ norm might not induce sufficient sparsity. This has led to interest in non-convex regularizers like the $L_p$ norm with $p \in [0, 1)$. The $L_2$-$L_p$ minimization problem, specifically minimizing $\|Ax - b\|^2_2 + \lambda \|x\|^p_p$, aims to leverage the attractive sparsity-inducing properties of the $L_p$ norm while maintaining a least-squares fit.
Despite its theoretical appeal and practical use, the computational complexity of finding a global minimizer for the $L_2$-$L_p$ problem remained an open question. This paper aims to address this by rigorously analyzing the problem's hardness and providing conditions under which useful, sparse solutions can be found.
Methods
The paper employs a combination of theoretical analysis and proof techniques from computational complexity theory.
- NP-Hardness Proofs: The core of the paper's contribution lies in proving that the $L_q$-$L_p$ minimization problem (a generalization of $L_2$-$L_p$) is strongly NP-hard. This is achieved through polynomial-time reductions from known NP-hard problems, specifically the partition problem and the 3-partition problem. These reductions transform instances of these known hard problems into instances of the $L_q$-$L_p$ minimization problem, demonstrating that if the latter could be solved efficiently, so could the former.
- Smoothed Versions: The authors extend their NP-hardness results to smoothed versions of the $L_q$-$L_p$ problem. This is significant because smoothing often makes optimization problems easier to handle. The fact that even smoothed versions remain NP-hard highlights the inherent difficulty of the problem.
- Sparsity Bounds: On the positive side, the paper derives theoretical bounds, denoted by $\beta(k)$ and $\gamma(k)$, on the regularization parameter $\lambda$. These bounds provide sufficient conditions on $\lambda$ to guarantee that any global or local minimizer of the $L_2$-$L_p$ problem will have at most $k$ non-zero entries. This is crucial for practical applications where a specific level of sparsity is desired.
Datasets
Not discussed in the paper. The paper focuses on theoretical complexity and general properties of the optimization problem, rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Inherent Hardness: The $L_2$-$L_p$ minimization problem, even with $p \in [0,1)$ and $q \ge 1$, is fundamentally hard to solve globally. This means that no efficient (polynomial-time) algorithm is likely to exist for finding the absolute best sparse solution in all cases.
- Smoothing Offers No Escape: The NP-hardness extends to smoothed versions of the problem. This is a strong result, suggesting that simply making the objective function Lipschitz continuous doesn't alleviate the computational burden of finding a global optimum.
- Local Minima Can Be Good: Despite the global hardness, the paper provides conditions under which local minimizers are guaranteed to be sparse. This is a critical insight for practical algorithms, as finding local minima is often more feasible than finding global ones.
- Parameter Choice is Key: The derived bounds $\beta(k)$ and $\gamma(k)$ offer concrete guidance on how to choose the regularization parameter $\lambda$. Selecting $\lambda$ based on these bounds can ensure that the resulting minimizer (even if local) exhibits the desired sparsity.
- Bridge Estimators: The paper connects its findings to "bridge estimators," which are known for their desirable statistical properties. The theoretical bounds are shown to align with conditions required for the consistency and oracle efficiency of these estimators.
Key Results
- Strong NP-Hardness: The $L_q$-$L_p$ minimization problem is proven to be strongly NP-hard for any $p \in [0,1)$, $q \ge 1$, and $\lambda > 0$. This includes its smoothed version.
- Sparsity Guarantees:
- If $\lambda \ge \beta(k)$, any minimizer of the $L_2$-$L_p$ problem has at most $k$ non-zero entries (for $k \ge 2$).
- If $\lambda \ge \gamma(k)$, any local minimizer within the level set $\{x : \|Ax - b\|^2_2 \le \|b\|^2_2\}$ has at most $k$ non-zero entries (for $k \ge 2$).
- Unique Global Minimizer: A specific bound $\beta(1)$ is established, such that if $\lambda > \beta(1)$, then $x=0$ is the unique global minimizer of the $L_2$-$L_p$ problem.
Limitations and Future Work
- Global Minimization Hardness: The primary limitation is the NP-hardness of finding a global minimizer. This implies that for large-scale problems, exact solutions might be computationally infeasible.
- Worst-Case Complexity: The NP-hardness results are worst-case complexities. In practice, many instances might be solvable efficiently, or approximate solutions might be sufficient.
- Future Work: The paper suggests that while finding a global minimizer is hard, the derived bounds for sparsity of local minimizers are promising for practical applications. Future work could focus on developing efficient algorithms that can reliably find these sparse local minimizers or exploring approximation algorithms. The paper also hints that for very small $k$ (e.g., 1 to 3), enumerating combinations might be a viable strategy.
Summary updated