optimal monotonic transform: $\min_f (f(x)-y)^2$

Question

Given two vectors of length $N$ denoted by $x_i$ and $y_i$, $1\leq i\leq N$, what is the monotonic transformation $f(x)$ that minimizes the overall distance $D=\sum_{i=1}^{N}{(f(x_i) - y_i)^2}$. Does there exist either a closed form solution or fast algorithm for computing it?

Answer 1

First, I will reorder $x_i$, such that if $x_i \leq x_j$, we have $f(x_i)\leq f(x_j)$. WLOG, I am assuming monotone means monotone increasing.

Let $f(x_i)=f_i$.

The problem is just

$$\min_f \sum_{i=1}^N (f_i-y_i)^2$$

subject to $$f_i \leq f_{i+1}, \forall i \in \left\{ 1, \ldots, N-1\right\}$$

The objective function is a quadratic with constraints which are linear. This is a quadratic programming problem. Furthermore, the objective function is convex.

This problem can be solved by a vareity of method, for example, interior point methods, conjugate gradient method, gradient projection method or extension of simplex method. Softwares such as Matlab and R have solvers for such problems.