Shae's Ramblings

This post aims at gathering different inequalities pertaining to the product \(\mathrm{A}x\) where \(\mathrm{A}\) is a \(m\times n\) matrix, and \(v\in\mathbb{R}^n\) is a vector. We will decompose the matrix \(\mathrm{A}\) in terms of its column vectors \(a_j\) and its row vectors \(\tilde{a}_i^\mathsf{T}\):

$$ \mathrm{A} = \begin{bmatrix} a_1 & \dots & a_n \end{bmatrix} = \begin{bmatrix} \tilde{a}_1^\mathsf{T} \\ \vdots \\ \tilde{a}_m^\mathsf{T} \end{bmatrix} $$

Euclidean norm

The quantity $$\lVert\mathrm{A}x \rVert_2^2 = \sum_{i=1}^m \left(\tilde{a}_i^\mathsf{T}x\right)^2$$ can be decomposed using the cauchy-schwartz inequality to obtain

$$\lVert\mathrm{A}x \rVert_2^2 \leq \left(\sum_{i=1}^m \lVert\tilde{a}_i\rVert_2^2\right)\, \lVert x\rVert_2^2 = \lVert \mathrm{A} \rVert_{\mathrm{F}}^2 \, \lVert x\rVert_2^2 $$

thus there is a \(M = \lVert \mathrm{A} \rVert_{\mathrm{F}}\) such that \( \lVert\mathrm{A}x \rVert_2 \leq M\lVert x\rVert_2^2\).

This means all matrices are continuous & bounded linear maps for the \(l_2\) norm.

Manhattan norm

Suppose we wish to measure with input and output spaces using the \(l_1\) norm. The quantity $$\lVert\mathrm{A}x \rVert_1 = \sum_{i=1}^m \lvert\tilde{a}_i^\mathsf{T}x\rvert = \sum_{i=1}^m \lvert\sum_{j=1}^n a_{ij}x_j\rvert $$ can be upper-bounded using the finite-sum generalization of the scalar inequality \(\lvert a + b \rvert \leq \lvert a\rvert + \lvert b \rvert\). Denoting \(\lVert \mathrm{A} \rVert_1\) the sum of the unsigned entries \(\lvert a_{ij} \rvert\) we have the inequality:

$$ \lVert\mathrm{A}x \rVert_1 \leq \lVert\mathrm{A} \rVert_1 \lVert x \rVert_1$$

we can conclude similarly to the first section.

Infinity norm

Assume we now use the infinity norm \(\lVert \cdot \rVert_\infty\), we can upper bound the output \(\mathrm{A}x\) as follows:

\begin{align} \lVert \mathrm{A}x \rVert_\infty = \max_i\lvert \tilde{a}_i^\mathsf{T} x\rvert &= \max_i \left\lvert \sum_{j=1}^n a_{ij}x_j\right\rvert \\ & \leq \max_i \sum_{j=1}^n \left\lvert a_{ij} \right\rvert \left\lvert x_j\right\rvert \\ & \leq \lVert x\rVert_\infty \max_i \sum_{j=1}^n \left\lvert a_{ij} \right\rvert = M\,\lVert x\rVert_\infty \end{align}

we thus obtain that any linear operator is bounded and continuous for \(l_\infty\) in finite dimensions.

Duality

To be added.