1
$\begingroup$

Let $a,b$ be two vectors with strictly positive elements and $\delta = 1 - \frac{\langle a,b \rangle}{\|a\|\|b\|}$. Bound the following optimization problem as a function of $\delta$

$$\sup_{x>0} \frac{\langle a^2,x^2 \rangle}{\langle a,x \rangle^2} + \frac{\langle b^2,x^2 \rangle}{\langle b,x \rangle^2} - 2 \frac{\langle a \circ b,x^2 \rangle}{\langle a,x \rangle \langle b,x \rangle }$$

Here $a^2$ is the vector $a$ with all of its elements squared and $a\circ b$ is the element-wise product of $a$ and $b$.

If $\delta=0$, then the optimal value is 0. If $\delta \to 1$, then the optimal value is at most 2. Another way to express for the optimization problem is:

$$\sup_{x>0} \bigg\|\frac{a \circ x}{\langle a,x \rangle} - \frac{b \circ x}{\langle b,x \rangle} \bigg\|_2^2$$

Notice that $\frac{a \circ x}{\langle a,x \rangle}$ and $\frac{b \circ x}{\langle b,x \rangle}$ can be interpreted as two points on the probability simplex.

$\endgroup$
1
  • $\begingroup$ The first optimization problem is the same as the second one. Expanding the norm in the second problem gives the expression in the first. An exact explicit expression for the supremum would be great. An upper bound which respects the dependance on $\delta$ (ie, if $\delta = 0$ then optimal value is 0, if $\delta \to 1$ then optimal value is at most 2) is also fine. $\endgroup$ Commented Oct 8, 2023 at 21:30

1 Answer 1

1
$\begingroup$

It turns out that $\delta = 0$ is the only case with a bound better than 2. Let $a = (1,t), b = (1,\epsilon^2)$ and $x = (\epsilon,1)$ for some $t,\epsilon > 0$. Then $$\bigg\|\frac{a \circ x}{\langle a,x \rangle} - \frac{b \circ x}{\langle b,x \rangle} \bigg\|_2^2 = \left(\frac{1}{1+\epsilon}-\frac{\epsilon}{t+\epsilon}\right)^2+\left(\frac{t}{t+\epsilon}-\frac{\epsilon}{1+\epsilon}\right)^2 = 2-O(\epsilon).$$ Hence, by letting $\epsilon \to 0$ we get arbitrarily close to the upper bound of 2. By selecting appropriate $t$, we get any correlation $\frac{\langle a, b\rangle}{\|a\|\|b\|} \in (0,1)$. So there is no better bound in terms of the correlation $1-\delta$.

$\endgroup$

You must log in to answer this question.

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