Useful inequalities in estimation

Here I would like to collect a bunch of useful inequalities in estimation. This list is by no means complete, but I will keep adding new things when appropriate.

(1) Cauchy-Schwarz inequality: Let $(X,\langle\cdot,\cdot\rangle)$ be an inner product space, and $||x||=\sqrt{\langle x,x \rangle}$ (think of $L^2$ norm), then for all $x,y\in X$, $|\langle x,y \rangle| \leq ||x||\cdot||y||$.

This inequality has an obvious geometric interpretation for $\mathbb{R}^2$ (or $\mathbb{R}^3$) vector space, but let's prove it for the general case.

Proof: If $x=0$, the general inequality obviously holds.

If $x\neq 0$, let $\hat{x}\equiv \frac{x}{||x||}$, $y_{\parallel}\equiv \langle \hat{x},y \rangle \hat{x}$, $y_{\perp}\equiv y-y_{\parallel}$, then

$0\leq ||y_{\perp}||^2 = ||y-y_{\parallel}||^2 = ||y-\langle \hat{x},y \rangle\hat{x}||^2 = \langle  y-\langle \hat{x},y \rangle\hat{x}, y-\langle \hat{x},y \rangle\hat{x} \rangle = \langle  y-\langle \hat{x},y \rangle\hat{x}, y \rangle - \langle  y-\langle \hat{x},y \rangle\hat{x}, \langle \hat{x},y \rangle\hat{x} \rangle \\ = \langle  y, y \rangle - \langle  \langle \hat{x},y \rangle\hat{x}, y \rangle -  \langle  y, \langle \hat{x},y \rangle\hat{x} \rangle +  \langle  \langle \hat{x},y \rangle\hat{x}, \langle \hat{x},y \rangle\hat{x} \rangle = ||y||^2 -  \langle  \langle \hat{x},y \rangle\hat{x}, y \rangle - \overline{ \langle  \langle \hat{x},y \rangle\hat{x}, y\rangle } + ||\langle \hat{x},y \rangle\hat{x}||^2 \\ = ||y||^2 -  2Re \{ \langle  \langle \hat{x},y \rangle\hat{x}, y \rangle \} + ||\langle \hat{x},y \rangle\hat{x}||^2 = ||y||^2 - 2|\langle \hat{x},y \rangle|^2 + |\langle \hat{x},y \rangle|^2 = ||y||^2 - |\langle \hat{x},y \rangle|^2$

$\Rightarrow ||y||^2 \geq |\langle \hat{x},y \rangle|^2 = |\langle \frac{x}{||x||},y \rangle|^2 = \frac{1}{||x||^2} |\langle x,y \rangle|^2 \Rightarrow ||x||^2||y||^2 \geq  |\langle x,y \rangle|^2   \ \ \ \ \ \square$

Note: In the proof we considered a complex space. It can be simplified for a real space.

(2) Hölder's inequality: Let $(S,\Sigma,\mu)$ be a measure space and let $p,q \in [1,\infty]$ with $1/p+1/q=1$. Then for all measurable functions $f$ and $g$ on $S$, $||fg||_1 \leq ||f||_p||g||_q$.

Note: Clearly, for $p=q=2$, this implies the Cauchy-Schwarz inequality. So Hölder's inequality can be considered as a generalization of Cauchy-Schwarz.

To prove Hölder's inequality, we will need Young's inequality, which simply states that for $a,b>0$, we have $a\cdot b \leq \frac{a^p}{p}+\frac{b^q}{q}$, with $p,q$ defined the same way as in Hölder's inequality. Clearly for $p=q=2$, Young's inequality is valid by completing the square.

Proof of Young's inequality: consider $f: x \mapsto e^x$ which is a convex function, so we have for $\lambda \in [0,1]$, $f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda) f(y)$. Now consider $\lambda = 1/p$, $x=log(a^p)$, $y=log(b^q)$. Then $LHS=a\cdot b$ and $RHS = \frac{a^p}{p}+\frac{b^q}{q}$.      $\square$

Proof of Hölder's inequality: If $f=0$ or $g=0$, the inequality obviously holds. Otherwise, $\frac{1}{||f||_p||g||_q} ||fg||_1 = || \frac{|f|}{||f||_p}  \frac{|g|}{||g||_p}||_1 \leq || \frac{|f|^p}{p||f||_p^p} ||_1 + || \frac{|g|^p}{p||g||_p^p} ||_1 \leq \frac{1}{p} + \frac{1}{q} = 1$    $\square$

The Hölder's inequality can be generalized to multiple functions. For $i=1,..,n$, let $p_i \in [1,\infty]$ such that $\sum_{i=1}^n\frac{1}{p_i}=1$, then $||\Pi_{i=1}^n f_i ||_1 \leq \Pi_{i=1}^n ||f_i||_{p_i}$.

(3) Minkowski inequality: Let $(S,\Sigma,\mu)$ be a measure space, let $1\leq p <\infty$ and let $f$ and $g$ be elements of $L^p(S)$. Then $f+g$ is in $L^p(S)$ and we have $||f+g||_p \leq ||f||_p + ||g||_p$. 

Note: The Minkowski inequality is simply the triangle inequality for $L^p$ norm. 

Proof: We need to first prove that $f+g$ is indeed in $L^p(S)$. For $p=1$, this is clearly the case. For $p>1$, since $|x|^p$ is a convex function, we have $|\frac{1}{2}f + \frac{1}{2}g|^p \leq |\frac{1}{2}|f| + \frac{1}{2}|g| |^p \leq \frac{1}{2} |f|^p + \frac{1}{2} |g|^p \Rightarrow |f+g|^p \leq 2^{p-1} (|f|^p + |g|^p)$. So indeed $f+g$ has finite $L^p$ norm.

Now we can legitimately discuss $||f+g||_p$. 

$||f+g||_p^p=\int |f+g|^p d\mu=\int |f+g|^{p-1}|f+g| d\mu$

$\leq \int |f+g|^{p-1}(|f|+|g|) d\mu = \int |f+g|^{p-1}|f| d\mu+\int |f+g|^{p-1}|g| d\mu$

$\leq ((\int |f|^p d\mu)^{1/p} + (\int |g|^p d\mu)^{1/p}) (\int |f+g|^{(p-1)q} d\mu)^{1/q} $, with $1/q=1-1/p$ by Hölder's inequality

$=((\int |f|^p d\mu)^{1/p} + (\int |g|^p d\mu)^{1/p}) (\int |f+g|^p d\mu)^{1-1/p}$

$=(||f||_p+||g||_p) ||f+g||_p^{p-1}$

$\Rightarrow ||f+g||_p \leq ||f||_p+||g||_p$     $\square$

(4) Duality argument: In many cases, it is beneficial to consider the dual norm to expand the expression of a norm. Let $||\cdot||$ be a norm on $\mathbb{R}^n$. The associated dual norm, denoted $||\cdot||_*$ is defined as $||z||_*=sup\{z^Tx: ||x||<1 \}$. (think of this as an operator norm). The way to connect dual norm to a $l^p$ norm is to use the property that the dual of $l^p$ norm is the $l^q$ norm with $1/p+1/q=1$, i.e.,

$sup\{z^Tx: ||x||_p<1 \} =||z||_q$ 

Proof: $z^Tx = \sum_i z_ix_i \leq ||x||_p ||z||_q \leq ||z||_q$, by Hölder's inequality.    $\square$

(5) Young's convolution inequality: Let $p,q,r \in [1,\infty]$ satisfy $1+\frac{1}{r}=\frac{1}{p}+\frac{1}{q}$. Let $f\in L^p(\mathbb{R}^n)$ and $g\in L^q(\mathbb{R}^n)$. Then the convolution $f*g$ is in $L^r(\mathbb{R}^n)$ and we have $||f*g||_r \leq ||f||_p ||g||_q$.

Proof: We begin by seeking bound on $f*g(x)$.

$|f*g(x)| \leq \int |f(x-y)||g(y)| dy = \int (|f(x-y)|^p|g(y)|^q)^{1/r} |f(x-y)|^{(r-p)/r} |g(y)|^{(r-q)/r} dy$

$\leq || (|f(x-y)|^p|g(y)|^q)^{1/r} ||_r || |f(x-y)|^{(r-p)/r} ||_{\frac{pr}{r-p}} || |g(y)|^{(r-q)/r} ||_{\frac{qr}{r-q}}$    by generalized Hölder's inequality

$ = (\int |f(x-y)|^p|g(y)|^q dy)^{1/r}  ||f||_p^{(r-p)/r} ||g||_q^{(r-q)/r}$.

Then 

$||f*g||_r^r = \int |f*g(x)|^r dx \leq \int (\int |f(x-y)|^p|g(y)|^q dy)  ||f||_p^{r-p} ||g||_q^{r-q} dx$

$=||f||_p^{r-p} ||g||_q^{r-q} \iint |f(x-y)|^p|g(y)|^q dy dx $

$=||f||_p^{r-p} ||g||_q^{r-q} \int |g(y)|^q (\int |f(x-y)|^p dx) dy $  by Fubini's theorem 

$=||f||_p^r ||g||_q^r$    $\square$

(6) Sobolev space $H^s(\mathbb{R}^n)$ is an algebra if $s>n/2$, i.e., if $u$, $v$ are in $H^s(\mathbb{R}^n)$, then so is $uv$. Moreover, we have $||uv||_s \leq C ||u||_s ||v||_s$.

Proof: First note that, for $p>0$,

$(1+|\xi|^2)^p \leq (1+2|\xi-\eta|^2+2|\eta|^2)^p \leq 2^p(1+|\xi-\eta|^2+1+|\eta|^2)^p\leq c(1+|\xi-\eta|^2)^p+c(1+|\eta|^2)^p$, where the last inequality can be understood from $(a+b)^p=a^p(1+b/a)^p<2^p a^p$, say for $b<a$.

Let $\langle \xi \rangle=\sqrt{1+|\xi|^2}$, then

$\langle \xi \rangle^s |\widehat{uv}(\xi)| \leq \langle \xi \rangle^s \int |\hat{u}(\xi-\eta)\hat{v}(\eta)|d\eta \leq  c \int \langle \xi-\eta \rangle^s |\hat{u}(\xi-\eta)\hat{v}(\eta)|d\eta +  c \int \langle \eta \rangle^s |\hat{u}(\xi-\eta)\hat{v}(\eta)|d\eta$

                       $\leq c|\langle \cdot \rangle^s \hat{u}|*|\hat{v}|+c|\langle \cdot \rangle^s \hat{v}|*|\hat{u}|$

Using Young's convolution inequality, then we have 

$||uv||_{H^s} \leq c||u||_{H^s}||\hat{v}||_{L^1}+c||\hat{u}||_{L^1}||v||_{H^s}$

Since $s>n/2$, we have $||\hat{u}||_{L^1}=\int \langle \xi \rangle^{-s} \langle \xi \rangle^s |\hat{u}(\xi)| d\xi \leq ||\langle \xi \rangle^{-s}||_{L^2} ||\langle \xi \rangle^s \hat{u}||_{L^2} \leq C ||u||_{H^s}$, where we have used Cauchy-Schwarz for the first inequality and the fact that integral for $||\langle \xi \rangle^{-s}||_{L^2}$ converges for the second inequality.