1
$\begingroup$

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

$h=argmin_{h}\sum_{n\in[0,N]}{(f(n)-h(g(n)))^2}$

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!

$\endgroup$

2 Answers 2

1
$\begingroup$

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).

$\endgroup$
0
0
$\begingroup$

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$.

$\endgroup$
3
  • 1
    $\begingroup$ Did you read that Grönwall is looking for a monotone function h. $\endgroup$
    – Someone
    Sep 10, 2010 at 12:14
  • $\begingroup$ 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. $\endgroup$
    – fedja
    Sep 10, 2010 at 12:34
  • $\begingroup$ Sorry about the typo. $\endgroup$
    – Grönwall
    Sep 10, 2010 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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