Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.