Approximately inverting functions with Monte Carlo methods 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!
 A: 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$.
