# Is there a bound on the norm of the product of second moment matrix with random vector?

Let $$X_1,\dots,X_n$$ be vectors in $$\mathbb{R^d}$$. Assume all of the vectors are inside the unite $$\ell_2$$ ball, but outside the ball of radius $$r$$ for some $$r \in (0,1)$$, i.e. $$r \leq \|X_i\| \leq 1$$ . Let $$P$$ be a vector in the probability simplex $$\Delta_n$$ with $$P_i>0$$ for all $$i$$. Consider the second moment matrix $$\Sigma(P) = \sum_{i=1}^n P_i X_i X_i^\top$$. Assume the $$X_i$$s are such that $$\Sigma(P)$$ is full rank. Does the following bound always hold? If not, when does it hold? $$\|\Sigma(P)^{-1}X_j\| \leq \frac{1}{r P_j} \quad \forall j\in \{1,\dots,n\}$$ For instance, if $$n=d$$ and $$X_i=e_i$$ are the canonical basis vectors of $$\mathbb{R}^d$$, then this bounds holds with equality.

$$\newcommand\Si{\Sigma}$$ $$\newcommand\X{\mathbf X}$$ The answer is no. Indeed, let $$p_i:=P_i$$, $$p:=P$$, $$\X:=(X_1,\dots,X_n)$$, and $$\Si_\X:=\Si(p)$$. At least one of the vectors $$\Si^{-1}X_j$$ is nonzero, for some $$j$$, because otherwise the matrix $$I=\Si_\X^{-1}\Si_\X=\sum_1^n p_i\Si_\X^{-1}X_i X_i^T$$ would be zero. So, there is some $$j$$ such that $$c:=\|\Si_\X^{-1}X_j\|>0$$. Replacing now $$\X$$ by $$a\X$$ for real $$a>0$$ and letting $$a\to0$$, we will have $$\|\Si_{a\X}^{-1}(aX_j)\|=\frac1a\,\|\Si_\X^{-1} X_j\|=\frac ca\to\infty,$$ so that the inequality $$\|\Si_{a\X}^{-1}(aX_j)\|\le\frac1{p_j}$$ will fail to hold for small enough $$a$$.
The OP has edited the question, thus invalidating this answer. However, even after the edit, the answer remains no. E.g., let $$n=2$$, $$p_1=p_2=1/2$$, $$X_1:=[1,1]^T/\sqrt2$$, and $$X_2:=[1,1-h]^T/\sqrt2$$ with $$h\downarrow0$$. Then $$\|X_1\|=1$$, $$1\ge\|X_2\|\sim1$$, but $$\|\Si_{\X}^{-1}(X_1)\|=\frac{2 \sqrt{2} \sqrt{h^2-2 h+2}}{h} \sim\frac4h \not\lesssim2=\frac1{p_1}.$$
• What if the $X_i$ are further restricted to be outside a ball of certain radius? So basically $r \leq\|X_i\|\leq 1$ for some fixed $r \in (0,1)$. Could such an inequality hold as a function of $r$, maybe something like $\frac{1}{r p_j}$ Feb 3, 2020 at 4:21