0
$\begingroup$

Le $\lambda_1 \ge \lambda_2 \ge \ldots \ge \lambda_d$ be positive numbers. For any $x \in \mathbb R^d$ and $r \ge 0$, define $\gamma(x,r) := \sup_{z \in E(r)}x^\top z$, where $$ E(r) := E \cap B_2^d(r) = \{z \in \mathbb R^d \mid \sum_j z_j^2/\lambda_j \le 1,\, \|z\|_2 \le r\}, $$ the intersection of a hyper-ellipsoid $E := \{z \in \mathbb R^d \mid \sum_j z_j^2/\lambda_j \le 1\}$ and the Euclidean ball $B_2^d(r)$ of radius $r$. Note that for any $r \ne 0$, the mapping $x \mapsto \gamma(x,r)$ defines a norm on $\mathbb R^d$. Finally, from a statistical perspective, note that if $x \sim N(0,I_d)$, then $\mathbb E \gamma(x,r)$ is the Gaussian width of $E(r)$.

Also define $D(r) := \{x \in \mathbb R^d \mid \sum_{j=1}^d x_j^2/\lambda_j(r) \le 1\}$, where $\lambda_j(r) := \min(\lambda_j,r^2)$. Let $x \mapsto \omega(x,r)$ be the support function of $D(r)$.

Question. Are there absolute positive constants $c_1$ and $c_2$ such that $$ \gamma(x,r) \le c_2\omega(x,c_1 r), $$ for all $x \in \mathbb R^d$ and $r \ge 0$.

Note that the reverse inequality holds. Indeed, if $x \in D(r)$, then $\sum_{j=1}^d x_j^2/\min(\lambda_j,r^2) \le 1$ and so

  • $\sum_{j=1}^d x_j^2/\lambda_j \le 1$, i.e $x \in E$, and
  • $\sum_{j=1}^d x_j^2/r^2 \le 1$, i.e $x \in B_2^d(r)$,

i.e, $x \in E(r)$. Thus, $D(r) \subseteq E(r)$, and we conclude that $\gamma \ge \omega$.

Edit: Solution

We show that the claimed bound holds with $c_1=1$ and $c_2=\sqrt 2$. For this, it suffices to show that $E(r) \subset \sqrt{2} D(r)$. Indeed, let $x \in E(r)$. Then, $$ \begin{split} \sum_j x_j^2/\lambda_j(r) &= \sum_j x_j^2/\min(r^2,\lambda_j) = \sum_j x_j^2 \max(1/r^2,1/\lambda_j)\\ & \le \sum_j x_j^2 (1/r^2 + 1/\lambda_j) = \sum_j x_j^2/r^2 + \sum_j x_j^2/\lambda_j \le 1 + 1 = 2. \end{split} $$ Thus, $x \in \sqrt{2} D(r)$.

$\endgroup$
10
  • $\begingroup$ Sorry for the noise, but it turns our the problem is solved by an argument of Theorem 2.1 of this paper jmlr.org/papers/volume4/mendelson03a/mendelson03a.pdf. I'll close the question if nobody objects to it. $\endgroup$
    – dohmatob
    Commented Feb 5, 2023 at 16:51
  • $\begingroup$ (i) Your inequality cannot be true, as it is not homogeneous in $x$. There seem to be three mistakes in the definition of $\omega$. (ii) Theorem 2.1 in the paper linked in your comment seems rather different from whatever you wanted to ask here. In particular, it involves random variables, in contrast with your post. $\endgroup$ Commented Feb 5, 2023 at 17:03
  • $\begingroup$ I omitted a square root sign in the definition of $\omega$. Fixed. $\endgroup$
    – dohmatob
    Commented Feb 5, 2023 at 17:09
  • $\begingroup$ Concerning your, other comments, it is indeed shown in the reference that $D(r) \subseteq \mathcal E(r) \subseteq \sqrt{2} D(r)$, where $D(r) := \{x \in \mathbb R^d \mid \sum_j x_j^2/\lambda_j(r) \le 1\}$. There is no randomness involved here. The claim then follows upon comparing the support functions of these sets . No ? $\endgroup$
    – dohmatob
    Commented Feb 5, 2023 at 17:12
  • $\begingroup$ Two more mistakes remaining there (try replacing $\lambda_j$ and $r^2$ by $t^2\lambda_j$ and $t^2r^2$). $\endgroup$ Commented Feb 5, 2023 at 17:12

0

You must log in to answer this question.