Chebyshev FIR Design via Linear Programming

We return now to the $\ensuremath{L_\infty}$ -norm minimization problem of §4.10.2:

$$\min_{\underline{h}}\left\Vert\,\mathbf{A}{\underline{h}}-{\underline{d}}\,\right\Vert _\infty, \protect$$ (5.46)

and discuss its formulation as a linear programming problem, very similar to the optimal window formulations in §3.13. We can rewrite (4.46) as

$$\min_{\underline{h}}\max_k \vert{\underline{a}}_k^T {\underline{h}}- {\underline{d}}_k\vert$$ (5.47)

where ${\underline{a}}_k^T$ denotes the $k$ th row of the matrix $\mathbf {A}$ . This can be expressed as

$$\min\; t$$

$$\vert{\underline{a}}_k^T {\underline{h}}-{\underline{d}}_k\vert<t$$ s.t. (5.48)

Introducing a new variable

$$\tilde{{\underline{h}}} \isdefs \left[ \begin{array}{c} {\underline{h}}\\ t \end{array} \right],$$ (5.49)

then we can write

$$t \eqsp f^T \tilde{{\underline{h}}} \isdefs \left[\begin{array}{cccc} 0 & \cdots & 0 & 1 \end{array}\right] \tilde{{\underline{h}}},$$ (5.50)

and our optimization problem can be written in more standard form:

$$\min_{\tilde{{\underline{h}}}} f^T \tilde{{\underline{h}}}$$

$$\left\vert [\begin{array}{cc} a_k^T \; 0\\ \end{array} ] \cdot \tilde{{\underline{h}}} -{\underline{d}}_k \right\vert \;<\; \tilde{{\underline{h}}}^T f^T\tilde{{\underline{h}}}$$ s.t. (5.51)

Thus, we are minimizing a linear objective, subject to a set of linear inequality constraints. This is known as a linear programming problem, as discussed previously in §3.13.1, and it may be solved using the matlab linprog function. As in the case of optimal window design, linprog is not normally as efficient as the Remez multiple exchange algorithm (firpm), but it is more general, allowing for linear equality and inequality constraints to be imposed.