Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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
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 (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] Ian Barrodale and Andrew Young, Algorithms for best 𝐿₁ and 𝐿_{∞} linear approximations on a discrete set, Numer. Math. 8 (1966), 295–306. 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 and F. D. K. Roberts, An improved algorithm for discrete 𝑙₁ linear approximation, SIAM J. Numer. Anal. 10 (1973), 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] Karl H. Usow, On 𝐿₁ approximation. II. Computation for discrete functions and discretization effects, SIAM J. Numer. Anal. 4 (1967), 233–244. MR 0217499 (36 #588)
  • [10] Harvey M. Wagner, Linear programming techniques for regression analysis, J. Amer. Statist. Assoc. 54 (1959), 206–212. 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: http://dx.doi.org/10.1090/S0025-5718-1975-0378354-8
PII: S 0025-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