## Abstract

We consider the unconstrained Lq - Lp minimization: find a minimizer of ∥Ax-b∥qq+λ∥x∥ pp for given A ∈ Rm×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 L2-Lp 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 Lq - Lp problem have various attractive features due to the concavity and non-Lipschitzian property of the regularization function ∥̇∥pp. In this paper, we show that the L q - Lp 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 |
---|---|

Pages (from-to) | 371-383 |

Number of pages | 13 |

Journal | Mathematical Programming |

Volume | 143 |

Issue number | 1-2 |

DOIs | |

Publication status | Published - 1 Feb 2014 |

## Keywords

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

## ASJC Scopus subject areas

- Software
- Mathematics(all)

## Fingerprint

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

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