MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $f$ and $g$ be two discrete signals. I want to find a monotone function h such that


I don't really care about finding the global optimum, I just want a good fit. What would be a good representation of f to achieve that? Thanks!

share|cite|improve this question
up vote 1 down vote accepted

Here is another try:

Assume w.l.o.g. that values of $g(n)$ are in increasing order, i.e. $g(0) \le g(1) \le \cdots\le g(n)$. Moreover, assume the first $n_1$ values in that sequence are equal, then the next $n_2$ values are equal, etc. and that there are $m$ distinct values i.e. $$g(0)=g(1)=\cdots=g(n_1-1) < g(n_1)=\cdots=g(n_1+n_2-1) < \cdots < g(n_1+\cdots+n_{m-1}) + \cdots g(n_1+\cdots+n_m-1).$$We have to decide the following $m$ values of $h$: $$h_k = h(g(k)), \quad k=1,2,\ldots m$$

Say we are looking for an increasing $h$ (you can look for a decreasing $h$ in a similar way and take the best of the two solutions). Denote by $H_r(t)$ the value of the solution of the problem limited to the first $r$ groups, where $t$ is an additional upper bound $t$ on the values taken by $h$, i.e. $$H_r(t) = \min_{h_1 \le h_2 \le \cdots \le h_r \le t} \quad \sum_{k=1}^r \quad \sum_{i=n_1+\cdots+n_{r-1}}^{n_1+\cdots+n_r-1} (f(i) - h_k)^2$$

When $r=1$, the value of $H_1(t)$ can now be easily computed: it is easy to check that the optimal $h_1$ is equal to the average $\bar{f_1}=\frac{1}{n_1}(f(0)+f(1)+ \ldots+ f(n_1-1))$ if it is less than $t$, and to $t$ otherwise, and that $$H_1(t)=constant + n_1 (\min (t-\bar{f_1},0))^2 .$$From that we can successively compute the values of $H_2(t)$, $H_3(t)$, etc. and end up with the final solution when $r=n$, using the recurrence $$H_{r}(t) = \min_{s \le t}\ H_{r-1}(s) + constant + n_s(s-\bar{f_r})^2$$ (this is similar to dynamic programming).

share|cite|improve this answer
Very neat! Thanks a lot. – Grönwall Sep 14 '10 at 11:33

Edit: the answer below ignores the monotonicity constraint, and refers to a previous version of the problem with $g(h(n))$ instead of $h(g(n))$

You problem is completely separable: for each $k$, choose the value of $h(k)$ such that $g(h(k))$ is as close as possible to $f(k)$, a decision that is independent from the values of $h(n)$ for all other $n \neq k$. Each of these choices is made by simple inspection of the possible values for $g$.

share|cite|improve this answer
Did you read that Grönwall is looking for a monotone function h. – Someone Sep 10 '10 at 12:14
As if there existed any monotone functions from $[1,N]$ to $[1,N]$ other than $x$ and $N+1-x$. Certainly, something else was meant (say, $g(h)$ should really be $h(g)$), but I'm too lazy to strain my mind-reading abilities. – fedja Sep 10 '10 at 12:34
Sorry about the typo. – Grönwall Sep 10 '10 at 12:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.