# Automatic inverse of a function?

**URL:** <https://discourse.julialang.org/t/automatic-inverse-of-a-function/53342>\
**Category:** Optimization (Mathematical)\
**Created:** [January 14, 2021, 5:07pm UTC](https://discourse.julialang.org/t/automatic-inverse-of-a-function/53342 "2021-01-14T17:07:31Z")\
**Posts on this page:** 18\
**Page:** 1

<div class="post-metadata">

**Author:** ![lrnv](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lrnv/32/19373_2.png) [@lrnv](https://discourse.julialang.org/u/lrnv)\
**Post date:** [January 14, 2021, 5:07pm UTC](https://discourse.julialang.org/t/automatic-inverse-of-a-function/53342/1 "2021-01-14T17:07:31Z")

</div>

Hey,

I do have a function that makes a heavy computation in Julia, from \mathbb R^n to \mathbb R^m. It uses loops, multiplications, additions, divisions, substractions, powers and exp/log.

I am looking to inverse the function. I can carry out the inverse when the number of parameters and outputs is small, but when it gets larger i cannot by hand, and the combinatorics are hard.

Is there somewhere a software that could carry out the inversion for me ? I am not very informed about what kind of methods exists, which makes searching for implementation harder.But since Julia has awsome automatic differentation things, my guess is that someone came with this problem before me 🙂

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [January 14, 2021, 5:28pm UTC](https://discourse.julialang.org/t/automatic-inverse-of-a-function/53342/2 "2021-01-14T17:28:18Z")

</div>

Unfortunately, this is basically impossible. The problem is that most functions (eg `f(a,b)=a+b`) are not invertible.

---

<div class="post-metadata">

**Author:** ![lrnv](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lrnv/32/19373_2.png) [@lrnv](https://discourse.julialang.org/u/lrnv)\
**Post date:** [January 14, 2021, 5:30pm UTC](https://discourse.julialang.org/t/automatic-inverse-of-a-function/53342/3 "2021-01-14T17:30:49Z")

</div>

I hear you, yes. subpieces of the algorithm might not be invertibles. But what if the global algorithm is, indeed, invertible ? I mean, f(a,b) = (a+b, exp(a+2b)) is invertible, and you could get more creative.

---

<div class="post-metadata">

**Author:** ![mcabbott](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mcabbott/32/6603_2.png) [@mcabbott](https://discourse.julialang.org/u/mcabbott)\
**Post date:** [January 14, 2021, 6:19pm UTC](https://discourse.julialang.org/t/automatic-inverse-of-a-function/53342/4 "2021-01-14T18:19:43Z")

</div>

Maybe you can use:

[https://github.com/GiggleLiu/NiLang.jl](https://github.com/GiggleLiu/NiLang.jl)

---

<div class="post-metadata">

**Author:** ![lrnv](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lrnv/32/19373_2.png) [@lrnv](https://discourse.julialang.org/u/lrnv)\
**Post date:** [January 14, 2021, 6:27pm UTC](https://discourse.julialang.org/t/automatic-inverse-of-a-function/53342/5 "2021-01-14T18:27:33Z")

</div>

> [@mcabbott](#):
>
> Maybe you can use:
> 
> ![](https://github.githubassets.com/favicons/favicon.svg) [github.com](https://github.com/GiggleLiu/NiLang.jl)
> 
> ![](https://global.discourse-cdn.com/julialang/original/3X/9/b/9b45d4b45d96bb69742209f4b5a290dca0e8c889.png)
> 
> ### [GiggleLiu/NiLang.jl](https://github.com/GiggleLiu/NiLang.jl)
> 
> A differential eDSL that can run faster than light and go back to the past.

It seems like this is not what i want: it restores the input of a function (which is amazing), but does not compute the inverse operation to be applicable to other arguments.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [January 14, 2021, 6:43pm UTC](https://discourse.julialang.org/t/automatic-inverse-of-a-function/53342/6 "2021-01-14T18:43:55Z")

</div>

How do you know that the complete algorithm is invertible, though, if you can’t see that “by hand”? You would need some algorithmic way to determine that.

There is very nice work by @zennatavares on [parametric inversion](https://github.com/zenna/ParametricInversion.jl).

You can also try [IntervalConstraintProgramming.jl](https://github.com/JuliaIntervals/IntervalConstraintProgramming.jl), which you can think of as giving a set-valued inverse of a function evaluated over a given set, which is all that you can hope for in general.

---

<div class="post-metadata">

**Author:** ![zennatavares](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zennatavares/32/6205_2.png) [@zennatavares](https://discourse.julialang.org/u/zennatavares)\
**Post date:** [January 14, 2021, 7:01pm UTC](https://discourse.julialang.org/t/automatic-inverse-of-a-function/53342/7 "2021-01-14T19:01:38Z")

</div>

If you’re looking to solve for a particular input then @dpsanders interval constraint programming is a good way to go. If that doesn’t work you could try relaxing the problem.

If you’re trying to actually invert the function there are a few options.

Sounds like your example is “partially” invertible. See this paper [https://dl.acm.org/doi/10.1145/3409000](https://dl.acm.org/doi/10.1145/3409000)

I’m not sure they have a tool though.

Finally I’m looking for benchmarks to try parametric inversion on so if you can send me an example I can take a look.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [January 15, 2021, 1:18am UTC](https://discourse.julialang.org/t/automatic-inverse-of-a-function/53342/8 "2021-01-15T01:18:46Z")

</div>

For a very simple proof that automatic inversion is generally impossible (even for invertible functions), consider that RSA encryption is invertible. If you can invert this automatically you will get several million dollars and a job at any tech company you want.

---

<div class="post-metadata">

**Author:** ![DrPapa](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/drpapa/32/6835_2.png) [@DrPapa](https://discourse.julialang.org/u/DrPapa)\
**Post date:** [January 15, 2021, 1:13pm UTC](https://discourse.julialang.org/t/automatic-inverse-of-a-function/53342/9 "2021-01-15T13:13:42Z")

</div>

I agree in general, but isn’t the idea that it is possible to modify the function of interest such that it is invertible by returning extra information about internal states?

E.g. instead of doing \mathbb{R}\times\mathbb{R}\overset{f}{\rightarrow}\mathbb{R} you do \mathbb{R}\times\mathbb{R}\overset{g}{\rightarrow}\mathbb{R}\times\mathbb{R}

```julia
f(a,b) = a+b

```

vs

```julia
g(a,b) = (a+b, b)

```

For the RSA example, I would think that you could invert it IF you had access to intermediate states. Which obviously you don’t have. But you could write it so it was available.

---

<div class="post-metadata">

**Author:** ![antoine-levitt](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/antoine-levitt/32/4008_2.png) [@antoine-levitt](https://discourse.julialang.org/u/antoine-levitt)\
**Post date:** [January 15, 2021, 3:46pm UTC](https://discourse.julialang.org/t/automatic-inverse-of-a-function/53342/10 "2021-01-15T15:46:48Z")

</div>

I don’t understand the original question, but what you usually do to invert a differentiable function f is to find a zero of g(x) = f(x) - y, eg with Newton method.

---

<div class="post-metadata">

**Author:** ![lrnv](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lrnv/32/19373_2.png) [@lrnv](https://discourse.julialang.org/u/lrnv)\
**Post date:** [January 15, 2021, 5:04pm UTC](https://discourse.julialang.org/t/automatic-inverse-of-a-function/53342/11 "2021-01-15T17:04:42Z")

</div>

> [@antoine-levitt](#):
>
> I don’t understand the original question, but what you usually do to invert a differentiable function f is to find a zero of g(x) = f(x) - y, eg with Newton method.

You are totaly right. My OP was silly.

---

<div class="post-metadata">

**Author:** ![patrick-kidger](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/patrick-kidger/32/20378_2.png) [@patrick-kidger](https://discourse.julialang.org/u/patrick-kidger)\
**Post date:** [January 15, 2021, 5:23pm UTC](https://discourse.julialang.org/t/automatic-inverse-of-a-function/53342/12 "2021-01-15T17:23:43Z")

</div>

This sort of thing can be doable, by writing a system based around a collection of invertible primitives.

As a simple example:

```julia
f(a, b) = (a + b, b)
f_inv(a, b) = (a - b, b)

g(a, b) = (a * b, b)
g_inv(a, b) = (a / b, b)

function myfunction(a, b)
    for j = 1:100
        a, b = f(a, b)
        if j in (7, 19)
            a, b = b, a
        end
        if j in (5, 32)
            a, b = g(a, b)
        end
    end
    return a, b
end

function myfunction_inv(a, b)
    for j = 100:-1:1
        if j in (5, 32)
            a, b = g_inv(a, b)
        end
        if j in (7, 19)
            a, b = b, a
        end
        a, b = f_inv(a, b)
    end
    return a, b
end

```

With a little clever engineering you can make it so that you don’t have to write `myfunction_inv` by hand (and have it autogenerated based on the invertible primitives you provide). Doing so would be very similar to writing an autodifferentiation system (just that you’re using invertible primitives rather than differentiable primitives) so the same sorts of methods apply: e.g. source-to-source transformations like Zygote; or by dynamically building up a computation graph like in PyTorch.

---

<div class="post-metadata">

**Author:** ![mcabbott](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mcabbott/32/6603_2.png) [@mcabbott](https://discourse.julialang.org/u/mcabbott)\
**Post date:** [January 15, 2021, 6:22pm UTC](https://discourse.julialang.org/t/automatic-inverse-of-a-function/53342/13 "2021-01-15T18:22:25Z")

</div>

> [@patrick-kidger](#):
>
> This sort of thing can be doable

Or, has been done. Using the package I linked above:

```julia
julia> @i f(a, b) = a += b

julia> f(3, 5)
(8, 5)

julia> (~f)(8, 5) # inverse
(3, 5)

julia> @i g(a, b) = a *= b

julia> g(7, 9)
ERROR: MethodError: no method matching (::MulEq{typeof(identity)})(::Int64, ::Int64)
Closest candidates are:
  (::MulEq{typeof(identity)})(::ULogarithmic, ::Real) at /Users/me/.julia/packages/NiLang/5Z72s/src/ulog.jl:13

```

Note that your `g` isn’t invertible, because `b` might be zero, so it won’t allow it.

---

<div class="post-metadata">

**Author:** ![lrnv](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lrnv/32/19373_2.png) [@lrnv](https://discourse.julialang.org/u/lrnv)\
**Post date:** [January 15, 2021, 6:34pm UTC](https://discourse.julialang.org/t/automatic-inverse-of-a-function/53342/14 "2021-01-15T18:34:07Z")

</div>

> [@mcabbott](#):
>
> Or, has been done. Using the package I linked above:

It is not quite the same thing, as your example show: You have to compute f(3,5) before being able to compute ~f(f(3,5)). You cannot compute directly ~f(x,y) for any x,y

---

<div class="post-metadata">

**Author:** ![mcabbott](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mcabbott/32/6603_2.png) [@mcabbott](https://discourse.julialang.org/u/mcabbott)\
**Post date:** [January 15, 2021, 7:07pm UTC](https://discourse.julialang.org/t/automatic-inverse-of-a-function/53342/15 "2021-01-15T19:07:59Z")

</div>

Sure, I agree this isn’t what everyone means by inverse, at all times. It won’t crack RSA for you, but it is a working implementation of precisely the kind of reverse computation I was quoting.

---

<div class="post-metadata">

**Author:** ![smldis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/smldis/32/1735_2.png) [@smldis](https://discourse.julialang.org/u/smldis)\
**Post date:** [January 19, 2021, 12:41pm UTC](https://discourse.julialang.org/t/automatic-inverse-of-a-function/53342/16 "2021-01-19T12:41:35Z")

</div>

If you don’t find a symbolic solution either by hand or by using a software (sympy, maple, mathematica, …),  
you can always consider the numerical approach:  
given Y= f(X) where f is your julia function and your Y₀,  
search the solutions of `f(X)-Y₀ = 0` with a numerical algorithm every time you want the “inverse”.  
This problem could also be formulated as a nonlinear minimization of (f(X)-Y₀)², see NLopt.jl and JuMP.jl for the software.

---

<div class="post-metadata">

**Author:** ![liuyxpp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/liuyxpp/32/9870_2.png) [@liuyxpp](https://discourse.julialang.org/u/liuyxpp)\
**Post date:** [January 19, 2021, 1:04pm UTC](https://discourse.julialang.org/t/automatic-inverse-of-a-function/53342/17 "2021-01-19T13:04:39Z")

</div>

Very nice! Or even better, since you can translate the inverse problem to an optimization problem, machine learning techniques are ready for the work. lol.

---

<div class="post-metadata">

**Author:** ![rafael.guerra](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rafael.guerra/32/216610_2.png) [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)\
**Post date:** [January 19, 2021, 5:28pm UTC](https://discourse.julialang.org/t/automatic-inverse-of-a-function/53342/18 "2021-01-19T17:28:51Z")

</div>

This is basically the same answer as @antoine-levitt