An efficient method for the discrete linear approximation problem
Author:
Nabih N. Abdelmalek
Journal:
Math. Comp. 29 (1975), 844850
MSC:
Primary 65D15; Secondary 90C10
MathSciNet review:
0378354
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: An improved dual simplex algorithm for the solution of the discrete linear 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 illconditioned problems, the basis matrix can lend itself to triangular factorization and can thus ensure a stable solution. Numerical results are given.
 [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, " solution of overdetermined system of linear equations by a dual simplex method," Comm. ACM (Submitted.)
 [3]
N. N. ABDELMALEK, " 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 . 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 norm," Comm. ACM, v. 17, 1974, pp. 319920.
 [8]
R. H. BARTELS & G. H. GOLUB, "The simplex method of linear programming using LU decomposition," Comm. ACM, v. 12, 1969, pp. 266268. 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)
 [1]
 N. N. ABDELMALEK, "On the discrete linear approximation and solutions of overdetermined linear equations," J. Approximation Theory, v. 11, 1974, pp. 3853. MR 0388750 (52:9584)
 [2]
 N. N. ABDELMALEK, " solution of overdetermined system of linear equations by a dual simplex method," Comm. ACM (Submitted.)
 [3]
 N. N. ABDELMALEK, " 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 and linear approximations on a discrete set," Numer. Math., v. 8, 1966, pp. 295306. MR 33 #5096. MR 0196912 (33:5096)
 [5]
 I. BARRODALE & F. D. K. ROBERTS, An Improved Algorithm For Discrete . Approximation, The University of Wisconsin, MRC Tech. Report no. 1172, 1972.
 [6]
 I. BARRODALE & F. D. K. ROBERTS, "An improved algorithm for discrete . approximation," SIAM J. Numer. Anal., v. 10, 1973, pp. 839848. MR 0339449 (49:4208)
 [7]
 I. BARRODALE & F. D. K. ROBERTS, "Solution of an overdetermined system of equations in the norm," Comm. ACM, v. 17, 1974, pp. 319920.
 [8]
 R. H. BARTELS & G. H. GOLUB, "The simplex method of linear programming using LU decomposition," Comm. ACM, v. 12, 1969, pp. 266268. MR 39 #2302.
 [9]
 K. H. USOW, "On approximation II: Computation for discrete functions and discretization effects," SIAM J. Numer. Anal., v. 4, 1967, pp. 233244. 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. 206212. 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:
http://dx.doi.org/10.1090/S00255718197503783548
PII:
S 00255718(1975)03783548
Keywords:
Discrete linear approximation,
overdetermined system of linear equations,
linear programming,
dual simplex algorithm
Article copyright:
© Copyright 1975
American Mathematical Society
