6
$\begingroup$

I'm having a difficult time finding any theory on an inverse problem I've come up against. Let's say I have an unknown function $f:[0,1] \rightarrow \mathbb{R}$, and I know $\int_{a}^{b} f$ for some collection $A$ of pairs $(a,b)\in[0,1]^2$. I'm looking for pointers to any material that discusses condtions on $f$ and $A$ that are sufficient recover (all of? some of?) the values of $f$. Google searches just keep turning up elementary-calculus-help-type pages. I'm a beginning graduate student, if it matters. Thanks.

Edit: I'm actually looking for something broader than I asked for. I know that recovering the values of $f$ is a lot to ask and is very unlikely unless $A=[0,1]^2$; I'm also looking for approximations to $f$, anything that can be said about its properties/behaviour, etc. when $A\subsetneqq [0,1]^2$.

$\endgroup$
  • 1
    $\begingroup$ Well, if $f$ is integrable, then the integral is jointly continuous in $a$ and $b$, so dense sets suffice. So for instance $\{0\} \times \mathbb{Q}$ would work. $\endgroup$ – Nate Eldredge Feb 5 '18 at 0:00
  • 2
    $\begingroup$ Recovery of function from its integral is called differentiation (Newton-Leibniz formula). $\endgroup$ – Alexandre Eremenko Feb 5 '18 at 0:27
  • 2
    $\begingroup$ If $A=\{0\}\times[0,1]$, you’re in business also. Otherwise, maybe you could set this up as an optimization problem: find the “simplest “ function satisfying certain constraints, whatever your definition of simple is. Finally, why not work with the anti derivative, $F$ instead of with $f$? Your conditions immediately give you information about $F$. $\endgroup$ – Anthony Quas Feb 5 '18 at 1:00
  • $\begingroup$ Is $f$ assumed continuous? $\endgroup$ – LSpice Feb 5 '18 at 16:14
  • 1
    $\begingroup$ Could you add a little more detail on the background of the problem? Is this a theoretical question or a practical one? Do you assume "exact data" (i.e. the values $\int_a^b f$ are exact)? Any more information about $A$? If you aim at approximations of $f$, do you aim at error bounds or just convergence? What do you assume about $f$? (Barely integrable, continuity, smoothness, bounds on derivatives,…?) Up to now, the answers seem to poke around not knowing for what to look… $\endgroup$ – Dirk Feb 5 '18 at 16:57
5
$\begingroup$

Here is how you make an inverse problem of this problem: Choose a space $X$ for the function $f$ you are looking for (e.g. $L^2(0,1)$ to work in Hilbert spaces, but other spaces may be more suitable, depending on your needs).

I assume that you only have finitely many definite integrals (since I assume that this is a practical problem where the definite integrals come from measurements). Now let us denote your tuples as $(a_1,b_1),\dots (a_N,b_N)$. You forward operator is $$\newcommand{\RR}{\mathbb{R}} K:X\to\RR^N $$ mapping $f$ to the $N$-vector with components $\int_{a_i}^{b_i}f(x)\,dx$. So you are given a vector $g\in\RR^N$ and want some solution to $$ Kf = g. $$ Now you are in business with the standard theory for linear inverse problems.

You have some of the usual problems coming with an inverse problem: Non-uniqueness (the operator is not injective) and probably instability in some sense (depending on you data and values $(a_i,b_i)$). (As far as I see, non-solvability should not be an issue as $K$ should be surjective for meaningful tupels $(a_i,b_i)$).

To deal with non-uniqueness: You may view this as an advantage as you can choose among all solutions of $Kf=g$. To pick one, you can choose regularization functional $R:X\to [0,\infty]$ and define a minimum-$R$-solution as solution of $$ \min\{R(f)\mid f\in X,\ Kf=g\}. $$ From a computational point of view, convex functional $R$ are beneficial and you can choose $R$ to impose some structure on your solution, e.g. $R(f) = \int_0^1 |f'(x)|^2\, dx$ imposes some smoothness (effectively this means that you constrain your solutions to the Sobolev space $H^1$). The most straight-forward choice would be $R(f) = \int_0^1 |f(x)|^2\, dx$ which should produce a linear equality as optimality condition (and you are effectively computing the Moore-Penrose pseudo-inverse). I could say more about regularizing functionals if needed.

If your data vector $g$ is also uncertain, i.e. it may be given by measurement data with an error, you may want to relax your problem and look for solutions of $$ \min\{R(f)\mid d(Kf,g)\leq\delta\} $$ for some discrepancy functional $d$ and some value $\delta>0$. Both should be related to the error in your data. Note that this is in some way equivalent to (generalized) Tikhonov regularization which would be solving $$ \min_f d(Kf,g) + \lambda R(f) $$ for some regularization parameter $\lambda>0$. The most simple case of this would be standard Tikhonov regularization in Hilbert spaces: $$ \min_f \|Kf-g\|_{2}^2 + \lambda\|f\|_{L^2(0,1)}^2 $$ leading to the linear optimality condition $$ K^*(Kf-g) + \lambda f = 0. $$ The adjoint operator $K^*:\RR^N\to L^2(0,1)$ is given by $$ K^*g = \sum_{i=1}^N g_i\chi_{[a_i,b_i]} $$ (where $\chi_{[a_i,b_i]}$ is the characteristic function of $[a_i,b_i]$). So the optimality condition is actually $$ \sum_i \left[\langle f,\chi_{[a_i,b_i]}\rangle - g_i\right]\chi_{[a_i,b_i]} + \lambda f = 0. $$ This shows that the regularized solution is also a linear combination of the characteristic functions $\chi_{[a_i,b_i]}$ and thus, we still get a finite dimensional linear problem for the coefficients.

If you want some smoothness, try $R(f) = \int_0^1 |f'(x)|^2\, dx$. This would give an optimality conditions like $$ \sum_i \left[\langle f,\chi_{[a_i,b_i]}\rangle - g_i\right]\chi_{[a_i,b_i]} - \lambda f'' = 0 $$ and thus the solution is piecewise quadratic.

$\endgroup$
  • $\begingroup$ It's not clear whether the set $A$ of sample pairs is meant to be finite. $\endgroup$ – LSpice Feb 5 '18 at 16:15
  • $\begingroup$ @lspice Sure. Somehow my gut tells me that this is an applied math question where many things are open and open to modelling (whick would imply a finite number of data points) but I may well be wrong... $\endgroup$ – Dirk Feb 5 '18 at 16:27
2
$\begingroup$

In general, it appears that hardly anything interesting can be said. E.g., let $A=\{(1/5,3/5),(2/5,4/5)\}$; here, it will be convenient to think of $A$ as a set of (say) open intervals, rather than a set of pairs of endpoints of intervals.

However, note first that, without loss of generality, for each open interval in $A$, all the intervals (closed, left-open, right-open) with the same endpoints may be assumed to belong to $A$. Next, let us assume that $\int_0^1|f|<\infty$ and that $A$ is a semi-ring (see measures on semi-rings) and $[0,1]\in A$. Then the formula $\mu(I):=\int_I f$ for $I\in A$ defines a finite signed countably-additive measure $\mu$ on $A$, which can be uniquely extended to a signed measure $\bar\mu$ on the sigma-algebra $\Sigma$ generated by $A$.

The measure $\bar\mu$ determines, and is determined by, the conditional expectation $E(f|\Sigma)$ (of $f$ given $\Sigma$), equal the Radon--Nikodym derivative $\dfrac{d\bar\mu}{d\lambda|_\Sigma}$ (with respect to the underlying Lebesgue measure $\lambda$ over $[0,1]$), and this conditional expectation is then precisely all that we can get from the knowledge of the map $A\ni I\mapsto \int_I f$. (One might note that the appearance of the Radon--Nikodym derivative here is in broad agreement with the comment "Recovery of function from its integral is called differentiation" by Alexandre Eremenko.)

E.g., if $A$ consists of all intervals with endpoints in the set $\{j/n\colon j=0,\dots,n\}$, then all that we will know is, in essence, the "histogram" of the average values of $f$ over the intervals $[0,1/n],\dots,[1-1/n,1]$, and this "histogram" is the best approximation to $f$ that we can get in this case.

Extended comment: Dirk suggested an inverse-problem approach. One may note that such an approach will work perfectly well (and, generally, even better) within the above framework of the conditional expectation. Indeed, for a space $X$ of (say) real-valued integrable functions on $[0,1]$ we have the map $X\overset K\to\mathbb R^A$ defined by the formula $Kf:=(\int_I f)_{I\in A}$ for $f\in X$. This map can be factored as follows: \begin{equation} X\overset{E(\cdot|\Sigma)}\longrightarrow X_\Sigma\overset{K_\Sigma}\longrightarrow\mathbb R^A, \end{equation} where $X_\Sigma$ is the set of all integrable $\Sigma$-measurable functions in $X$ and $K_\Sigma$ is the restriction of $K$ to $X_\Sigma$; indeed, by the definition of the conditional expectation/Radon--Nikodym derivative, we have
$K_\Sigma E(f|\Sigma)=Kf$ for all $f\in X$. Thus, instead of $K$, one can deal with its restriction $K_\Sigma$, with the same (or greater) degree of success. In particular, if $A$ is finite, then we have to deal with the finite-dimensional space $X_\Sigma$ instead of the possibly infinite-dimensional space $X$.

This comment may be viewed as an illustration of what was said previously: that the conditional expectation $E(f|\Sigma)$ is precisely all that we can get from the knowledge of the map $A\ni I\mapsto \int_I f$.

$\endgroup$
  • $\begingroup$ I have added an extended comment about an inverse-problem approach. $\endgroup$ – Iosif Pinelis Feb 5 '18 at 13:17
  • $\begingroup$ Nice! Do I see correctly that $X_\Sigma$ contains functions that are piecewise constant in the case where $A$ is finite? In this case, a regularization may be in order if one aims at a different structure. $\endgroup$ – Dirk Feb 5 '18 at 13:22
  • $\begingroup$ @Dirk : Right, $X_\Sigma$ will consist of piecewise constant functions if $A$ is finite, and then one may indeed want to regularize/smooth those functions. $\endgroup$ – Iosif Pinelis Feb 5 '18 at 13:32
0
$\begingroup$

If $A$ is infinite and dense then you can find the function exactly by taking limits. I'll look at the finite case. In the event that the function is a polynomial of degree $n$ then knowing the integral over $n+1$ internally disjoint intervals is enough for recovery. Without knowing that the function is a polynomial , but given $n+1$ integrals one could find the unique polynomial of degree $n$ that matches the data. Or the polynomial of degree $n-m$ that best fits.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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