Re: Inversion of an algorithm

On Apr 13, 7:17 pm, Ben Bacarisse <ben.use...@xxxxxxxxx> wrote:
user923005 <dcor...@xxxxxxxxx> writes:
On Apr 13, 2:27 pm, Ben Pfaff <b...@xxxxxxxxxxxxxxx> wrote:
user923005 <dcor...@xxxxxxxxx> writes:
On Apr 12, 2:09 pm, Ben Pfaff <b...@xxxxxxxxxxxxxxx> wrote:
Willem <wil...@xxxxxxxxxxxxxx> writes:
Jean Guillaume Pyraksos wrote:
) Say I have a one-one function f from a set A to a set B. I have
) an algorithm to compute f.
) Has anyone worked on getting *automatically* an algorithm for the
) inverse function from B to A ? Or is there a deep result about that ?
) Has this problem something to do with automatic differentiation ?
)
) f is *not* specifically a math function, but a recursive one on trees.

Functions usually don't have an inverse function.  Only a very special
subclass of functions do. (Injective, I believe they're called).

Jean already said that he knows that the function is injective
(injective and one-to-one are synonyms).

That, in itself, makes it impossible to automate generically.

It is trivial to invert a one-to-one function, given some ways of
describing the function.  For example, if the function is
described using a table, then you can just rearrange the table.

It is more difficult to invert one-to-one functions described
other ways.  So far, Jean hasn't told us any details of how his
algorithm is described, so it's hard to say how much more
difficult in his case.

One to one isn't good enough.  It also has to be onto.

Why?  If there are some values in the function's range that have
no corresponding value in its domain, those are just don't-cares
in the inverse function.  No?

For a concrete example that is interesting enough to consider, think
about the function:

double f(double x)
{
   return pow( x, x );
}

Quite an interesting function, with a minimum at (1/e)^(1/e).

The domain we will consider is between (0 and 1].

Now, for every real-number value of x, there is exactly one value of
y.  (We have lots of other nice things to say about this function on
this domain -- it is smooth, continuous, and differentiable).

However, when we rotate this function about the line y = x {the
classic eyeball test to see if a function is invertible} we will see
something that will make us unhappy if we want to invert it.
That unhappy finding is that for any y value between 1.0 and (1/e)^(1/
e) there are exactly two possible values of x that will produce it.
We don't know which one it came from.

That is an example of a function that is not one-to-one.  No one was
questioning this case.  Ben Pfaff was talking about one-to-one
functions that are not also onto.  These are, it is true, not
invertible, but there is an obvious inverse implied by any such
function -- the inverse defined over the image of f rather than the
codomain of f.  I think that is what he was getting at.

There is logical problem inverting a function that is not one-to-one
but only a problem of definition inverting a one-to-one function that
is not onto.

Yes, I reversed the properties I wanted to describe. I don't know if
it was dyslexia or just stupidity.

For a function that is not onto (suppose that the extreme value for
the range is 100 and the smallest is 0) we can supply values for the
inverse that do not map to anything.
So, for instance (over the domain 0 to largest unsigned long long
value...):

double f(double x)
{
switch ((unsigned long long)x) {
case 0:
return x;
break
case 1:
return 3 * x;
break
case 2:
return 4 * x;
break
case 3:
return 5 * x;
break
case 4:
return 6 * x;
default:
return 7 * x;
}
return result;
}

This function is clearly one to one, but the inverse will have holes
in it. From 1 to 3 in the inverse domain, there are no possible
inputs that produce output.
In this case, a simple test could return EDOM, but it might be
complicated how to describe the gaps in the inverse function's domain
for other less simple functions.
Considering that he is looking at some tree counting thing, I think it
not unlikely that he will face a similar problem to this.
.

Relevant Pages

  • Re: Inversion of an algorithm
    ... Has anyone worked on getting *automatically* an algorithm for the ... inverse function from B to A? ... That unhappy finding is that for any y value between 1.0 and ^(1/ ... There is logical problem inverting a function that is not one-to-one ...
    (comp.programming)
  • Re: bilinear pairing between special groups
    ... for inverting the map ... efficient algorithm for finding the cyclic group of order q sitting ... This is not the discrete logarithm problem, since we do now know the ... could be done efficiently, but what happens with the bilinear pairing, ...
    (sci.math)
  • Re: VMPC function. Question on definition of inverting
    ... > algorithm fails to work well. ... fastest algorithm of inverting the function. ... I don't know to what extent my algorithm of inverting VMPC would be helpful. ... Bartosz Zoltak ...
    (sci.crypt)
  • Square-root Kalman Filter Algorithm
    ... Currently I am using traditional Kalman Filter algorithm for my problem ... the code has problems with inverting some matrices. ... square-root algoritm is more stable. ...
    (comp.dsp)
Loading