Absolute Lower Bound Theory for Nonzero Entries in Solutions of L2-Lp Minimization
发布时间：2025-04-30
点击次数：
- 发布时间：
- 2025-04-30
- 论文名称：
- Absolute Lower Bound Theory for Nonzero Entries in Solutions of L2-Lp Minimization
- 发表刊物：
- SIAM Journal on Scientific Computing
- 摘要：
- Recently, variable selection and sparse
reconstruction are solved by finding an optimal solution of a
minimization model where the objective function is the sum of a
data-fitting term in $ell_2$ norm and a regularization term in
$ell_p$ norm $(0<p<1)$. Since it is a non-convex model, most
algorithms for solving the problem can only provide an approximate
local optimal solution, where nonzero entries in the solution cannot
be identified theoretically. In this paper, we establish lower
bounds for the absolute value of nonzero entries in every local
optimal solution of the model, which can be used to eliminate zero
entries precisely in any numerical solution. Therefore, we have
developed a lower bound theorem to classify zero and nonzero entries
in its every local solution. These lower bounds clearly show the
relationship between the sparsity of the solution and the choice of
the regularization parameter and norm, so that our theorem can be
used for selecting desired model parameters and norms. Furthermore,
we also develop error bounds for verifying accuracy of numerical
solutions of the $ell_2$-$ell_p$ minimization model. To
demonstrate applications of our theory, we propose an orthogonal
matching pursuit-smoothing gradient (OMP-SG) hybrid method for
solving the nonconvex, non-Lipschitz continuous $ell_2$-$ell_p$
minimization problem. Computational results show the effectiveness
of the lower bounds for identifying nonzero entries in numerical
solutions and the OMP-SG method for finding a high quality numerical
solution.
- 合写作者：
- Xiaojun Chen, Fengmin Xu, Yinyu Ye
- 卷号：
- 32 (13)
- 页面范围：
- pp. 2832-2852.
- 是否译文：
- 否
- 发表时间：
- 2010-05-05