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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.