spectral norm of block-wise sums of matrices

Question

Let $A = [A_1, \ldots, A_m] \in \mathbb{R}^{n \times md}$, where for all $i=1,\ldots,m$, $A_i \in \mathbb{R}^{n \times d}$, $d>1$. Let $x = [x_1,\ldots,x_m]^\top \in \mathbb{R}^m$ with $\|x\|_2 \leq \varepsilon$, then what is a tight upper bound of $\big\| \sum_{i=1}^m A_i x_i \big\|_2$, i.e., the spectral norm of a weighted sum of blocks matrices $A_i$ ($A_i$ is not a vector here), in terms of the largest singular value $\sigma_{\max}(A)$ of $A$ and $\varepsilon$?

A direct calculation gives $\big\| \sum_{i=1}^m A_i x_i \big\|_2 \leq \sum_{i=1}^m \|A_i\|_2 |x_i| \leq \sigma_{\max}(A) \|x\|_1 \leq \sqrt{m} \sigma_{\max}(A) \varepsilon$. But is it possible to get $$\big\| \sum_{i=1}^m A_i x_i \big\|_2 \leq \sigma_{\max}(A) \varepsilon$$

why or why not?

When $d=1$, it simply holds from the Cauchy-Schwarz inequality. When $m=1$, this also holds trivially. But what if $m>1$ and $d>1$?

Answer 1

If I understand correctly, $\sum A_i x_i = A (x \otimes I_d)$, so $$ \|\sum A_i x_i\| \leq \|A\|\, \|x\otimes I_d\| = \|A\|\, \|x\|, $$ where the last inequality holds because $\|M\otimes N\|=\|M\|\,\|N\|$ for all matrices $M$, $N$ (which itself holds because the singular values of $M\otimes N$ are obtained by multiplying those of $M$ and $N$).

Answer 2

OK, so we have $A_i \in \mathbb{R}^{n \times d}$, $i=1,\ldots,m$, and consider the matrix $A = [A_1, \ldots, A_m] \in \mathbb{R}^{n \times md}$. Let $x = [x_1,\ldots,x_m]^\top \in \mathbb{R}^m$. Using the Kronecker product we can write $$ \sum_{i=1}^m A_i x_i = A \ \left( \begin{bmatrix}x_1 \\ \vdots \\ x_m \end{bmatrix} \otimes I_d\right) .$$ Then, as the spectral norm is submultiplicative, we have $$ \sigma_{\max} \left( \sum_{i=1}^m A_i x_i \right) \leq \sigma_{\max} \left( A \right) \ \sigma_{\max} \left( \begin{bmatrix}x_1 \\ \vdots \\ x_m \end{bmatrix} \otimes I_d\right) = \sigma_{\max} \left( A \right) \| x \|_2.$$ In the last equality we have used the property that the singular values of a Kronecker product are the products of the singular values of the factors.

A good introduction to Kronecker products can be found in

Horn, Roger A.; Johnson, Charles R. (1991), Topics in Matrix Analysis, Cambridge University Press