pava_ls: Least-Squares Pooled Adjacent Violators Algorithm

In sdzhao/cole: COmpound Loss Emporium

Least-Squares Pooled Adjacent Violators Algorithm

Description

An implementation of the pooled adjacent violators algorithm for minimizing the least squares loss subject to the monotonicity (non-decreasing) constraint.

Usage

pava_ls(y)

Arguments

y	numeric vector of observations corresponding to a sorted, increasing predictor

Details

It is assumed that y is ordered corresponding to the correct indices for a monotone non-decreasing fit. If a monotone non-increasing fit is desired use base::rev() as in the examples.

The basic idea is to start by partitioning the data into singletons (zero least squares loss), then merge neighboring sets if the monotone non-decreasing constraint is violated. The value a set takes is the average of its elements, this is implemented by tracking set cardinality and the current mean so that the merger of two sets is just a weighted sum.

This algorithm has time complexity O(n). However, this implementation may have worse complexity because of the way we are removing elements in a vector during the merge.

Value

a numeric vector of fitted values corresponding to y

Examples

# non-decreasing example
set.seed(1)
y <- atan(seq(from = -5, to = 5, length.out = 51)) + rnorm(51, sd = 0.2)
y.hat <- pava_ls(y) # not exported
plot(y)
points(y.hat, col = "red")

#non-increasing example
set.seed(1)
y <- -atan(seq(from = -5, to = 5, length.out = 51)) + rnorm(51, sd = 0.2)
y.hat <- rev(pava_ls(rev(y)))
plot(y)
points(y.hat, col = "red")

sdzhao/cole documentation built on May 2, 2022, 9:42 a.m.