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

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] N. N. ABDELMALEK, "On the discrete linear $ {L_1}$ approximation and $ {L_1}$ solutions of overdetermined linear equations," J. Approximation Theory, v. 11, 1974, pp. 38-53. MR 0388750 (52:9584)
  • [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] I. BARRODALE & A. YOUNG, "Algorithms for best $ {L_1}$ and $ {L_\infty }$ linear approximations on a discrete set," Numer. Math., v. 8, 1966, pp. 295-306. MR 33 #5096. MR 0196912 (33:5096)
  • [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 & F. D. K. ROBERTS, "An improved algorithm for discrete $ {l_1}$. approximation," SIAM J. Numer. Anal., v. 10, 1973, pp. 839-848. MR 0339449 (49:4208)
  • [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] K. H. USOW, "On $ {L_1}$ approximation II: Computation for discrete functions and discretization effects," SIAM J. Numer. Anal., v. 4, 1967, pp. 233-244. MR 36 #588. MR 0217499 (36:588)
  • [10] H. M. WAGNER, "Linear programming techniques for regression analysis," J. Amer. Statist. Assoc., v. 54, 1959, pp. 206-212. MR 24 #A612. MR 0130753 (24:A612)

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

American Mathematical Society