Filter design by convex iteration

From Wikimization

(Difference between revisions)
Jump to: navigation, search
Line 63: Line 63:
\textrm{minimize} &\|\textrm{diag}(G)\|_\infty\\
\textrm{minimize} &\|\textrm{diag}(G)\|_\infty\\
\textrm{subject~to}
\textrm{subject~to}
-
& g = \left[ h^\mathrm{H}(n) \, h^\mathrm{H}(n-1) \, ... \, h^\mathrm{H}(n-N)\right] &\\
+
& g = \left[ \left[
 +
\begin{array}{c}
 +
h(n) \\
 +
h(n-1) \\
 +
\vdots \\
 +
h(n-N) \\
 +
\end{array}
 +
\right] &\\
& R(\omega) = r(0)+\!\sum\limits_{n=1}^{N-1}2r(n)\cos(\omega n)\\
& R(\omega) = r(0)+\!\sum\limits_{n=1}^{N-1}2r(n)\cos(\omega n)\\
&\frac{1}{\delta_1^2}\leq R(\omega)\leq\delta_1^2 &\omega\in[0,\omega_p]\\
&\frac{1}{\delta_1^2}\leq R(\omega)\leq\delta_1^2 &\omega\in[0,\omega_p]\\

Revision as of 02:37, 24 August 2010

LaTeX: H(\omega) = h(0) + h(1)e^{-j\omega} + \cdots + h(N-1)e^{-j(N-1)\omega}  where  LaTeX: h(n)\in\mathbb{C}^N denotes impulse response.

For a low pass filter, frequency domain specifications are:

LaTeX: 
\begin{array}{ll}
\frac{1}{\delta_1}\leq|H(\omega)|\leq\delta_1\,, &\omega\in[0,\omega_p]\\
|H(\omega)|\leq\delta_2\,, &\omega\in[\omega_s\,,\pi]
\end{array}

To minimize peak magnitude of LaTeX: h\, , the problem becomes

LaTeX: \begin{array}{cll}
\textrm{minimize} &\|h\|_\infty\\
\textrm{subject~to} &\frac{1}{\delta_1}\leq|H(\omega)|\leq\delta_1\,, &\omega\in[0,\omega_p]\\
&|H(\omega)|\leq\delta_2\,, &\omega\in[\omega_s\,,\pi]
\end{array}

But this problem statement is nonconvex.

So instead, a new vector

LaTeX: 
g \triangleq   \left[
</p>
<pre>              \begin{array}{c}
                h(n) \\
                h(n-1) \\
                \vdots \\
                h(n-N) \\
              \end{array}
            \right]\in\mathbb{C}^{N^2}
</pre>
<p>

is defined by concatenation of time-shifted versions of LaTeX: h\, .

Then

LaTeX: G\triangleq gg^\mathrm{H}=\,\left[\begin{array}{*{20}c}
h(n)h(n)^{\rm H} & h(n)h(n-1)^{\rm H} & h(n)h(n-2)^{\rm H} & \cdots & h(n)h(n-N)^{\rm H}\\
h(n-1)h(n)^{\rm H} & h(n-1)h(n-1)^{\rm H} & h(n-1)h(n-2)^{\rm H} & \cdots & h(n-1)h(n-N)^{\rm H}\\
h(n-2)h(n)^{\rm H} & h(n-2)h(n-1)^{\rm H} & h(n-2)h(n-2)^{\rm H} & \ddots & h(n-2)h(n-N)^{\rm H}\\
\vdots & \vdots & \ddots & \ddots & \vdots\\
h(n-N)h(n)^{\rm H} & h(n-N)h(n-1)^{\rm H} & h(n-N)h(n-2)^{\rm H} & \cdots & h(n-N)h(n-N)^{\rm H}
\end{array}\right]\in\mathbb{C}^{N^2\times N^2}

is a positive semidefinite rank 1 matrix.

Summing along each of LaTeX: 2N-1\, subdiagonals gives entries of the autocorrelation function LaTeX: r\, of LaTeX: h\, .

In particular, the main diagonal of LaTeX: G\, holds squared entries of LaTeX: h\, .

Minimizing LaTeX: \|h\|_\infty is therefore equivalent to minimizing LaTeX: \|\textrm{diag}(G)\|_\infty .


Define LaTeX: I_n\triangleq\,...

By spectral factorization, LaTeX: R(\omega)=|H(\omega)|^2\, , an equivalent problem is:

LaTeX: \begin{array}{cll}
\textrm{minimize} &\|\textrm{diag}(G)\|_\infty\\
\textrm{subject~to} 
& g =   \left[ \left[
</p>
<pre>              \begin{array}{c}
                h(n) \\
                h(n-1) \\
                \vdots \\
                h(n-N) \\
              \end{array}
       \right] &\\
</pre>
<p>& R(\omega) = r(0)+\!\sum\limits_{n=1}^{N-1}2r(n)\cos(\omega n)\\
&\frac{1}{\delta_1^2}\leq R(\omega)\leq\delta_1^2 &\omega\in[0,\omega_p]\\
& R(\omega)\leq\delta_2^2 & \omega\in[\omega_s\,,\pi]\\
& R(\omega)\geq0 & \omega\in[0,\pi]\\
& r(n)=\frac{1}{n}\textrm{trace}(I_{n-N}G) &n=1\ldots N\\
& r(n)=\frac{1}{n-N}\textrm{trace}(I_{n-N}G) &n=N+1\ldots 2N-1\\
& G\succeq0\\
& \textrm{rank}(G) = 1
\end{array}

Excepting the rank constraint, this problem is convex.

N = 32;
delta1 = 0.01;
delta2 = 0.01;

cvx_begin 
  variable h(N,1); 
  variable x(N,1); 
  G = h*h';
  minimize(norm(diag(G),inf));
  r = xcorr(h);
  R = fftcc(r);
  1/delta1^2 <= R <= delta1^2;    %%% range?
cvx_end
Personal tools