A Finite Smoothing Algorithm for Linear l₁ Estimation

From MaRDI portal
A Finite Smoothing Algorithm for Linear $l 1 $ Estimation





A new method for solving the linear \(\ell_ 1\) problem is described, analyzed, and tested. The linear \(\ell_ 1\) estimation problem is minimizing the functional \(F(x) = \sum^ m_{j=1}| \tau_ j(x)|\), where \(\tau_ j(x)\) (\(j = 1,\dots,m\)) is a set of linear functionals in \(\mathbb{R}^ n\). At each iteration the nondifferentiable function \(F\) is approximated by a smooth function, the Huber \(M\)- estimator \(F_ \gamma(x)\) (\(\gamma > 0\)). The main result (Theorem 1) shows that the \(\ell_ 1\) solution can be detected directly from a minimizer of \(F_ \gamma\) when \(\gamma\) is small enough, i.e., it is not necessary to let \(\gamma\) converge to zero in order to find a minimizer of \(F(x)\). This observation is essential for the efficiency and the numerical stability of the algorithm. The algorithm produces a sequence \(x_{\gamma_ i}\) (\(i = 1,\dots,i_ 0\)) of minimizers of \(F_ \gamma(x)\), where \(\{\gamma_ i\}\) is a decreasing sequence of positive numbers. When the threshold is small enough, an \(\ell_ 1\) solution is detected and the computation stops after a finite number of iterations. The minimizers of \(F_ \gamma(x)\) are found through a Newton-type iteration. Extensive numerical testing of the algorithm indicates that the number of different threshold values used only increases very slowly with the size of the problem. The relationship between the \(\ell_ 1\) problem and the linear programming problem indicates that the new method may also be used to solve the latter class of problems. A large number of numerical tests with the new algorithm and the Barrodale-Roberts algorithm are described. Numerical tests demonstrate significant superiority to existing simplex-type codes. The tests show that the new algorithm is very well suited for vector processing.




Cited in
(45)








This page was built for publication: A Finite Smoothing Algorithm for Linear $l_1 $ Estimation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5287100)