12
$\begingroup$

Suppose we have a function $f : \mathbb{R}^N \rightarrow \mathbb{R}$ which, given a vector, returns the value of its smallest element. How can I approximate $f$ with a differentiable function(s)?

$\endgroup$
  • $\begingroup$ The tag of the question is probably wrong. Sorry for that. $\endgroup$ – eakbas Aug 11 '10 at 5:45
  • $\begingroup$ Are these the real numbers $\mathbb{R}$? $\endgroup$ – Amir Sagiv Aug 11 '16 at 21:43
  • $\begingroup$ @AmirSagiv yes, they are. $\endgroup$ – eakbas Aug 12 '16 at 3:29
9
$\begingroup$

If signs aren't a big deal, use the generalized mean formula

$$ \left(\frac{1}{n}\sum x_i^k\right)^{1/k} $$

for $k\to -\infty$.

$\endgroup$
  • $\begingroup$ Nice, but you probably want to get rid of 1/n so that the result is as close to the smallest x_i as possible? $\endgroup$ – Neil Aug 11 '10 at 7:42
  • $\begingroup$ @Neil: The $1/n$ normalization is the standard one since it gives exactly what you want when all the $x_i$ are equal. But in fact if $n$ is fixed and $k$ approaches negative infinity, it doesn't matter asymptotically what constant you put inside the parentheses. $\endgroup$ – Tracy Hall Aug 11 '10 at 8:28
  • 4
    $\begingroup$ Since the function is piecewise linear, probably the most efficient smooth approximation is just by convolution with standard mollifiers $\epsilon^-n \rho(x/\epsilon)$, this simply 'rounds the corners' and leaves the function unchanged at most points. But the OP should really clarify what he needs. $\endgroup$ – Piero D'Ancona Aug 11 '10 at 11:10
  • $\begingroup$ is this function concave? $\endgroup$ – L.F. Cavenaghi Sep 2 '18 at 2:51
12
$\begingroup$

A smooth approximation is $f(x) = -\frac{1}{\rho}\log \sum_i e^{-\rho x_i} $. The larger $\rho>0$, the closer the approximation is to the minimum.

$\endgroup$
  • $\begingroup$ To get the proper normalization I think you actually want to replace sum_i with (1/n)sum_i, similar to Aaron Bergman's answer. I just tried it with sum vs mean inside the logarithm, and mean gave me much closer to the minimum, quantitatively. $\endgroup$ – Kevin Holt Feb 1 '17 at 18:36
  • $\begingroup$ I'm not sure. If there are many values $x_i$ which are large, their exponentials will be small, and the mean will increase beyond the minimum. I think the discussion in the other answer is similar. $\endgroup$ – Pait Feb 2 '17 at 17:52
  • $\begingroup$ Yes, but if there are many values $x_i$ that are close to the minimum, then the unnormalized version gives $f(x) < \min(x)$ which really has no useful interpretation, whereas in the normalized version when the mean increases beyond the minimum that can be interpreted as a compromise between the true minimum and the other values that are above the minimum. $\endgroup$ – Kevin Holt Feb 13 '17 at 21:09
  • $\begingroup$ I added this as a separate answer with a more in-depth argument. $\endgroup$ – Kevin Holt Feb 13 '17 at 21:10
  • $\begingroup$ The expression without the $1/n$ factor is always larger than the minimum. This is a problem if there are many points near the minimum - the approximation becomes too conservative. On the other hand the expression with the $1/n$ factor will become smaller than the minimum if there are many points larger than the minimum, which may make it less desirable. $\endgroup$ – Pait Feb 14 '17 at 22:50
4
$\begingroup$

For two dimensions, we have $\min(x,y) = \tfrac{1}{2}(x+y-|x-y|)$, so you just need a differentiable approximation to $x \mapsto |x|$. Then for higher dimensions we have $\min(x,y,z) = \min(x, \min(y,z))$, etc.

$\endgroup$
  • $\begingroup$ and is there a good analytical approximation to $|x|$? $\endgroup$ – Amir Sagiv Aug 12 '16 at 12:15
  • 3
    $\begingroup$ Bernstein, S. N. "Sur la meilleure approximation de |x| par les polynomes de degrés donnés." Acta Math. 37, 1-57, 1913. $\endgroup$ – Margaret Friedland Aug 12 '16 at 14:39
  • 1
    $\begingroup$ For instance $\sqrt{\epsilon +x^2}$ $\endgroup$ – Pietro Majer Feb 13 '17 at 21:08
3
$\begingroup$

I would use $$f(x) = -\frac{1}{\rho}\log \frac{1}{N} \sum_{i=1}^N e^{-\rho x_i},$$ which approaches $f(x) \rightarrow \min_i |x_i|$ as $\rho \rightarrow +\infty$.

There has been some debate about normalization, so let's compare these four: $$f_{A}(x) = -\frac{1}{\rho}\log \frac{1}{N}\sum_{i=1}^N e^{-\rho x_i} $$ $$f_{B}(x) = -\frac{1}{\rho}\log \sum_{i=1}^N e^{-\rho x_i} $$ $$f_C(x) = \left(\frac{1}{N}\sum x_i^{-\rho}\right)^{-1/\rho}$$ $$f_D(x) = \left(\sum x_i^{-\rho}\right)^{-1/\rho}$$

For $x$=[1,2,3,4,5] and $\rho=10$, $f_A=1.16$, $f_B=1.0$, $f_C=1.1745$, $f_D=1.0$.

For $x$=[1,2,3,4,5] and $\rho=100$, $f_A=1.016$, $f_B=1.0$, $f_C=1.0162$, $f_D=1.0$.

For $x$=[1,1,1,1,1] and $\rho=10$, $f_A=1$, $f_B=0.8391$, $f_C=1$, $f_D=0.8513$.

For $x$=[1,1,1,1,1] and $\rho=100$, $f_A=1$, $f_B=0.9839$, $f_C=1$, $f_D=0.9840$.

For $x$=[0,1,10,100,1000] and $\rho=10$, $f_A=0.1609$, $f_B=0$, $f_C=0$, $f_D=0$.

For $x$=[0,1,10,100,1000] and $\rho=100$, $f_A=0.0161$, $f_B=0$, $f_C=0$, $f_D=0$.

(For the last two cases, $f_C$ and $f_D$ can be evaluated by using $\log(0)=\infty$ and $\infty^{-1/\rho}=0$).

So as we would hope, when $\rho$ is large, all versions give reasonably good approximations to the minimum.

The question then is which is best when $\rho$ is not that big -- this is an important question since large $\rho$ can give practical difficulties with finite precision arithmetic. Comparing the four versions above, we can see that the mean versions (A and C) overestimate the minimum when $x$ has a lot of values above the minimum. Conversely, the sum versions (B and D) underestimate the minimum when $x$ has a lot of values that are all equal to the minimum. Which is better is ultimately a question of your application. But to me, the mean version gives an answer that makes much more sense. The approximate minimum should be similar to the minimum but the approximation should get pulled in the direction of all of the individual values in $x$. This is what happens in the mean version (A and C), which also keep the approximate minimum inside the range of the data, i.e. $$\min(x) \le f_A(x) , f_C(x) \le \max(x)$$ On the other hand, the sum versions (B and D) can give a minimum value that is actually lower than any value contained in the data (see the third and fourth examples above). In other words, it is possible that $$f_B(x), f_D(x) < \min(x),$$ which is a property I want to avoid in an approximate minimum since it makes it very hard to interpret that approximate-minimum value. So I find A,C to be more useful than B,D.

The last question is A vs C. Version A is fairly stable as $x_i \rightarrow 0$, but version C however runs out of precision. For example $x^{-100}$ overflows double precision below $x \approx 8.27e^{-4}$ and overflows single precision below $x \approx 0.412$.

Therefore, at least in my own uses, $f_A$ gives the most useful approximation and is the most numerically stable.

$\endgroup$
  • $\begingroup$ I think $-{1\over N\rho} \log\big( \sum_{i=1}^N...$ is a typo for $-{1\over \rho }\log\big({1\over N } \sum_{i=1}^N...$ $\endgroup$ – Pietro Majer Feb 13 '17 at 22:05
  • $\begingroup$ So... am I getting downvoted for a typo, or is there something else wrong with what I wrote? $\endgroup$ – Kevin Holt Feb 15 '17 at 16:54
1
$\begingroup$

What about $f: [x_1 \dots\ x_n] \mapsto \frac{1}{\sum_i x_i^{-1}}$?

$\endgroup$
  • $\begingroup$ I see a small problem if any of the $x_i$ is nonpositive. $\endgroup$ – Pait Jun 27 '13 at 22:07
  • $\begingroup$ @pait: +1, you may want to add this comment to the accepted answer as well? $\endgroup$ – Neil Jun 28 '13 at 1:33
  • $\begingroup$ Well the accepted answer states that it's only applicable to absolute values, and 0 is not a problem in the formula with squares. It seems that to achieve smoothness it is more practical to work with exponentials. $\endgroup$ – Pait Jun 28 '13 at 12:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.