Given a nonlinear function $f : \mathbb{R}^n \rightarrow \mathbb{R}$.
My goal is to reduce the number of arguments that this function takes using only linear combinations of its original arguments. Let $x \in \mathbb{R}^n$ be the original arguments and
$$ \tilde{x} = A x $$
the "reduced" arguments $\tilde{x} \in \mathbb{R}^m$ with $A \in \mathbb{R}^{m \times n}$ and $m \leq n$. So the task is then to find $A$ and $g : \mathbb{R}^m \rightarrow \mathbb{R}$ such that $g(\tilde{x}) = f(x) \, \forall x \in \mathbb{R}^n$ and that $m$ is as small as possible.
Example 1: Take $f : \mathbb{R}^4 \rightarrow \mathbb{R}$ with
$$ f(x) = (x_1 + x_2)^2 + (x_3 - x_4)^2 $$
It is now easy to choose a linear combination to reduce the number of arguments of $f$ by
$$ \tilde{x} = \begin{bmatrix} \tilde{x}_1 \newline \tilde{x}_2 \end{bmatrix} = A x = \begin{bmatrix} 1 & 1 & 0 & 0 \newline 0 & 0 & 1 & -1 \end{bmatrix} \begin{bmatrix} x_1 \newline x_2 \newline x_3 \newline x_4 \end{bmatrix} = \begin{bmatrix} x_1 + x_2 \newline x_3 - x_4 \end{bmatrix} $$
So we can rewrite $f$ as the function $g : \mathbb{R}^2 \rightarrow \mathbb{R}$ in terms of the new arguments as
$$ g(\tilde{x}) = \tilde{x}_1^2 + \tilde{x}_2^2 $$
Now $g$ is a function of only 2 arguments, so $m < n$ because $2 < 4$. I assume that this is also the smallest $m$ possible here.
Example 2: Take $f : \mathbb{R}^4 \rightarrow \mathbb{R}$ with
$$ f(x) = x_1 x_2 x_3 x_4 $$
Here, I see no possiblity to reduce the number of arguments somehow using the described technique. So I would assume that here, the smallest possible $m = n = 4$.
Questions: Three questions basically.
- Is there a way to always find the smallest $m$, the related $A$ matrix and $g$ function?
- If not, a way to find some $m < n$, if it exists, the related $A$ matrix and $g$ function?
- Is this a known (or related to a known) problem? If yes, references are appreciated.
Note: The two examples are multivariate polynomials, but I would be also interested in a solution for non-polynomial $f$.
Let $f$ be a function of $n$ variables $x_{1},x_{2} ... x_{n}$, and $y_{1}, y_{2} .. y_{m}$ be a linear combinations of those variables, such that $f$ can be written entirely from them. Ie. $f(x_1,x_2 ,... x_n) = f^{*}(y_{1}, y_{2} .. y_{m})$ .
You have to consider that with respect to these new variables, $f$ has an $n-m$ dimensional "directions" on which it remains constant. If we find the subspace spanned by those of those directions, then a basis for any complement of it will give us a good set of $(y_{1}, y_{2} .. y_{m})$.
Consider the gradient $\nabla f$ . To find the directions under which $f$ is constant, you find the space S of vectors $v_{k}\in S$ such that $\forall x_1,x_2,..x_n, <\nabla f(x1,..x_n), v_{k}> = 0$
The dimention of $S$ is the number of variables you can eliminate. Eg, for $$ f(x) = (x_1 + x_2)^2 + (x_3 - x_4)^2$$ $$\nabla f = (2(x_1+x_2),2(x_1+x_2), 2(x_3 - x_4), 2(x_3 - x_4))$$ We see that this is orthogonal to vectors spanned by $(1,-1,0,0), (0,0,1,-1)\forall x_1,x_2,x_3,x_4$, giving us 2 variables to eliminate,
To compute the number of variables that the problem can be reduced to we need to take $n$ variables $X_1, X_2, ... X_n \in {\mathbb R}^n$, then compute the rank of the matrix $[\nabla f(X_1),\nabla f(X_2) ... \nabla f(X_n)]$ . For example, if its determinant is always 0, then at least one variable can be eliminated,as its rank is no greater than $n-1$. This is tedious as there are a lot of variables, but doable for a wide variety of symbolic expressions.