Linear Time Isotonic and Unimodal Regression in the L1 and L∞ Norms.

Linear Time Isotonic and Unimodal Regression in the L1 and L∞ Norms. Victor Boyarshinov Malik Magdon-Ismail We consider L1-isotonic regression and L∞ isotonic and unimodal regression. For L1- isotonic regression, we present a linear time algorithm when the number of outputs are bounded. We extend the algorithm to construct an approximate isotonic regression in linear time when the output range is bounded. We present linear time algorithms for L∞ isotonic and unimodal regression. Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY 01/21/2004 cs-04-02

Linear Time Isotonic and Unimodal Regression in the L1 and L∞ Norms.

Victor Boyarshinov

Malik Magdon-Ismail

We consider L1-isotonic regression and L∞ isotonic and unimodal regression. For L1- isotonic regression, we present a linear time algorithm when the number of outputs are bounded. We extend the algorithm to construct an approximate isotonic regression in linear time when the output range is bounded. We present linear time algorithms for L∞ isotonic and unimodal regression.

Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY

01/21/2004

cs-04-02