A comparison of methods for discrete L_1 curve-fitting

We study discrete L_1, curve-fitting of n points in k dimensional space. Execution times for the algorithms of Barrodaie-Roberts (BR), Bartels-Conn-Sinclair (BCS), and Bloomfieid-Steiger (BS) - three of the best LAD curve-fitting procedures - are compared over a variety of deterministic and random curve-fitting problems. Analysis of the results allows us to make surprisingly precise statements about the computational complexity of these algorithms. In particular, BR is in a different complexity ciass than BCS and BS as the number of points,n, increases. All algorithms are linear in'the dimension, k, andBS is less complex than BCS.Technical report DCS-TR-9