A row relaxation method for large ℓ p least norm problems

This paper presents a row relaxation method for solving the regularized ℓ p least norm problem\documentclass{article}\pagestyle{empty}\begin{document}$$ {\rm minimize}P({\rm x}) = \frac{1}{2}\varepsilon \parallel {\rm x}\parallel _{\rm 2}^{\rm 2} + \parallel A{\rm x} - {\rm b}\parallel _p^p /p $$\end{document}where e and p are positive constants, 1< p <∞ The interest that we have in this problem lies in the observation that for small values of E the minimizer of P (X ) is a good substitute for a minimizer of the unregularized problem\documentclass{article}\pagestyle{empty}\begin{document}$$ {\rm minimize }U({\rm x}) = \parallel A{\rm x} - {\rm b}\parallel _p^p /p $$\end{document}It is shown that the dual of the regularized problem has the form\documentclass{article}\pagestyle{empty}\begin{document}$$ {\rm minimize }D({\rm y}) = {\rm b}^T {\rm y} - \frac{1}{2}\varepsilon \parallel A^T {\rm y/}\varepsilon \parallel _2^2 - \parallel {\rm y}\parallel _q^q /q $$\end{document}where q = p /(p ‐ 1). Moreover, if y solves the dual problem then X = A T y/ϵ solves the primal problem and P(A T y/ϵ) = D(y). Maximizing the dual objective function by changing one variable at a time results in a row relaxation method that resembles Kaczmarz's method. This feature makes the new method suitable for solving large sparse C, problems that arise in computerized tomography, geophysics, and groundwater hydrology. Numerical experiments illustrate the feasibility of our ideas.