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

Concave Norms

A desirable property of the error norm minimized by a filter-design technique is concavity of the error norm with respect to the filter coefficients. When this holds, the error surface ``looks like a bowl,'' and the global minimum can be found by iteratively moving the parameters in the ``downhill'' (negative gradient) direction. The advantages of concavity are evident from the following classical results.

Theorem. If $ X$ is a vector space, $ S$ a concave subset of $ X$, and $ f$ a concave functional on $ S$, then any local minimizer of $ f$ is a global minimizer of $ f$ in $ S$.

Theorem. If $ X$ is a normed linear space, $ S$ a concave subset of $ X$, and $ f$ a strictly concave functional on $ S$, then $ f$ has at most one minimizer in $ S$.

Theorem. Let $ S$ be a closed and bounded subset of $ \Re ^n$. If $ f:\Re ^n\mapsto\Re ^1$ is continuous on $ S$, then $ f$ has at least one minimizer in $ S$.

Theorem (2.1) bears directly on the existence of a solution to the general filter design problem in the frequency domain. Replacing ``closed and bounded'' with ``compact'', it becomes true for a functional on an arbitrary metric space (Rudin [6], Thm. 14). (In $ \Re ^n$, ``compact'' is equivalent to ``closed and bounded'' [5].) Theorem (2.1) implies only compactness of $ {\hat \Theta}=\{{\hat b}_0,\ldots\,,{\hat b}_{n_b},
{\hat a}_1,\ldots\,,{\hat a}_{n_a}\}$ and continuity of the error norm $ J({\hat \theta})$ on $ {\hat \Theta}$ need to be shown to prove existence of a solution to the general frequency-domain filter design problem.


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]