Spectral norm of concatenation of two matrices.

Question

Let $A \in R^{n*p}$ and $B \in R^{n*d}$ such that both have spectral norm(largest singular value) equal to 1. Now if I concatenate the columns of $A$ and $B$ to construct $M=[A|B]$, then what can we say about the spectral norm of $M$. I am able to bound it by 2 but can we say something stronger(equal to or better upper bound)?

Answer 1

Note that $$ \pmatrix{A&B}\pmatrix{A&B}^T = AA^T + BB^T $$ Thus, we have $$ \|\pmatrix{A&B}\|^2 = \lambda_{max}(AA^T + BB^T) \leq \lambda_{max}(AA^T) + \lambda_{max}(BB^T) = \|A\|^2 + \|B\|^2 = 2 $$ Thus, we have $\|\pmatrix{A&B}\| \leq \sqrt{2}$, which is the best upper bound we can get.

---

Equivalently: $$ \| \pmatrix{A & B}\pmatrix{x_1\\x_2}\| = \|Ax_1 + Bx_2\| \leq \|A\|\|x_1\| + \|B\|\|x_2\| = \|x_1\| + \|x_2\| $$ thus, we want to maximize $\|x_1\| + \|x_2\|$ under the constraint that $\|(x_1,x_2)\| = 1$, which is to say that $\|x_1\|^2 + \|x_2\|^2 = 1$. This maximum is attained when $\|x_1\| = \|x_2\| = \sqrt{2}/2$.

Answer 2

$2$ is the optimum bound, since you can take $n=p=d=1$ and $A=B=1$. Then, in the $\infty$ norm, $\|M\|_\infty = 2$.