1

There's three components to this problem:

  1. A three dimensional vector A.
  2. A "smooth" function F.
  3. A desired vector B (also three dimensional).

We want to find a vector A that when put through F will produce the vector B.

F(A) = B

F can be anything that somehow transforms or distorts A in some manner. The point is that we want to iteratively call F(A) until B is produced.

The question is:

How can we do this, but with the least amount of calls to F before finding a vector that equals B (within a reasonable threshold)?

quano
  • 18,812
  • 25
  • 97
  • 108
  • 1
    If function F is "smooth", you can define "closeness" measure for vectors and try gradient descent or some another kind of iterative optimization algorithm. This is "un-informed search", so it is worth to generate some random vectors at first to get initial approximation – MBo Apr 21 '21 at 07:14
  • 1. brute force with least amount of iterations is not brute force at all.... 2. if `F()` is also monotonic you can use binary search if not you need different kind of search like CCD or [approximation search](https://stackoverflow.com/a/36163847/2521214) 3. the part of your post after `F(A) = B` describes entirely different problem (F is unknown) than before it (A is unknown) or its just my bad English? can you clarify ... If you want to construct `F` so it takes any `A` and converges to selected `B` ? that should be relatively easy to do. – Spektre Apr 26 '21 at 07:20
  • for example by decomposing it to scale and rotation change between `A,B` and interpolate it with some `n` steps. Also are we talking about integer, float or fixed point? how many bits, how many iterations,what range of values .. – Spektre Apr 26 '21 at 07:23
  • In this particular case, F is a matrix transformation that is missing an inverse (think linear blend skinning). You are correct, brute force was poor wording. – quano Apr 26 '21 at 20:56
  • @quano maybe you should add a sample input (with the F) ... also you still did not clear what is unknown `F` or `A` ? as half of your post suggest `A` and the other `F` – Spektre Apr 27 '21 at 07:48
  • 1
    @Spektre A is unknown. F and B are known. – quano Apr 27 '21 at 19:09
  • @quano can you share actual example of `F,B` ... linear blend skinning is not a good choice as it has much more than just 1x3D vector input ... also how many steps of Applying `F` on `A` to produce `B` ? it is fixed constant `n>=1` or stop once the result has converged ? ... – Spektre Apr 28 '21 at 07:49
  • LBS does have more inputs, but only **A** would have to change to try and find **B** (the skinning weights and bone transformation would be fixed). How many steps? As few steps as possible. It doesn't need to be fixed. Loop can break when a value within threshold has been reached. – quano Apr 29 '21 at 20:23
  • @quano Well if LBS is the `F()` then its not just a matrix operation as you suggested... and without actual example i am not confident to create an answer that might not be what you looking for because it works but not for your exact `F` case ... – Spektre Apr 30 '21 at 07:19

3 Answers3

3

I am assuming that what you call "smooth" is tantamount to being differentiable. Since the concept of smoothness only makes sense in the rational / real numbers, I will also assume that you are solving a floating point-based problem.

In this case, I would formulate the problem as a nonlinear programming problem. i.e. minimizing the squared norm of the difference between f(A) and B, given by

(F(A)_1 -B_1)² + (F(A)_2 - B_2)² + (F(A)_3 - B_3)²

It should be clear that this expression is zero if and only if f(A) = B and positive otherwise. Therefore you would want to minimize it.

As an example, you could use the solvers built into the scipy optimization suite (available for python):

from scipy.optimize import minimize

# Example function
f = lambda x : [x[0] + 1, x[2], 2*x[1]]

# Optimization objective
fsq = lambda x : sum(v*v for v in f(x))

# Initial guess
x0 = [0,0,0]

res = minimize(fsq, x0, tol=1e-6)

# res.x is the solution, in this case
# array([-1.00000000e+00,  2.49999999e+00, -5.84117172e-09])

A binary search (as pointed out above) only works if the function is 1-d, which is not the case here. You can try out different optimization methods by adding the method="name" to the call to minimize, see the API. It is not always clear which method works best for your problem without knowing more about the nature of your function. As a rule of thumb, the more information you give to the solver, the better. If you can compute the derivative of F explicitly, passing it to the solver will help reduce the number of required evaluations. If F has a Hessian (i.e., if it is twice differentiable), providing the Hessian will help as well.

As an alternative, you can use the least_squares function on F directly via res = least_squares(f, x0). This could be faster since the solver can take care of the fact that you are solving a least squares problem rather than a generic optimization problem.

From a more general standpoint, the problem of restoring the function arguments producing a given value is called an Inverse Problem. These problems have been extensively studied.

hfhc2
  • 4,182
  • 2
  • 27
  • 56
  • in case of convergence of repeated application of `A=F(A)` into `B` as OP described your solution would most likely not work ... – Spektre Apr 28 '21 at 07:53
2

Provided that F(A)=B, F,B are known and A remains unknown, you can start with a simple gradient search:

F(A)~= F(C) + F'(C)*(A-C)~=B

where F'(C) is the gradient of F() evaluated in point C. I'm assuming you can calculate this gradient analytically for now.

So, you can choose a point C that you estimate it is not very far from the solution and iterate by:

C= Co;
While(true)
{
   Ai = inverse(F'(C))*(B-F(C)) + C;
   convergence = Abs(Ai-C);
   C=Ai;

   if(convergence<someThreshold)
      break;
}

if the gradient of F() cannot be calculated analytically, you can estimate it. Let Ei, i=1:3 be the ortonormal vectors, then

   Fi'(C) = (F(C+Ei*d) - F(C-Ei*d))/(2*d);
   F'(C) = [F1'(C) | F2'(C) | F3'(C)];

and d can be chosen as fixed or as a function of the convergence value.

These algorithms suffer from the problem of local maxima, null gradient areas, etc., so in order for it to work, the start point (Co) must be not very far from the solution where the function F() behaves monotonically

Amo Robb
  • 810
  • 5
  • 11
0

it seems like you can try a metaheuristic approach for this. Genetic algorithm (GA) might be the best suite for this. you can initiate a number of A vector to init a population, and use GA to make evolution on your population, so you will have better generation in which they have better vectors that F(Ax) closer to B. Your fitness function can be a simple function that compare F(Ai) to B You can choose how to mutate your population by each generation.

A simple example about GA can be found here link

Thọ Đỗ Xuân
  • 140
  • 5