An efficient method for the discrete linear $L_{1}$ approximation problem
HTML articles powered by AMS MathViewer
- by Nabih N. Abdelmalek PDF
- Math. Comp. 29 (1975), 844-850 Request permission
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.References
- 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 10.1016/0021-9045(74)90037-9 N. N. ABDELMALEK, "${L_1}$ solution of overdetermined system of linear equations by a dual simplex method," 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.)
- 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 10.1007/BF02162565 I. BARRODALE & F. D. K. ROBERTS, An Improved Algorithm For Discrete ${l_1}$. Approximation, The University of Wisconsin, MRC Tech. Report no. 1172, 1972.
- 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 10.1137/0710069 I. BARRODALE & F. D. K. ROBERTS, "Solution of an overdetermined system of equations in the ${l_1}$ norm," 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.
- 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 10.1137/0704022
- Harvey M. Wagner, Linear programming techniques for regression analysis, J. Amer. Statist. Assoc. 54 (1959), 206–212. MR 130753, DOI 10.1080/01621459.1959.10501506
Additional Information
- © Copyright 1975 American Mathematical Society
- 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