Isotonic regression
Encyclopedia
In numerical analysis
, isotonic regression (IR) involves finding a weighted least-squares fit
to a vector
with weights vector 
subject to a set of monotonicity constraints giving a simple or partial order over the variables. The monotonicity constraints define a directed acyclic graph
over the nodes 
corresponding to the variables 
. Thus, the IR problem where a simple order is defined corresponds to the following quadratic program
(QP):
In the case when
is a total order
, a simple iterative algorithm for solving this QP is called the pool adjacent violators algorithm (PAVA). Best and Chakravarti (1990) have studied the problem as an active set identification problem, and have proposed a primal algorithm in O(n), the same complexity
as the PAVA, which can be seen as a dual algorithm.
IR has applications in statistical inference
, for example, computing the cost at the minimum
of the above goal function, gives the "stress" of the fit of an isotonic curve to mean experimental results when an order is expected.
Another application is nonmetric multidimensional scaling
(Kruskal, 1964), where a low-dimensional embedding
for data points is sought such that order of distances between points in the embedding matches order of dissimilarity between points. Isotonic regression is used iteratively to fit ideal distances to preserve relative dissimilarity order.
Isotonic regression is also sometimes referred to as monotonic regression. Correctly speaking, isotonic is used when the direction of the trend is strictly increasing, while monotonic could imply a trend that is either strictly increasing or strictly decreasing.
Isotonic Regression under the
for 
is defined as follows:
, and 
, and 
.
The isotonic estimator,
, minimizes the weighted least squares-like condition:
Where
is the unknown function we are estimating, and 
is a known function.
Software has been developed in the R statistical package for computing isotone (monotonic) regression.
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
, isotonic regression (IR) involves finding a weighted least-squares fit
to a vectorEuclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
with weights vector subject to a set of monotonicity constraints giving a simple or partial order over the variables. The monotonicity constraints define a directed acyclic graphDirected acyclic graph
In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
over the nodes corresponding to the variables . Thus, the IR problem where a simple order is defined corresponds to the following quadratic programQuadratic programming
Quadratic programming is a special type of mathematical optimization problem. It is the problem of optimizing a quadratic function of several variables subject to linear constraints on these variables....
(QP):
In the case when
is a total orderTotal order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
, a simple iterative algorithm for solving this QP is called the pool adjacent violators algorithm (PAVA). Best and Chakravarti (1990) have studied the problem as an active set identification problem, and have proposed a primal algorithm in O(n), the same complexity
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
as the PAVA, which can be seen as a dual algorithm.
IR has applications in statistical inference
Statistical inference
In statistics, statistical inference is the process of drawing conclusions from data that are subject to random variation, for example, observational errors or sampling variation...
, for example, computing the cost at the minimum
Maxima and minima
In mathematics, the maximum and minimum of a function, known collectively as extrema , are the largest and smallest value that the function takes at a point either within a given neighborhood or on the function domain in its entirety .More generally, the...
of the above goal function, gives the "stress" of the fit of an isotonic curve to mean experimental results when an order is expected.
Another application is nonmetric multidimensional scaling
Multidimensional scaling
Multidimensional scaling is a set of related statistical techniques often used in information visualization for exploring similarities or dissimilarities in data. MDS is a special case of ordination. An MDS algorithm starts with a matrix of item–item similarities, then assigns a location to each...
(Kruskal, 1964), where a low-dimensional embedding
Embedding
In mathematics, an embedding is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup....
for data points is sought such that order of distances between points in the embedding matches order of dissimilarity between points. Isotonic regression is used iteratively to fit ideal distances to preserve relative dissimilarity order.
Isotonic regression is also sometimes referred to as monotonic regression. Correctly speaking, isotonic is used when the direction of the trend is strictly increasing, while monotonic could imply a trend that is either strictly increasing or strictly decreasing.
Isotonic Regression under the
for is defined as follows: Simply ordered case
To illustrate the above, let, and , and .The isotonic estimator,
, minimizes the weighted least squares-like condition:Where
is the unknown function we are estimating, and is a known function.Software has been developed in the R statistical package for computing isotone (monotonic) regression.