A row relaxation method for large \(l_ 1\) problems (Q1176532)

To solve the regularized \(\ell_ 1\) problem: \(\hbox{minimize }{1\over 2}\varepsilon \| x\|^ 2_ 2 + \| Ax+b\|_ 1\) (where \(\varepsilon =\hbox{const}>0\), \(A\) is a real \(m\times m\) matrix, \(b\) and \(x\) are real \(m\)- and \(n\)-dimensional vectors respectively, \(x\) is the vector of unknowns), an efficient row relaxation method (resembling the Kaczmarz's method) is proposed. The author's approach is analogous to the suggested by \textit{G. T. Herman}, \textit{A. Lent} and \textit{H. Hurwitz} [J. Inst. Math. Appl. 25, 361-366 (1980; Zbl 0441.65033)], \textit{Y. Censor} [SIAM Rev. 23, 444-466 (1981; Zbl 0469.65037) and Math. Program., Ser. B 42, 307-325 (1988; Zbl 0658.90099)] et al. for regularized \(\ell_ 2\) problems (i.e. with \(\| \cdot\|_ 2\) instead of \(\|\cdot\|_ 1\) in the above minimization problem). Both \(\ell_ 1\) and \(\ell_ 2\) problems arise when a large, very sensible relatively to small changes in the data, linear equations system is to be solved, e.g. in the field of image reconstruction from projections. The \(\ell_ 1\) formulation of the regularized problem, when compared with \(\ell_ 2\) one, has the advantage of less sensitivity to the presence of occasional large errors in the data. The proposed algorithm is similar to one proposed by the author in [A row relaxation method for large-scale linear programming. Tech. Rep., Hydrological Service of Israel (1990)] for the regularized linear programming problem (and is derived in the similar manner, using some structural analogies between the above problem and the dual of the partially regularized linear programming problem). A simple iterative technique to improve the obtained solution is also presented and analyzed. Finally, the author demonstrates the possibility to use his method for constrained \(\ell_ 1\) problems (the minimization problem as above but subject to a set of linear constraints).