A Globally Convergent Method for Lp Problems

Abstract

The $l_p$ norm discrete estimation problem $min_{x \epsilon \Re}{n}$ $\|b-A^{T}x\|_{p}$ is troblesome when $p$ is close to unity because the objective function approaches a discontinuous form. In this paper, we present an efficient approach for solving $l_p$ norm problems for all $1\leq p less than 2$. When $p=1$, it is essentially the method presented in [4], which is globally and quadratically convergent algorithm under some nondegeneracy assumptions. The existing iteratively reweighted least squares (IRLS) can be obtained from the new approach by updating some "dual multipliers" in a special fashion. The new method is globally convergent. It is superlinearly convergent when there is no zero residual at the solution. The main computational cost of our new methos is the same as the IRLS method: a reweighted least squares solve. Numerical experiments indicate this method is significantly faster than popular iteratively reweighted least squares method when $p$ is close or equal to one.