A Finite Smoothing Algorithm for Linear l₁ 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.
- On orthogonal linear \(\ell_1\) approximation
- A simple solution to the ^ 1 optimization problem
- A globally and quadratically convergent affine scaling method for linear \(l_ 1\) problems
- On Newton's method for Huber's robust M-estimation problems in linear regression
- New characterizations of \(\ell_ 1\) solutions to overdetermined systems of linear equations
- Piecewise-linear pathways to the optimal solution set in linear programming
- A penalty continuation method for the _ solution of overdetermined linear systems
- Approximation in normed linear spaces
- An \(L_{1}\) estimation algorithm with degeneracy and linear constraints.
- On the characterization of quadratic splines
- Implementing a parallel constrained \(l_ 1\) approximation algorithm
- A class of smoothing functions for nonlinear and mixed complementarity problems
- Smoothing methods for convex inequalities and linear complementarity problems
- Sparse solutions to an underdetermined system of linear equations via penalized Huber loss
- Image restoration from noisy incomplete frequency data by alternative iteration scheme
- Quantile regression neural networks: a Bayesian approach
- Fully smoothed _1-TV models: bounds for the minimizers and parameter choice
- Modelling and estimation of nonlinear quantile regression with clustered data
- Huber approximation for the non-linear \(l_{1}\) problem
- Finite algorithms for robust linear regression
- Smoothed penalty algorithms for optimization of nonlinear models
- Gauss-Seidal algorithm to L₁ minimization
- Necessary and Sufficient Conditions for Noiseless Sparse Recovery via Convex Quadratic Splines
- A Globally Convergent Method for l_p Problems
- An on-line adaptation for discrete<tex>l_{1}</tex>linear estimation
- Censored Discrete Linear l₁ Approximation
- Piecewise Polynomial Solutions Without a priori Break Points
- l1 solution of linear inequalities
- scientific article; zbMATH DE number 1349149 (Why is no real title available?)
- scientific article; zbMATH DE number 1124620 (Why is no real title available?)
- Least absolute value regression: recent contributions
- A Base-Point Descent Algorithm For Solving The Linear l 1 Problem
- Quantile regression via iterative least squares computations
- A finite hyperplane traversal algorithm for 1-dimensional \(L^1pTV\) minimization, for \(0<p\leq 1\)
- Bayesian quantile regression for ordinal models
- Linear programming and \(\ell _ 1\) regression: A geometric interpretation
- The best least absolute deviations line -- properties and two efficient methods for its derivation
- Bayesian quantile regression for longitudinal count data
- Numerical algorithms for nonlinear L_p-norm problem and its extreme case
- Huberization image restoration model from incomplete multiplicative noisy data
- Adaptive Huber-type smoothing algorithm for change point detection in quantile regression
- Shrinkage estimation of varying covariate effects based on quantile regression
- An iterative algorithm for \(l_1\)-norm approximation in dynamic estimation problems
- Minimizers of sparsity regularized Huber loss function
- Multiple criteria linear regression
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)