Convergence of the reweighted ℓ1minimization algorithm for ℓ2-ℓpminimization

Xiaojun Chen; Weijun Zhou

doi:10.1007/s10589-013-9553-8

Convergence of the reweighted ℓ₁minimization algorithm for ℓ₂-ℓ_pminimization

Xiaojun Chen, Weijun Zhou

Research output: Journal article publication › Journal article › Academic research › peer-review

92 Citations (Scopus)

Abstract

The iteratively reweighted ℓ1minimization algorithm (IRL1) has been widely used for variable selection, signal reconstruction and image processing. In this paper, we show that any sequence generated by the IRL1 is bounded and any accumulation point is a stationary point of the ℓ2-ℓpminimization problem with 0<p<1. Moreover, the stationary point is a global minimizer and the convergence rate is approximately linear under certain conditions. We derive posteriori error bounds which can be used to construct practical stopping rules for the algorithm.

Original language	English
Pages (from-to)	47-61
Number of pages	15
Journal	Computational Optimization and Applications
Volume	59
Issue number	1-2
DOIs	https://doi.org/10.1007/s10589-013-9553-8
Publication status	Published - 1 Jan 2014

Keywords

Global convergence
Nonsmooth and nonconvex optimization
Pseudo convex
Stationary points

ASJC Scopus subject areas

Control and Optimization
Computational Mathematics
Applied Mathematics

More information

10.1007/s10589-013-9553-8

Cite this

@article{b8f04fdac95942efae661714fa981d1c,

title = "Convergence of the reweighted ℓ1minimization algorithm for ℓ2-ℓpminimization",

abstract = "The iteratively reweighted ℓ1minimization algorithm (IRL1) has been widely used for variable selection, signal reconstruction and image processing. In this paper, we show that any sequence generated by the IRL1 is bounded and any accumulation point is a stationary point of the ℓ2-ℓpminimization problem with 0<p<1. Moreover, the stationary point is a global minimizer and the convergence rate is approximately linear under certain conditions. We derive posteriori error bounds which can be used to construct practical stopping rules for the algorithm.",

keywords = "Global convergence, Nonsmooth and nonconvex optimization, Pseudo convex, Stationary points",

author = "Xiaojun Chen and Weijun Zhou",

year = "2014",

month = jan,

day = "1",

doi = "10.1007/s10589-013-9553-8",

language = "English",

volume = "59",

pages = "47--61",

journal = "Computational Optimization and Applications",

issn = "0926-6003",

publisher = "Springer Netherlands",

number = "1-2",

}

TY - JOUR

T1 - Convergence of the reweighted ℓ1minimization algorithm for ℓ2-ℓpminimization

AU - Chen, Xiaojun

AU - Zhou, Weijun

PY - 2014/1/1

Y1 - 2014/1/1

N2 - The iteratively reweighted ℓ1minimization algorithm (IRL1) has been widely used for variable selection, signal reconstruction and image processing. In this paper, we show that any sequence generated by the IRL1 is bounded and any accumulation point is a stationary point of the ℓ2-ℓpminimization problem with 0<p<1. Moreover, the stationary point is a global minimizer and the convergence rate is approximately linear under certain conditions. We derive posteriori error bounds which can be used to construct practical stopping rules for the algorithm.

AB - The iteratively reweighted ℓ1minimization algorithm (IRL1) has been widely used for variable selection, signal reconstruction and image processing. In this paper, we show that any sequence generated by the IRL1 is bounded and any accumulation point is a stationary point of the ℓ2-ℓpminimization problem with 0<p<1. Moreover, the stationary point is a global minimizer and the convergence rate is approximately linear under certain conditions. We derive posteriori error bounds which can be used to construct practical stopping rules for the algorithm.

KW - Global convergence

KW - Nonsmooth and nonconvex optimization

KW - Pseudo convex

KW - Stationary points

UR - http://www.scopus.com/inward/record.url?scp=84906841208&partnerID=8YFLogxK

U2 - 10.1007/s10589-013-9553-8

DO - 10.1007/s10589-013-9553-8

M3 - Journal article

SN - 0926-6003

VL - 59

SP - 47

EP - 61

JO - Computational Optimization and Applications

JF - Computational Optimization and Applications

IS - 1-2

ER -