Expected norm $1$ of inner product

Question

Let $A$ denote a random vector with elements sampled i.i.d according to a distribution with mean $0$ and variance $\sigma^2$ and $x$ be a fixed vector. Can we calculate $E[||A^T x||_1 ]$ exactly or lower bound it somehow? I am specifically interested in a discrete distribution in the following form. $$ \begin{cases} 0, &w.p. &1-2p \\ 1, &w.p. &p \\ -1, &w.p. &p \end{cases} $$

Answer 1

Upper-bound. Let the shape of your random matrix $A$ be $n\times m$. First observe that $E[\|Ax\|_1] \le E[\sqrt{m}\|Ax\|_2] \le \left(mE\|Ax\|_2^2\right)^{1/2}$, where the second inequality is Jensen's inequality.

Now, let $\Sigma=\sigma^2 I_{m \times m}$ be the common covariance matrix of the rows of $A$ and $\mu = O_m$ be the mean. Then $$ E\|Ax\|_2^2 = \sum_{i=1}^nE|a_i^Tx|^2 = n(trace(xx^T\Sigma) + \mu^T\Sigma\mu) = n\sigma^2\|x\|^2_2. $$ Therefore, $$ E\|Ax\|_1 \le \sqrt{nm}\sigma\|x\|_2. $$

Edit: non-trivial lower-bound

Let $s \in \{-1,0,+1\}^m$ be the vector of the signs of the coordinates of $x$, and let $\|x\|_0 = \|s\|_0$ be the number of nonzero coordinates of $x$. Also, let $b = a_1 \in \mathbb R^m$ be the first row of the random matrix $A$. Then, one computes

$$ \begin{split} E|a_1^Tx| = E|\sum_j x_jb_j| &= \sum_{z \in \{-1,0,+1\}^m}\left|\sum_{j=1}^m x_jz_j\right|P(b_1=z_1,\ldots,b_m=z_m)\\ &= \sum_{z \in \{-1,0,+1\}^m}\left|\sum_{j=1}^m x_jz_j\right|\Pi_{j=1}^mP(Z_j=z_j)\\ &= \sum_{z \in \{-1,0,+1\}^m}\left|\sum_{j=1}^m x_jz_j\right|p^{\|z\|_0}(1-2p)^{m-\|z\|_0}\\ &=\sum_{z \in \{-1,0,+1\}^m}p^{\|z\|_0}(1-2p)^{m-\|z\|_0}\left|\sum_{j=1}^m x_jz_j\right|\\ & \ge 2p^{\|s\|_0}(1-2p)^{m-\|s\|_0}\left|\pm \sum_{j=1}^m x_js_j\right|\\ &= 2p^{\|x\|_0}(1-2p)^{m-\|x\|_0} \|x\|_1, \end{split} $$

where the inequality is because we have focused only on those $z \in \{-1,0,+1\}^m$ which have the same (or opposite) signs as $x$.

Therefore, we have the lower-bound $$ E\|Ax\|_1 \ge 2np^{\|x\|_0}(1-2p)^{m-\|x\|_0}\|x\|_1. $$

In fact, be restricted to those $z \in \{-1,0,+1\}$ whose coordinates have signs match those of $x$ or are simply zeroeth-out, we get the better bound

$$ E\|Ax\|_1 \ge 2n\sum_{I \subseteq supp(x)}p^{|I|}(1-2p)^{m-|I|}\|x_I\|_1 \ge 2np^{\|x\|_0}(1-2p)^{m-\|x\|_0}\|x\|_1, $$ where $supp(x) := \{j \in \{1,\ldots,m\} \mid x_j \ne 0\}$ is the support of $x$, and $x_I \in \mathbb R^{|I|}$ is the restriction of the vector $x$ onto the indices in the subset $I$.