WEIGHTED MEDIAN ALGORITHMS FOR L1 APPROXIMATION

被引：29

作者：

GURWITZ, C ^{[1
]}

机构：

[1] CUNY BROOKLYN COLL,DEPT COMP & INFORMAT SCI,BROOKLYN,NY 11210

来源：

BIT | 1990年 / 30卷 / 02期

关键词：

AMS Subject Classification: 65D99; 65K10; L[!sub]1[!/sub] approximation; median;

D O I：

10.1007/BF02017350

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The weighted median problem arises as a subproblem in certain multivariate optimization problems, including L1 approximation. Three algorithms for the weighted median problem are presented and the relationships between them are discussed. We report on computational experience with these algorithms and on their use in the context of multivariate L1 approximation. © 1990 BIT Foundations.

引用

页码：301 / 310

页数：10

共 16 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[2] IMPROVED ALGORITHM FOR DISCRETE L1 LINEAR-APPROXIMATION [J].

BARRODALE, I ;

ROBERTS, FDK .

SIAM JOURNAL ON NUMERICAL ANALYSIS, 1973, 10 (05) :839-848

[3] MINIMIZATION TECHNIQUES FOR PIECEWISE DIFFERENTIABLE FUNCTIONS - L1 SOLUTION TO AN OVERDETERMINED LINEAR-SYSTEM [J].

BARTELS, RH ;

CONN, AR ;

SINCLAIR, JW .

SIAM JOURNAL ON NUMERICAL ANALYSIS, 1978, 15 (02) :224-241

[4]

BLEICH C, 1983, 75 NEW YORK U DEP CO

[5] LEAST ABSOLUTE DEVIATIONS CURVE-FITTING [J].

BLOOMFIELD, P ;

STEIGER, W .

SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, 1980, 1 (02) :290-301

[6]

Blum M., 1973, Journal of Computer and System Sciences, V7, P448, DOI 10.1016/S0022-0000(73)80033-9

[7] A STABLE ALGORITHM FOR SOLVING THE MULTIFACILITY LOCATION PROBLEM INVOLVING EUCLIDEAN DISTANCES [J].

CALAMAI, PH ;

CONN, AR .

SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, 1980, 1 (04) :512-526

[8] ROBUST MODELING WITH ERRATIC DATA [J].

CLAERBOUT, JF ;

MUIR, F .

GEOPHYSICS, 1973, 38 (05) :826-844

[9] ALGORITHM SELECT - FOR FINDING ITH SMALLEST OF N-ELEMENTS [M1] [J].

FLOYD, RW ;

RIVEST, RL .

COMMUNICATIONS OF THE ACM, 1975, 18 (03) :173-173

[10] EXPECTED TIME BOUNDS FOR SELECTION [J].

FLOYD, RW ;

RIVEST, RL .

COMMUNICATIONS OF THE ACM, 1975, 18 (03) :165-172

← 1 2 →