Given $A \in \mathbb R^{m \times n}$, find upper bound for $\mathbb E\|Az\|_q$ for $z$ drawn uniformly at random on the sphere $\{\|z\|_p = 1\}$

32 Views Asked by At

Let $m$ and $n$ be positive integers and $p,q \in [1,\infty]$. Consider the finite-dimensiaonal normed vector spaces $X = (\mathbb R^m,\|\cdot\|_p)$ and $Y = (\mathbb R^n,\|\cdot\|_q)$, where

$$ \|x\|_p := \begin{cases}(\sum_{i=1}^m|x_i|^p)^{1/p},&\mbox{ if }1 \le p < \infty,&\\\max_{i=1}^m|x_i|,&\mbox{ else.}\end{cases} $$

Let $A:X \rightarrow Y$ be a linear operator, and $z$ be uniformly distributed on the unit sphere in $m$-sphere of $X$, and define $\Delta_{p,q}(A):= E[\|Az\|_q]$.

Question. What are good upper bounds for the quantity $\Delta_{p,q}(A)$ in terms of spectral properties of $A$ ($m$, $n$, singular values, etc.) ?

Note. I'm particularly interested in the cases where $p,q \in \{1,2,\infty\}$.

Solution for the euclidean case $p=q=2$

Suppose $p=q=2$. Then $z$ is uniform on the euclidean unit $m$-sphere, and so has mean $\mu = 0$ and covariance matrix $\Sigma = (1/m)I_m$. By Jensen's inequality and standard formula for expectation of quadratic forms, one computes

$$ \begin{split} \Delta_{2,2}(A)^2 &:= (E\|Az\|_2)^2 \le E\|Az\|_2^2 = \text{Trace}(A^TA\Sigma) + \|A\mu\|_2^2 = (1/m)\text{Trace}(A^TA)\\ & = (1/m)\|A\|_{\text{Fro}}^2, \end{split} $$

from which we get $\Delta_{2,2}(A) \le m^{-1/2}\|A\|_{\text{Fro}}$.


Edit: Solution for the case $p \in \{2,\infty\}$

By symmetry, $z$ has mean 0 and covariance

$$ \Sigma_p = \begin{cases}\frac{1}{m}I_m,&\mbox{ if }p = 2,\\\frac{1}{3}I_m + \mathcal O(m^2e^{-Cm}),&\mbox{ if }p=\infty.\end{cases} $$

Thus, one computes

$$ E\|Az\|_2^2 = \text{Trace}(A^TA\Sigma_p) = \begin{cases}\frac{1}{m}\text{Trace}(A^TA) = \|A\|_F^2,&\mbox{ if }p = 2,\\\frac{1}{3}\|A\|_F^2+ \mathcal O(m^2e^{-Cm}),&\mbox{ if }p=\infty.\end{cases} \tag{1} $$

On the other hand, we have by classical equaivalence bounds for norms on finite-dimensional spaces, one has

$$ \|Az\|_q \le \begin{cases}n^{1/q-1/2}\|Az\|_2,&\mbox{ if }1 \le q < 2,\\\|Az\|_2, &\mbox{ if }2 \le q \le \infty.\end{cases}. $$

Taking expectations on both sides and using (1), we then get

$$ \begin{split} \frac{\Delta_{p,q}(A)}{\|A\|_F} &\le \begin{cases}m^{-1/2}n^{1/q-1/2},&\mbox{ if }p=2,\;1 \le q < 2,\\m^{-1/2}, &\mbox{ if }p=2,\;2 \le q \le \infty,\\\dfrac{n^{1/q-1/2}}{3},&\mbox{ if }p=\infty,\; 1 \le q < 2,\\\frac{1}{3},&\mbox{ if }p=\infty,\; 2 \le p \le \infty.\end{cases}\\ \end{split} $$ which can be written more compactly as

$$ \frac{\Delta_{p,q}(A)}{\|A\|_F} \le \begin{cases}m^{-1/2}n^{(1/q-1/2)_+},&\mbox{ if }p=2,\\\dfrac{n^{(1/q-1/2)_+}}{3},&\mbox{ if }p=\infty.\end{cases} $$