Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 

 

An efficient method for the discrete linear $ L\sb{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.


References [Enhancements On Off] (What's this?)

  • [1] Nabih N. Abdelmalek, On the discrete linear 𝐿₁ approximation and 𝐿₁ solutions of overdetermined linear equations, J. Approximation Theory 11 (1974), 38–53. MR 0388750
  • [2] N. N. ABDELMALEK, "$ {L_1}$ solution of overdetermined system of linear equations by a dual simplex method," Comm. ACM (Submitted.)
  • [3] N. N. ABDELMALEK, "$ {L_1}$ solution of overdetermined system of linear equations by a dual simplex method and LU decomposition," Comm. ACM (Submitted.)
  • [4] Ian Barrodale and Andrew Young, Algorithms for best 𝐿₁ and 𝐿_{∞} linear approximations on a discrete set, Numer. Math. 8 (1966), 295–306. MR 0196912, https://doi.org/10.1007/BF02162565
  • [5] I. BARRODALE & F. D. K. ROBERTS, An Improved Algorithm For Discrete $ {l_1}$. Approximation, The University of Wisconsin, MRC Tech. Report no. 1172, 1972.
  • [6] I. Barrodale and F. D. K. Roberts, An improved algorithm for discrete 𝑙₁ linear approximation, SIAM J. Numer. Anal. 10 (1973), 839–848. MR 0339449, https://doi.org/10.1137/0710069
  • [7] 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.
  • [8] 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.
  • [9] Karl H. Usow, On 𝐿₁ approximation. II. Computation for discrete functions and discretization effects, SIAM J. Numer. Anal. 4 (1967), 233–244. MR 0217499, https://doi.org/10.1137/0704022
  • [10] Harvey M. Wagner, Linear programming techniques for regression analysis, J. Amer. Statist. Assoc. 54 (1959), 206–212. MR 0130753

Similar Articles

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

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


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1975-0378354-8
Keywords: Discrete linear $ {L_1}$ approximation, overdetermined system of linear equations, linear programming, dual simplex algorithm
Article copyright: © Copyright 1975 American Mathematical Society