Next  |  Prev  |  Up  |  Top  |  Index  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

Specific Norms

The $ Lp$ norms are defined on the space $ Lp$ by

$\displaystyle \left\Vert\,F\,\right\Vert _p \mathrel{\stackrel{\mathrm{\Delta}}...
... F(e^{j\omega})\right\vert^p {d\omega\over 2\pi} \right)^{1/p}, \quad p\geq 1 .$ (1)

$ Lp$ norms are technically pseudo-norms; if functions in $ Lp$ are replaced by equivalence classes containing all functions equal almost everywhere, then a norm is obtained.

Since all practical desired frequency responses arising in digital filter design problems are bounded on the unit circle, it follows that $ \{H(e^{j\omega})\}$ forms a Banach space under any $ Lp$ norm.

The weighted $ Lp$ norms are defined by

$\displaystyle \left\Vert\,F\,\right\Vert _p \mathrel{\stackrel{\mathrm{\Delta}}...
...vert^p W(e^{j\omega}){d\omega\over 2\pi} \right)^ \frac{1}{ p}, \quad p\geq 1 ,$ (2)

where $ W(e^{j\omega})$ is real, positive, and integrable. Typically, $ \int W = 1$. If $ W(e^{j\omega})=0$ for a set of nonzero measure, then a pseudo-norm results.

The case $ p=2$ gives the popular root mean square norm, and $ \vert\vert\,\cdot\,\vert\vert _2^2$ can be interpreted as the total energy of $ F$ in many physical contexts.

An advantage of working in $ L2$ is that the norm is provided by an inner product,

$\displaystyle \left<H,G\right>\mathrel{\stackrel{\mathrm{\Delta}}{=}}\int_{-\pi}^\pi H(e^{j\omega})\overline{G(e^{j\omega})}{d\omega\over 2\pi}.

The norm of a vector $ H\in L2$ is then given by

$\displaystyle \left\Vert\,H\,\right\Vert\mathrel{\stackrel{\mathrm{\Delta}}{=}}\sqrt{\left<H,H\right>}.

As $ p$ approaches infinity in Eq. (1), the error measure is dominated by the largest values of $ \vert F(e^{j\omega})\vert$. Accordingly, it is customary to define

$\displaystyle \left\Vert\,F\,\right\Vert _\infty \mathrel{\stackrel{\mathrm{\Delta}}{=}}\max_{-\pi < \omega \leq \pi} \left\vert F(e^{j\omega})\right\vert ,$ (3)

and this is often called the Chebyshev or uniform norm.

Suppose the $ L^1$ norm of $ F(e^{j\omega})$ is finite, and let

$\displaystyle f(n) \mathrel{\stackrel{\mathrm{\Delta}}{=}}\frac{1}{ 2\pi} \int_{-\pi}^\pi F(e^{j\omega}) e^{j\omega n} {d\omega\over 2\pi}

denote the Fourier coefficients of $ F(e^{j\omega})$. When $ F(e^{j\omega})$ is a filter frequency response, $ f(n)$ is the corresponding impulse response. The filter $ F$ is said to be causal if $ f(n)=0$ for $ n<0$.

The norms for impulse response sequences $ \vert\vert\,f\,\vert\vert _p$ are defined in a manner exactly analogous with the frequency response norms $ \vert\vert\,F\,\vert\vert _p$, viz.,

$\displaystyle \left\Vert\,f\,\right\Vert _p \mathrel{\stackrel{\mathrm{\Delta}}...
...eft(\sum_{n=-\infty}^\infty \left\vert f(n)\right\vert^p\right)^ \frac{1}{ p}.

These time-domain norms are called $ lp$ norms.

The $ Lp$ and $ lp$ norms are strictly concave functionals for $ 1<p<\infty$ (see below).

By Parseval's theorem, we have $ \vert\vert\,F\,\vert\vert _2= \vert\vert\,f\,\vert\vert _2$, i.e., the $ Lp$ and $ lp$ norms are the same for $ p=2$.

The Frobenious norm of an $ m\times n$ matrix $ A$ is defined as

$\displaystyle \left\Vert\,A\,\right\Vert _F \mathrel{\stackrel{\mathrm{\Delta}}{=}}\sqrt{\sum_{i=1}^m\sum_{j=1}^n \left\vert a_{ij}\right\vert^2}.

That is, the Frobenious norm is the $ L2$ norm applied to the elements of the matrix. For this norm there exists the following.

Theorem. The unique $ m\times n$ rank $ k$ matrix $ B$ which minimizes $ \vert\vert\,A-B\,\vert\vert _F$ is given by $ U\Sigma_k V^\ast$, where $ A=U\Sigma V^\ast$ is a singular value decomposition of $ A$, and $ \Sigma_k$ is formed from $ \Sigma$ by setting to zero all but the $ k$ largest singular values.

Proof. See Golub and Kahan [3].

The induced norm of a matrix $ A$ is defined in terms of the norm defined for the vectors $ {\underline{x}}$ on which it operates,

$\displaystyle \left\Vert\,A\,\right\Vert \mathrel{\stackrel{\mathrm{\Delta}}{=}...
...ert\,A{\underline{x}}\,\right\Vert}{ \left\Vert\,{\underline{x}}\,\right\Vert}

For the $ L2$ norm, we have

$\displaystyle \left\Vert\,A\,\right\Vert _2^2 = \sup_{\underline{x}}\frac{{\underline{x}}^T A^T A{\underline{x}}}{{\underline{x}}^T {\underline{x}}} ,

and this is called the spectral norm of the matrix $ A$.

The Hankel matrix corresponding to a time series $ f$ is defined by $ \Gamma(f)[i,j] \mathrel{\stackrel{\mathrm{\Delta}}{=}}f(i+j)$, i.e.,

\Gamma(f) \mathrel{\stackrel{\mathrm{\Delta}}{=}}\left(
...(2) & & \\
f(2) & & & \\
\vdots & & &

Note that the Hankel matrix involves only causal components of the time series.

The Hankel norm of a filter frequency response is defined as the spectral norm of the Hankel matrix of its impulse response,

$\displaystyle \left\Vert\,F(e^{j\omega})\,\right\Vert _H \mathrel{\stackrel{\mathrm{\Delta}}{=}}\left\Vert\,\Gamma(f)\,\right\Vert _2 .

The Hankel norm is truly a norm only if $ H(z)\in H^{-p}$, i.e., if it is causal. For noncausal filters, it is a pseudo-norm.

If $ F$ is strictly stable, then $ \vert F(e^{j\omega})\vert$ is finite for all $ \omega$, and all norms defined thus far are finite. Also, the Hankel matrix $ \Gamma(f)$ is a bounded linear operator in this case.

The Hankel norm is bounded below by the $ L2$ norm, and bounded above by the $ L-infinity$ norm [1],

$\displaystyle \left\Vert\,F\,\right\Vert _2 \leq \left\Vert\,F\,\right\Vert _H \leq \left\Vert\,F\,\right\Vert _\infty ,

with equality iff $ F$ is an allpass filter (i.e., $ \vert F(e^{j\omega})\vert$ constant).

Next  |  Prev  |  Up  |  Top  |  Index  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

Download gradient.pdf
Download the whole thesis containing this material.

``Elementary Gradient-Based Parameter Estimation'', by Julius O. Smith III, from ``Techniques for Digital Filter Design and System Identification, with Application to the Violin,'' Julius O. Smith III, Ph.D. Dissertation, CCRMA, Department of Electrical Engineering, Stanford University, June 1983.
Copyright © 2006-01-03 by Julius O. Smith III
Center for Computer Research in Music and Acoustics (CCRMA),   Stanford University
CCRMA  [Automatic-links disclaimer]