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

  • $\begingroup$ Of course you have $\|Ax\| \le \| A \| \|x\| = \sigma_{max}(A)\|x\|$, or am I misunderstanding the question? $\endgroup$ – Christian Remling Oct 1 '16 at 16:43
  • $\begingroup$ 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. $\endgroup$ – leo Oct 1 '16 at 17:51
  • $\begingroup$ $\sum_{i=1}^m A_i x_i \neq Ax$ here. $\endgroup$ – 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$).

  • $\begingroup$ Nice answer :-) $\endgroup$ – Fabian Wirth Oct 1 '16 at 19:24
  • $\begingroup$ @FabianWirth It seems we got the same idea... :) $\endgroup$ – Federico Poloni Oct 1 '16 at 19:29

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.