An efficient method for the discrete linear $L_{1}$ approximation problem

Author:
Nabih N. Abdelmalek

Journal:
Math. Comp. **29** (1975), 844-850

MSC:
Primary 65D15; Secondary 90C10

DOI:
https://doi.org/10.1090/S0025-5718-1975-0378354-8

MathSciNet review:
0378354

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: An improved dual simplex algorithm for the solution of the discrete linear ${L_1}$ approximation problem is described. In this algorithm certain intermediate iterations are skipped. This method is comparable with an improved simplex method due to Barrodale and Roberts, in both speed and number of iterations. It also has the advantage that in case of ill-conditioned problems, the basis matrix can lend itself to triangular factorization and can thus ensure a stable solution. Numerical results are given.

- Nabih N. Abdelmalek,
*On the discrete linear $L_{1}$ approximation and $L_{1}$ solutions of overdetermined linear equations*, J. Approximation Theory**11**(1974), 38–53. MR**388750**, DOI https://doi.org/10.1016/0021-9045%2874%2990037-9
N. N. ABDELMALEK, "${L_1}$ solution of overdetermined system of linear equations by a dual simplex method," - Ian Barrodale and Andrew Young,
*Algorithms for best $L_{1}$ and $L_{\infty }$ linear approximations on a discrete set*, Numer. Math.**8**(1966), 295–306. MR**196912**, DOI https://doi.org/10.1007/BF02162565
I. BARRODALE & F. D. K. ROBERTS, - I. Barrodale and F. D. K. Roberts,
*An improved algorithm for discrete $l_{1}$ linear approximation*, SIAM J. Numer. Anal.**10**(1973), 839–848. MR**339449**, DOI https://doi.org/10.1137/0710069
I. BARRODALE & F. D. K. ROBERTS, "Solution of an overdetermined system of equations in the ${l_1}$ norm," - Karl H. Usow,
*On $L_{1}$ approximation. II. Computation for discrete functions and discretization effects*, SIAM J. Numer. Anal.**4**(1967), 233–244. MR**217499**, DOI https://doi.org/10.1137/0704022 - Harvey M. Wagner,
*Linear programming techniques for regression analysis*, J. Amer. Statist. Assoc.**54**(1959), 206–212. MR**130753**

*Comm. ACM*(Submitted.) N. N. ABDELMALEK, "${L_1}$ solution of overdetermined system of linear equations by a dual simplex method and

*LU*decomposition,"

*Comm. ACM*(Submitted.)

*An Improved Algorithm For Discrete*${l_1}$.

*Approximation*, The University of Wisconsin, MRC Tech. Report no. 1172, 1972.

*Comm. ACM*, v. 17, 1974, pp. 319-920. R. H. BARTELS & G. H. GOLUB, "The simplex method of linear programming using

*LU*decomposition,"

*Comm. ACM*, v. 12, 1969, pp. 266-268. MR

**39**#2302.

Retrieve articles in *Mathematics of Computation*
with MSC:
65D15,
90C10

Retrieve articles in all journals with MSC: 65D15, 90C10

Additional Information

Keywords:
Discrete linear <IMG WIDTH="28" HEIGHT="38" ALIGN="MIDDLE" BORDER="0" SRC="images/img11.gif" ALT="${L_1}$"> approximation,
overdetermined system of linear equations,
linear programming,
dual simplex algorithm

Article copyright:
© Copyright 1975
American Mathematical Society