# spectral norm of block-wise sums of matrices

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$?

• Of course you have $\|Ax\| \le \| A \| \|x\| = \sigma_{max}(A)\|x\|$, or am I misunderstanding the question? – Christian Remling Oct 1 '16 at 16:43
• not exactly, each $A_i$ is a matrix, not a column vector, so it is a weighted sum of blocks of matrices, instead of matrix vector multiplication. I suppose it should be true, but sure how to prove. – leo Oct 1 '16 at 17:51
• $\sum_{i=1}^m A_i x_i \neq Ax$ here. – leo Oct 1 '16 at 18:25

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$).
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.