Absolute Lower Bound Theory for Nonzero Entries in Solutions of L2-Lp Minimization
Release Time:2025-04-30
Hits:
- Date:
- 2025-04-30
- Title of Paper:
- Absolute Lower Bound Theory for Nonzero Entries in Solutions of L2-Lp Minimization
- Journal:
- SIAM Journal on Scientific Computing
- Summary:
- 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.
- Co-author:
- Xiaojun Chen, Fengmin Xu, Yinyu Ye
- Volume:
- 32 (13)
- Page Number:
- pp. 2832-2852.
- Translation or Not:
- No
- Date of Publication:
- 2010-05-05