1
$\begingroup$

Let $f(x)$ be some unknown continuous square-integrable function defined on the interval $[0,1]$.

Suppose we have $i=1,...,n$ samples $f_i$ of $f$ of the following form: $$f_i(x)=a_i*f(x+b_i)+c_i$$ where each sample is defined on the interval $[\alpha,1-\alpha]$ and $-\alpha \leq b_i \leq \alpha$ for $0\leq\alpha<1/2$.

Additionally, assume that for at least two of the samples, $b_i$ equals $-\alpha$ and $\alpha$ respectively, i.e. the whole domain of $f(x)$ is sampled. Furthermore, assume $\int_0^1 f(x)\mathrm{d}x=0$ and $\int_0^1 (f (x))^2\mathrm{d}x=1$. Finally, since the sign of $f(x)$ is not retrievable, we care only about retrieving either $f(x)$ or $-f(x)$.

What would be an efficient way to determine $f(x)$, $a_i$, $b_i$ and $c_i$? For $\alpha=b_i=0$, a PCA-like analysis would work, but how to treat the case $0<\alpha<1/2$?

$\endgroup$
4
  • 1
    $\begingroup$ What do you mean by "an efficient way to estimate"? $\endgroup$ Commented Feb 15, 2023 at 16:15
  • $\begingroup$ I‘m looking for an algorithm which given the samples $f_i$ returns $f(x), a_i, b_i, c_i$. I am saying estimate because I’m not sure if it’s guaranteed that $f(x)$ can be fully retrieved $\endgroup$
    – dff
    Commented Feb 15, 2023 at 22:37
  • $\begingroup$ What exactly do you mean by "samples"? Does it mean that the functions $f_1,\dots,f_n$ are fully known? $\endgroup$ Commented Feb 19, 2023 at 15:09
  • $\begingroup$ Yes all of the $f_i$ are known on the interval $[\alpha, 1-\alpha]$. The $a_i$, $b_i$ and $c_i$ are unknown. Determining $f$ is therefore like solving a puzzle with overlapping puzzle pieces that also need to be rescaled… $\endgroup$
    – dff
    Commented Feb 19, 2023 at 18:37

1 Answer 1

1
$\begingroup$

$\newcommand\al{\alpha}\newcommand\tf{\tilde f}\newcommand\ta{\tilde a}\newcommand\tb{\tilde b}\newcommand\tc{\tilde c}$It is never possible to recover $f$ from such data, even approximately.

Indeed, suppose that, for some $\al\in(0,1/2)$, all we know are the values of \begin{equation*} f_i(x):=a_i f(x+b_i)+c_i \tag{1}\label{1} \end{equation*} for some unknown continuous function $f$ on $[0,1]$, some unknown real $a_1,b_1,c_1,\dots,a_n,b_n,c_n$ such that $|b_i|\le\al$ for all $i\in[n]:=\{1,\dots,n\}$, and all $x\in[\al,1-\al]$.

For any real $a\ne0$, and real $c$, any real $b$ such that $|b_i-b|\le\al$ for all $i\in[n]$, and all $u\in I:=[0,1]\cap[-b,1-b]$, let \begin{equation*} \tf(u):=af(u+b)+c; \tag{2}\label{2} \end{equation*} then extend the function $\tf$ from $I$ to $[0,1]$ arbitrarily, just so that the extended function still be continuous. For all $i\in[n]$, let $$\ta_i:=\frac{a_i}a,\quad\tb_i:=b_i-b,\quad\tc_i:=c_i-\frac ca\,a_i.$$ Then $|\tb_i|\le\al$ for all $i\in[n]$ and $$f_i(x)=\ta_i \tf(x+\tb_i)+\tc_i$$ for all $i\in[n]$ and all $x\in[\al,1-\al]$.

So, equation \eqref{1} for $f$ always admits any number of solutions not close to one another in any reasonable sense.


E.g., if the formula $f(u)=\sin u$ for $u\in[0,1]$ defines a solution $f$ of \eqref{1} for some real $a_1,b_1,c_1,\dots,a_n,b_n,c_n$ such that $|b_i|\le1/6$ for all $i\in[n]$, and all $x\in[1/3,2/3]$, then the formula $\tf(u)=2\sin(u+\pi/100)+e$ defines another solution $\tf$ of \eqref{1}, with $\ta_i:=\frac{a_i}2$, $\tb_i:=b_i-\pi/100$, $\tc_i:=c_i-\frac e2\,a_i$ in place of $a_i,b_i,c_i$.


After the above answer was posted, the OP has added the condition that at least one of the $b_i$'s equals $-\al$ and at least one of the $b_i$'s equals $\al$. Also, the OP has added the condition that functions $f$ and $\tf$ related by a relation of the form \eqref{2} should be considered indistinguishable. Thus, the above answer has been invalidated.

As an exception, I will now try to answer the changed question as well.

First here, we must consider the question of the identifiability of $f$: When do the identities \eqref{1} determine $f$ uniquely up to a transformation of the form \eqref{2}?

Let us provide a sufficient condition for such identifiability. Suppose that for some function $g$, some real $A_i,B_i,C_i$, and all $i\in[n]$ similarly to \eqref{1} we have
\begin{equation*} f_i(x)=A_i g(x+B_i)+C_i. \tag{1a}\label{1a} \end{equation*} So, letting $u:=x+b_i$, for each $i\in[n]$ and all $$u\in J_i:=(\al+b_i,1-\al+b_i)$$ we have $a_i f'(u)=A_i g'(u+B_i-b_i)$, so that (assuming $A_i\ne0$) $g'(u)=\frac{a_i}{A_i}\, f'(u+b_i-B_i)$, which latter must not depend on $i$. Assuming also that for distinct $i$ and $k$ in $[n]$ we have $J_i\cap J_k\ne\emptyset$ and $f'\ne0$ almost everywhere and \begin{equation*} \frac{f'(u+s)}{f'(u)}\text{ is not constant} \tag{3}\label{3} \end{equation*} for any $s\ne0$ and $u$ in any interval of nonzero length, we conclude that $b:=b_i-B_i$ does not depend on $i$. So, $g'(u)=\frac{a_i}{A_i}\, f'(u+b)$, whence $a:=\frac{a_i}{A_i}$ does not depend on $i$. So, $g'(u)=a f'(u+b)$ and hence $g(u)=a f(u+b)+c$ for some constant $c$. So, $f$ and $g$ are related by a transformation of the form \eqref{2}, which establishes the identifiability.

Now concerning actually finding $a_1,b_1,c_1,\dots,a_n,b_n,c_n$ such that \eqref{1} holds. To do this, one can rewrite \eqref{1} as \begin{equation*} f(u)=h_i(u):=\frac{f_i(u-b_i)-c_i}{a_i} \end{equation*} for $u\in J_i$, and then one may want to minimize (say) the total quadratic discrepancy \begin{equation*} Q:=Q(a_1,b_1,c_1,\dots,a_n,b_n,c_n):=\sum_{1\le i<j\le n}\int_{J_i\cap J_k}(h_i(u)-h_k(u))^2\,du \end{equation*} between the $h_i$'s.

Clearly, given \eqref{1}, the true minimum of $Q$ is $0$.

Note here that the condition \eqref{3} rules out the cases when $f'$ is periodic and also the cases when $f'$ is an exponential function. However, $f$ may be such that \eqref{3} holds approximately for $u$ in some small intervals. Also, even for rather small $n$, the number $3n$ of the unknowns $a_1,b_1,c_1,\dots,a_n,b_n,c_n$ is rather large, so that the search for the minimizer $(a_1,b_1,c_1,\dots,a_n,b_n,c_n)$ of $Q$ must be conducted in a space of a very large dimension, $3n$.

Furthermore, it appears that $Q$ has many local minima, some (many?) of which with values of $Q$ very close to $0$, but with the quasi-minimizer $(a_1,b_1,c_1,\dots,a_n,b_n,c_n)$ far from the true values of $(a_1,b_1,c_1,\dots,a_n,b_n,c_n)$.

E.g., if $f(x)\equiv2\cosh x$, $n=5$, $\al=1/5$, $(a_1,\dots,a_5)=(2, -1, 1, 3, -2)$, $(b_1,\dots,b_5)=(-\frac{1}{5},-\frac{2}{15},0,\frac{1}{15},\frac{1}{5})$, and $(c_1,\dots,c_5)=(0, -4, 1, 2, 3)$, Mathematica finds a quasi-minimizer of $Q$ with the value $\approx4.19\times10^{-6}$ for $Q$ but with values $\approx(-0.2,-0.2,0.022,0.2,0.2)$ for $(b_1,\dots,b_5)$ in place of the true values $(-\frac{1}{5},-\frac{2}{15},0,\frac{1}{15},\frac{1}{5})$. (This calculation, and similar ones, were done in Mathematica assuming the functions $f_i$ are known exactly. If the $f_i$'s are known only approximately, the situation will become even worse.)

It is hoped that these, mostly negative results will help the OP move in a better research direction.

$\endgroup$
3
  • $\begingroup$ Good observations. I tried to add some more conditions to my question to guarantee uniqueness of the solution... Practically, I am only interested in finding $g(x)=a f(x)+b$ for some arbitrary $a$ and $b$. $\endgroup$
    – dff
    Commented Feb 19, 2023 at 22:06
  • $\begingroup$ Thanks for the detailed answer. Interesting that Mathematica already has problems with the $n=5$ case. Can I conclude from your answer that you don't see a more algorithmic approach to solving this problem, besides looking for minimizers in a 3n dimensional space using numerical solvers? $\endgroup$
    – dff
    Commented Feb 22, 2023 at 8:15
  • $\begingroup$ @dff : You may want to try to minimize a characteristic of the discrepancy other than the quadratic characteristic $Q$ in my answer. However, I don't have a hope for that. As described in the answer, the problems are that the space to search over is high-dimensional and condition (3) may be satisfied, locally, just approximately, which can result in a large number of quasi-global minima, with values very close to $0$. BTW, somewhat unusually, the Mathematica command NMinimize that I used takes a long time in the cases I have tried, apparently trying a very large number of local minima. $\endgroup$ Commented Feb 22, 2023 at 12:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .