## Abstract

We consider the unconstrained L_{q} - L_{p} minimization: find a minimizer of ∥Ax-b∥^{q}_{q}+λ∥x∥ ^{p}_{p} for given A ∈ R^{m×n} and parameters λ >0, p ∈[0, 1) and q≥ 1. This problem has been studied extensively in many areas. Especially, for the case when q=2, this problem is known as the L_{2}-L_{p} minimization problem and has found its applications in variable selection problems and sparse least squares fitting for high dimensional data. Theoretical results show that the minimizers of the L_{q} - L_{p} problem have various attractive features due to the concavity and non-Lipschitzian property of the regularization function ∥̇∥^{p}_{p}. In this paper, we show that the L _{q} - L_{p} minimization problem is strongly NP-hard for any p ∈ [0,1) and q≥ 1, including its smoothed version. On the other hand, we show that, by choosing parameters (p,λ) carefully, a minimizer, global or local, will have certain desired sparsity. We believe that these results provide new theoretical insights to the studies and applications of the concave regularized optimization problems.

Original language | English (US) |
---|---|

Pages (from-to) | 371-383 |

Number of pages | 13 |

Journal | Mathematical Programming |

Volume | 143 |

Issue number | 1-2 |

DOIs | |

State | Published - Feb 2014 |

## Keywords

- Bridge estimator
- Nonconvex optimization
- Nonsmooth optimization
- Sparse solution reconstruction
- Variable selection

## Fingerprint

Dive into the research topics of 'Complexity of unconstrained L_{2}-L

_{p}minimization'. Together they form a unique fingerprint.