3
$\begingroup$

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

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

2 Answers 2

6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Nice answer :-) $\endgroup$ Oct 1, 2016 at 19:24
  • $\begingroup$ @FabianWirth It seems we got the same idea... :) $\endgroup$ Oct 1, 2016 at 19:29
4
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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