A row relaxation method for large ℓp least norm problems

✍ Scribed by Achiya Dax

• Publisher: John Wiley and Sons
• Year: 1994
• Tongue: English
• Weight: 671 KB
• Volume: 1
• Category: Article
• ISSN: 1070-5325
• DOI: 10.1002/nla.1680010304

✦ Synopsis

This paper presents a row relaxation method for solving the regularized C, , least norm problem where e and p are positive constants, 1 < p < 03. 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 minimize U(X) = I ~A X -bll,P/p It is shown that the dual of the regularized problem has the form 1 2 maximize D(y) = b'y --sllA'y/~ll; -IIyII:/q where q = p / ( p -1). Moreover, if y solves the dual problem then X = ATy/& solves the primal problem and P(ATy/&) = 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.