I have tuples of numbers $(x_{i,a})_{1\leq a \leq M, 1\leq i \leq n}, (x_{i})_{1\leq i \leq n}\subseteq [0,1]$ satisfying the following, for some fixed parameter $\beta \in (0,1)$: $$ \begin{align} \sum_{i=1}^n x_{i} &= 1 & \\ \sum_{a=1}^M x_{i,a} &= x_i, &\forall i \in \{1,\dots,n\} \\ \sum_{i=1}^n x_{i,a} &= \beta, &\forall a \in \{1,\dots,M\} \\ \end{align} $$ so in particular $0 \leq x_{i,a} \leq \min(\beta, x_i)$ for all $i,a$.

I am trying to obtain the best possible bound on the expression $$ \sum_{1\leq a,b\leq M} \left(\sum_{i=1}^n x_{i,a}x_{i,b}\right)^2 $$ in terms of $\beta$ and norms of the vector $x=(x_1,\dots, x_n)$. For instance, I can write $$ \begin{align} \sum_{1\leq a,b\leq M} \left(\sum_{i=1}^n x_{i,a}x_{i,b}\right)\left(\sum_{j=1}^n x_{j,a}x_{j,b}\right) &\leq \sum_{1\leq a,b\leq M} \left(\sum_{i=1}^n x_{i,a}x_{i,b}\right)\left(\max_{j}x_{j,b}\sum_{j=1}^n x_{j,a}\right) \\ &\leq \sum_{1\leq a,b\leq M} \left(\sum_{i=1}^n x_{i,a}x_{i,b}\right)\left(\max_{j}x_{j}\cdot \beta\right)\\ &=\beta\lVert x\rVert_\infty \sum_{1\leq a,b\leq M} \left(\sum_{i=1}^n x_{i,a}x_{i,b}\right) \\ &=\beta\lVert x\rVert_\infty \sum_{i=1}^n\left(\sum_{a=1}^M x_{i,a}\right)^2 =\beta\lVert x\rVert_\infty \sum_{i=1}^nx_i^2 \end{align} $$ obtaining the upper bound $\beta\lVert x\rVert_\infty \lVert x\rVert_2^2$. But this is not good enough for my purposes (the factor $\lVert x\rVert_\infty$ is too big, ideally I'd like it either squared or getting only powers of $\lVert x\rVert_2$).

The above is tantamount to using Holder's inequality (for $(1,\infty)$), but I do lose a lot on the assumptions when goind to $\max_{j} x_{j,b}$ and then $\max_{j} x_{j}$. Is there a tighter way to do it? Or an alternative way to "massage" the terms?

  • $\begingroup$ Yes, it it true - this is a fixed constant of the problem, but I didn't write it down... should have. $\endgroup$
    – Clement C.
    Feb 22, 2016 at 17:12
  • $\begingroup$ (Answering a comment that pointed out that $\beta=1/M$.) $\endgroup$
    – Clement C.
    Feb 22, 2016 at 17:35
  • $\begingroup$ I'm also curious as to why are you considering $<x_a,x_b>^2$. Is there a natural interpretation for this quantity? $\endgroup$
    – A.S.
    Feb 22, 2016 at 20:57
  • $\begingroup$ @A.S. Oh, it comes from a variance analysis for an algorithm in some natural-but-not-that-much setting... not sure how clear that is, but the square comes from $\operatorname{var} aX = a^2 \operatorname{var} X$ with $a=\sum_{i} x_{i,a}x_{i,b}$. $\endgroup$
    – Clement C.
    Feb 22, 2016 at 21:00

1 Answer 1


Some partial progress:

Instead of using Hölder's inequality for $(1,\infty)$, one can apply it for $(2,2)$ (i.e., Cauchy—Schwarz) to get a different bound: $$ \sum_{i=1}^n x_{i,a}x_{i,b} \leq \sqrt{\sum_{i=1}^n x_{i,a}^2}\sqrt{\sum_{i=1}^n x_{i,b}^2} \leq \sqrt{\sum_{i=1}^n x_{i}^2}\sqrt{\sum_{i=1}^n x_{i}^2} = \lVert x\rVert_2^2 $$ which relied on $x_{i,a}, x_{i,b} \leq x_i$. Doing so, we get a bound of $$ \sum_{a,b} \left(\sum_{i=1}^n x_{i,a}x_{i,b}\right)^2 \leq \lVert x\rVert_2^2 \sum_{a,b} \left(\sum_{i=1}^n x_{i,a}x_{i,b}\right) = \lVert x\rVert_2^4 $$ to be compared with the previous $\beta \lVert x\rVert_\infty\lVert x\rVert_2^2$.

While the bound is better in some regimes, it can be strictly worst; the very bad case being $x_i = \frac{1}{n}$ for all $i\in[n]$, where $\beta\lVert x\rVert_\infty = \frac{\beta}{n}$, yet $\lVert x\rVert_2^2 = \frac{1}{n}$.


You must log in to answer this question.

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