Approximately inverting functions with Monte Carlo methods

Question

I have the following problem: Let $f:\mathbb{R}^n \rightarrow \mathbb{R}^m$ with $n>m$ be a smooth function. I want to find input vectors $x \in \mathbb{R}^n$ which yield a given output $y\in \mathbb{R}^m$, so $f(x)=y$. My idea was to start at a random vector $x_0 \in \mathbb{R}^n$ and try to iteratively decrease the $L^2$-norm of the differences, so that for any $n$ we have $||f(x_{n+1})-y)||_2<||f(x_n)-y)||_2$. Would this be possible with some kind of Monte Carlo approach? Or are there any existing approaches that could be used for tackling this problem? Thanks in advance!

Answer 1

One approach is to solve the optimization problem $$ \text{minimize} \quad \frac12 \| f(x) - y \|_2^2. $$ The optimization variable is $x \in \mathbb R^n$. This optimization problem could be solved with a method such as gradient descent or Newton's method or Levenberg-Marquardt. Gradient descent is a simple way to go.

The derivative of the objective function $F(x) = \frac12 \| f(x) - y \|_2^2$ is $$ F'(x) = (f(x) - y)^T f'(x). $$ The $m \times n$ matrix $f'(x)$ is also called the Jacobian of $f$ at $x$. If we use the convention that the gradient of $F$ is a column vector then \begin{align} \nabla F(x) &= F'(x)^T \\ &= f'(x)^T (f(x) - y). \end{align} The gradient descent iteration is $$ x^{k+1} = x^k - t \nabla F(x^k). $$ If the step size $t > 0$ is sufficiently small then the iterates $x^k$ will converge to a local minimizer of $F$. There is a danger that we could get trapped in a local minimum, but if the initial guess $x^0$ is good enough then we have a good shot at converging to a value of $x$ that satisfies $f(x) = y$.