MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose there is a jointly convex function $f:\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R}$, $\mathbf{x},\mathbf{y}\in\mathbb{R}^m$ and $\mathbf{p}=[p_1\;\ldots\;p_m]^\top,\mathbf{q}=[q_1\;\ldots\;q_m]^\top$ satisfying $\|p\|^2=\sum_ip_i^2=\|q\|^2=\sum_jq_j^2=1$, I want to find the bound of $f\left({\mathbf{p}^2}^\top\mathbf{x},{\mathbf{q}^2}^\top\mathbf{y}\right)$ by decomposing it into weighted sum of $f(x_i,y_j)$ if $\mathbf{p},\mathbf{q}$ are constrained in a manifold.

The case without constraints of $\mathbf{p}$ and $\mathbf{q}$

Denote the element-wise squared vector of $\mathbf{p},\mathbf{q}$ as $$\mathbf{p}^2=[p_1^2\;\ldots\;p_m^2]^\top,\mathbf{q}^2=[q_1^2\;\ldots\;q_m^2]^\top,$$ then by Jensen's inequality for jointly convex function, we have \begin{eqnarray} f\left({\mathbf{p}^2}^\top\mathbf{x},{\mathbf{q}^2}^\top\mathbf{y}\right) &=&f\left(\sum_ip_i^2x_i,\sum_jq_j^2y_j\right)\\\ &=&f\left(\sum_i\left(p_i^2\sum_jq_j^2x_i\right),\sum_j\left(q_j^2\sum_ip_i^2y_j\right)\right)\\\ &=&f\left(\sum_i\sum_jp_i^2q_j^2x_i,\sum_i\sum_jp_i^2q_j^2y_j\right)\\\ &\leq&\sum_i\sum_j{p_i^2q_j^2f\(x_i,y_j)}\\\ &=&{\mathbf{p}^2}^\top F\mathbf{q}^2 \end{eqnarray} where $F_{ij}=f(x_i,y_j)$. This provides a general bound for $f\left({\mathbf{p}^2}^\top\mathbf{x},{\mathbf{q}^2}^\top\mathbf{y}\right)$.

Suppose $C=[c_{ij}]\_{m\times m}$ is an orthogonal matrix and the element squared matrix of $C$ is $$C^2=[c_{ij}^2]\_{m\times m},$$ then $C^2$ is a doubly stochastic matrix where $C^2\mathbf{1}=\mathbf{1}$and ${C^2}^\top\mathbf{1}=\mathbf{1}$.

The case if with constraint ${\mathbf{q}^2}={C^2}^\top\mathbf{p}^2$

If an additional constraint $\mathbf{q}^2={C^2}^\top\mathbf{p}^2$ is applied so that $\mathbf{p}$ and $\mathbf{q}$ are constrained on a manifold, we can substitute the constraint into the inequality above, we get the bound \begin{eqnarray} f\left({\mathbf{p}^2}^\top\mathbf{x},{\mathbf{q}^2}^\top\mathbf{y}\right) \leq{\mathbf{p}^2}^\top F{C^2}^\top\mathbf{p}^2 \end{eqnarray}

On the other hand, applying Jensen's inequality directly on the original formular, we can obtain another bound as \begin{eqnarray} f\left({\mathbf{p}^2}^\top\mathbf{x},{\mathbf{q}^2}^\top\mathbf{y}\right) &=&f\left(\sum_ip_i^2x_i,\sum_j\sum_ic_{ij}^2p_i^2y_j\right)\\\ &=&f\left(\sum_ip_i^2x_i,\sum_i\left(p_i^2\sum_jc_{ij}^2y_j\right)\right)\\\ &\leq&\sum_ip_i^2f\left(x_i,\sum_jc_{ij}^2y_j\right)\\\ &\leq&\sum_i\sum_j{p_i^2c_{ij}^2f(x_i,y_j)}\\\ &=&{\mathbf{p}^2}^\top(F\circ C^2)\mathbf{1} \end{eqnarray} where $\circ$ is the Hadamard (element-wise) product.

It is notable that this bound is simpler than the one obtained by substitution and has $\mathbf{p}$ is homogeneous in both sides of the inequality.

What is the case if with constraint $\mathbf{q}=C^\top\mathbf{p}$?

My question is that if the constraint is replaced with $\mathbf{q}=C^\top\mathbf{p}$, could we obtain the bound of $f\left({\mathbf{p}^2}^\top\mathbf{x},{\mathbf{q}^2}^\top\mathbf{y}\right)$ with Jensen's equality? If such a bound exists, could it have the simple form where $\mathbf{p}$ similar to ${\mathbf{p}^2}^\top(F\circ C^2)\mathbf{1}$?

Could anyone be so kind to give me some help on this problem? Any suggestion will be appreciated! Thank you very much!

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.