18
$\begingroup$

I am looking for an analytic function that approximates the minimum function. i.e.,

$|f(x_1,x_2) - \min(x_1,x_2)| < \zeta$ for some $\zeta$ that may be related to $|x_1 - x_2|$. Or may be a series $f_1,f_2,....$, where $\lim_{n \to \infty} \zeta = 0$.

$\endgroup$
1
  • 9
    $\begingroup$ I don't think the word analytic is what you're looking for. Anyway: $\min(a,b)=(a+b-|a-b|)/2$. $\endgroup$ Commented Apr 4, 2011 at 8:16

4 Answers 4

18
$\begingroup$

Note that you can easily switch between max and min as $\min(x, y) = - \max(-x, -y)$.

In various computer graphics applications, or in optimization problems, there are various "smooth" or "soft" maximum and minimum functions. In the graphics context they are used purely for aesthetics to eliminate ugly discontinuities. In the optimization problems they're used to give a nicer related function that the optimizers handle better than the true function.

One such common softmax is $\log(\exp(x) + \exp(y))$. Rescaling by $k$ sets a scale for the fuzziness: $\log(\exp(kx) + \exp(ky))/k$. This has the nice property that it approaches the larger of $x$ and $y$ when they are greatly different, but has the bad property that it is off by $\log 2$ when they are equal.

The maximum is also the $p = \infty$ limit of the generalized mean/power means. Conversely, the $p = -\infty$ limit is the minimum.

(There is also a softmax activation function which turns numbers into weights of the various choices. It's really a soft selection of the maximum, so is perhaps misnamed. This is not what you want though it is related -- using the weights for a sum of inputs gives something reasonable.)

$\endgroup$
4
  • 1
    $\begingroup$ The generalized mean, and softmax are probably something similar to what I am looking for, since this is for an applied work (modeling), and I wanted something that is hopefully not an eyesore(?) and can be extended to more than two arguments. $\endgroup$ Commented Apr 4, 2011 at 17:03
  • 1
    $\begingroup$ I think it is off by $\frac{log 2}{k}$ when equal. $\endgroup$
    – vonjd
    Commented Mar 7, 2013 at 16:15
  • $\begingroup$ If you take $\log(\exp(kx) + \exp(ky)$, multiply by $k$ and subtract the derivative with respect to $k$ divided by k, you end up with my proposed answer and the troubling $\log 2$ goes away. $\endgroup$
    – alfC
    Commented Dec 10, 2013 at 9:42
  • 1
    $\begingroup$ There is actually a function for this in SciPy: scipy.github.io/devdocs/generated/scipy.misc.logsumexp.html $\endgroup$
    – endolith
    Commented Mar 6, 2017 at 0:43
18
$\begingroup$

Following Raskolnikov's hint it is enough to produce an analytic approximation to the absolute value function. Here the functions $f_\epsilon(x):=\sqrt{x^2+\epsilon^2}$ come handy; they differ from $|x|$ by at most $\epsilon$ on all of ${\mathbb R}$. If $|x|$ is bounded a priori, say $|x|\leq 1$, then you even can replace the $f_\epsilon$ by suitable polynomials $q_\epsilon(x^2)$.

$\endgroup$
1
  • 3
    $\begingroup$ To be explicit, the polynomials $q_n(x):=1-\sum_{j=1}^n \left|{1/2\choose n}\right| (1-x^2)^j$ decrease uniformly to the absolute value function on $[-1,1]$. If you like, you can subtract the value at $x=0$, i.e., ${2n \choose n}/4^n$ to get polynomials $p_n$ with $p_n(0)=0$. $\endgroup$
    – user940
    Commented Apr 4, 2011 at 12:19
12
$\begingroup$

The only function that I know has this property is essentially

$$\max(x, y) \sim \frac{x e^{kx} + y e^{ky}}{e^{kx} + e^{ky}}$$

for large $k$.

(@wnoise was close to the answer. In this case there is no problem if $x=y$.)

This works for positive or negative numbers and tends to the maximum for $k\to\infty$. Other formulas based on powers are only valid for positive numbers (as $\sqrt[n]{x^n + y^n}$).

The integral counterpart is

$$ \frac{\int{f(x) e^{kf(x)} dx}}{\int{e^{kf(x)} dx}} $$

There is a small caveat if you want to implement this numerically you need to have an estimate of the maximum in the first place (and integrate over shifted values), otherwise the the integral (or even the sum) is going to under/overflow pretty easily.

This is related to the Laplace's method. Note that I asked a related question:

Real approximation to the maximum using Laplace's method integral

$\endgroup$
8
  • $\begingroup$ The formula based on power gives numer higher than the maximum value in some cases, do you have an explanation for this ? $\endgroup$
    – Feras
    Commented Oct 27, 2017 at 22:33
  • $\begingroup$ @Feras, do you have an example? are you talking about the first formula? $\endgroup$
    – alfC
    Commented Oct 28, 2017 at 1:26
  • $\begingroup$ I can't write and example here in a comment. Just generate random an array of big size let's say (100,100) and apply the formula of $pow(sum(pow(xi,n)),1/n)$ using n= 4. you'll see the answer is far from the hard maximum $\endgroup$
    – Feras
    Commented Oct 28, 2017 at 8:06
  • $\begingroup$ @Feras, first, I don't advocate to use $\sqrt[n]{\sum_i x_i^n}$, I propose something different. Second, what you describe looks like a numerical problem, for example if you use floating point, you can easily overflow or loose precision. What you do in that case is to normalize, and calculate this instead $|M| \sqrt[n]{\sum_i (x_i/|M|)^n}$, where $M$ is for example $max(x_i)$ or a guess for it. Does it work? $\endgroup$
    – alfC
    Commented Oct 28, 2017 at 18:50
  • $\begingroup$ Thanks for following, I'm not trying to normalize, I want a smooth maximum function instead of the hard maximum, I tested the Log(exp) function but it was hard to implement because of the overflow, I'm applying this smooth max in Neural network in order to compute the maximum and optimize the result. at the beginning it was not possible to start with high n parameter but after a few of optimizing the result i could the n. the only problem that I found in the function that n is proportional to the size of the input. $\endgroup$
    – Feras
    Commented Oct 29, 2017 at 11:29
5
$\begingroup$

You can smooth out any function by taking the convolution with a smooth bump function. As the support of the bump function shrinks to zero, the sequence of smoothed versions will converge to your original function.

Added: To be more specific, a Gaussian convolution with $|x|$ gives
$$|x|\approx x\ \mbox{erf}(x/\sqrt{2}\sigma)+\sqrt{2\over \pi}\sigma \exp(-x^2/2 \sigma^2)$$ as a smooth approximation to the absolute value function. If you prefer a function that vanishes at zero, take $$|x|\approx x\ \mbox{erf}(x/\sqrt{2}\sigma)+\sqrt{2\over \pi}\sigma \left[\exp(-x^2/2 \sigma^2)-1\right].$$ Here "erf" refers to the error function. Letting $\sigma$ approach zero gives better approximations.

For that matter, we could just use $$ |x|\approx x\ \mbox{erf}(x/\sigma).$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .