User anton sukhinov - MathOverflow

Convexified threshold of a function

2012-07-07T15:53:10Z

Upd. The question in a nutshell: find convex set on plane which is «closest» to a given non-convex set.

It is given integrable function $0\leq f(x,y)\leq 1$ with bounded support: $f(x,y)=0$ when $x^2+y^2\geq R$. Needed to find function $t(x,y)$ which takes only two values («binary» function): $t(x,y)\in\{0,1\}$ such as $$\iint\limits_{x^2+y^2<R}\left|f(x,y)-t(x,y)\right|dxdy\to\min.$$ We will call this task «threshold of a function». The solution is trivial: $$t(x,y)=\left\{\begin{array}{cl}0&\text{if }f(x,y)<1/2;\\1&\text{if }f(x,y)\geq1/2.\end{array}\right.$$ But what to do if I need to find threshold having convex support? I.e. I need to find a function $c(x,y)\in\{0,1\}$ that have convex support and satisfies minimization criteria stated above among all binary functions with convex support. I can use any norm which will be convenient.

I also interested in discrete analog of the problem: given set of points $p_i=\{x_i,y_i\}\in\mathbb{R}^2$ , $i=1,...,N$, and values $0\leq v(p_i)\leq 1$. Find convex polygon $P$, such as $$\sum_{p_i\in P}(1-v(p_i))+\sum_{p_i\notin P}v(p_i)\to\min.$$ I tried greedy algorithm to solve last problem: take convex hull of all points which have value $>1/2$ and then reduce convex hull point-by-point while target function decreases, but this fails for structures where 0-valued points are surrounded by 1-valued points.

Information amount of fuzzy data transfer

2012-06-22T19:01:45Z

Suppose we have binary channel from which we are able to receive zeroes and ones. We also know apriory probability $p$ of receiving "1". Then we can calculate information amount of each digit $q$ we receive:

q=0: $I=-\log_2(1-p)$ bits;

q=1: $I=-\log_2(p)$ bits.

Now imagine that the channel is "fussy": instead of receiving exact digits we receiving probability $q$ that transferred digit is "1". Previous example of "unfussy" channel is when $q$ can take only two values: $q\in\{0,1\}$ .

What will be the amount of information of receiving probability $q$ given probability $p$?

Thanks!

Scale random variables in a way they have equal probabilities of being minimal

2012-02-23T17:03:58Z

I have several positive random variables $x_i,\ i=1,...,N$ taken from different unknown distributions (these distributions can be closely approximated by log-normal if needed). I can sample these variables as many times as needed; all variables are sampled simultaneously.

From each sample my software selects the minimal variable $x_j$ and outputs its index $j$.

The problem is: all values of output index $1 \leq j \leq N$ should have equal probabalities. So, random variables should be somehow adjusted to be "equal" for the minumum operation.

I decided to multiply each random variable by some constant $k_i$. First idea was that $k_i=1/E[x_i]$, so that all adjusted variables will have equal expected values. The output indices indeed became much more uniform, but I pretty sure that my solution is wrong.

The software should also dynamically adapt to gradually changing distributions of random variables (noise shape of sensors depend on temperature).

Do you have any advice?

Comment by Anton Sukhinov

2012-06-23T18:41:54Z

I have not found this question in the FAQ

Comment by Anton Sukhinov

2012-02-25T06:15:41Z

That completely solves my problem. Thank you!