I have two vectors X and Y with a known dot product between them.
$\sum_{i=0}^n X_i Y_i = R $
I’d like to bound:
$\sum_{i=0}^n |X_i - Y_i| $
More generally I’d like to use the information on the dot product to gain insights into how individual elements in the vectors X and Y differ. I think the simplest way to do that is to bound the expression above: the sum across all elements of the difference between the elements.
Simplifying assumptions
For simplicity let’s assume that each vector has a mean of zero and 2-norm of 1. $\sum_{i=0}^n X_i =0; \sum_{i=0}^n Y_i = 0$
$ \| X \|_2^2 =\sum_{i=0}^n X^2_i =1; \| Y \|_2^2 = \sum_{i=0}^n Y^2_i =1$
Also for simplicity assume the elements of the vectors are reals bounded between -1 and 1. $X_i, Y_i \in [-1,1]$
What I've tried
Let D = X – Y. Then what I’m looking for is the 1-norm of D:
$ \| D \|_1 = \sum_{i=0}^n |X_i - Y_i| $
I can bound the 1-norm using the well known inequality involving the 2-norm:
$\| D \|_2 <= \| D \|_1 <= \sqrt{n} \| D \|_2 $
We can calculate the 2-norm of D: $\| D \|_2^2 =\sum_{i=0}^n (X_i - Y_i)^2 =\sum_{i=0}^n X_i^2 + Y_i^2 – 2 X_i Y_i = 2 -2 R$
Therefore we can bound the 1-norm as:
$\sqrt{2 -2 R} <= \| D \|_1 <= \sqrt{n(2 – 2 R)} $
Specific Questions
(1) Can I get a tighter bound on $\| D \|_1$ the one above? I haven't used $X_i, Y_i \in [-1,1]$.
(2) I considered using expressions besides $ \| D \|_1 $, for example: $\sum_{i=0}^n |\frac{X_i - Y_i}{X_i}| $
However I couldn't simplify this. My suspicion is that I need to use the dot product R in my simplification to get useful bounds.
Is there a way to bound $ \sum_{i=0}^n |\frac{X_i - Y_i}{X_i}| $ using R?
(3) Is there another interesting way, other than $ \| D \|_1 $, to get general insights into how individual elements in the vectors X and Y differ? (I realize ‘interesting’ is in the eye of the beholder, so I’d be willing to hear any potentially insightful approaches)
Suppose $X$, $Y$ are any two real vectors with scalar product $R$, without any assumption. The best bound you can find is akin to what you found, namely $$ \sqrt{\|X\|_2^2 +\|Y\|_2^2 - 2R}\le \|X-Y\|_1\le \sqrt{n(\|X\|_2^2 +\|Y\|_2^2 - 2R)} $$ It is sharp (for one side, take $Y=RX=(1,0,\dots,0)$, and for the other $Y=\frac RnX=\frac Rn(1,1,\dots,1)$). Notice that if $n=1$, the two bounds coincide.
If we suppose that $X,Y$ have the same 2-norm equal to 1 (and notice that in this case $X_i,Y_i\in [-1,1]$ always holds) , then the bounds are still sharp for $n>1$. If $n=1$, the conditions lead to $R=\pm 1$ and there are just two cases
If we add the condition of zero mean for both $X,Y$, then for $n=1$ you have no solutions, for $n=2$ you have just two cases $R=\pm 1$. For $n>2$ it gets tricky, since there is a better lower bound: $$2\sqrt{1-R}=\sqrt 2\sqrt{\|X\|_2^2 +\|Y\|_2^2 - 2R}\le \|X-Y\|_1$$
for even $n$, the upper bound given is already optimal. The upper bound can be improved only when $n$ is odd. In fact, in this case, we have $$ \|X-Y\|_1\le \sqrt{(n-\frac 1n)(\|X\|_2^2 +\|Y\|_2^2 - 2R)} = \sqrt{n-\frac 1n}\sqrt{2-2R} $$ All these bounds are sharp.