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.


1 Answer 1


$\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}.$$

  • $\begingroup$ 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}$ $\endgroup$ Feb 3, 2020 at 4:21
  • $\begingroup$ @SudeepRaja : If you have additional questions, please ask them in separate posts. Edits should not invalidate an answer. $\endgroup$ Feb 3, 2020 at 5:03
  • $\begingroup$ Noted. I'm new to stack overflow. Didn't know the etiquette. $\endgroup$ Feb 3, 2020 at 5:06

You must log in to answer this question.

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