Spectral norm of a difference matrix

104 Views Asked by At

Let $M,N\in\mathbb{N}\setminus\{1\}$ and suppose that $x\in\mathbb{R}^{M N}$. Denote $x$ by \begin{align} x = \begin{bmatrix} x_{1} \\ \vdots \\ x_{N} \\ \end{bmatrix} \end{align} where $x_{i}\in\mathbb{R}^M$ for each $i$. Define a matrix $L\in\mathbb{R}^{M(N-1)+(M-1)N \times MN}$ such that \begin{align} Lx = \begin{bmatrix} x_{1}-x_{2} \\ \vdots \\ x_{N-1} - x_{N} \\ A x_1 \\ \vdots \\ A x_N \\ \end{bmatrix} \end{align} where $A\in\mathbb{R}^{M-1\times M}$ is \begin{align} A = \begin{bmatrix} 1 & -1 & 0 & \cdots & 0 & 0 & 0 \\ 0 & 1 & -1 & \cdots & 0 & 0 & 0 \\ 0 & 0 & 1 & \cdots & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & -1 & 0 \\ 0 & 0 & 0 & \cdots & 0 & 1 & -1 \end{bmatrix} \end{align} What is the spectral norm $||L||_{2}$, or alternatively, find an upper bound better than the Frobenius norm $||L||_{F}$.