Complex Least Squares Approximation

Question

In the case of frequency domain FIR filter design, the error function given by :

$$E(\omega)=H(e^{j\omega})-D(e^{j\omega}) \tag{1}$$

is a linear function with respect to the unknown filter coefficients $h[n]$. Hence, the Least Squares frequency domain FIR filter design problem is a linear LS problem which can be solved by computing the solution to a system of linear equations. (from this: Algorithms for the Constrained Design of Digital Filters with Arbitrary Magnitude and Phase Responses ).

I have a three questions :

• How the error respect the unknown filter coefficient ?

• Does equation (1) is the same : $E(\omega)=D(e^{j\omega})-H(e^{j\omega})~$?

• Does this case is available with negative domain of frequency ?

Thank you in advance.

Answer 1

Even though I think there is a lot of valuable general information in Stanley Pawlukiewicz's answer and in Royi's answer, I think that some specific questions have not been answered, at least as far as I understand the OP's questions.

Let me go through the 3 bullet points in the OP one by one:

1. If you mean how the error function depends on the filter coefficients, then for a length $N$ FIR filter you simply have $$H(e^{j\omega})=\sum_{n=0}^{N-1}h[n]e^{-jn\omega}=\mathbf{c}^H(\omega)\cdot \mathbf{h}\tag{1}$$

where $\mathbf{h}$ is the vector of filter coefficients, $\mathbf{c}(\omega)$ is given by $\mathbf{c}(\omega)=[1,e^{j\omega},\ldots,e^{j(N-1)\omega}]$, and $^H$ denotes the Hermitian conjugate. Clearly, $(1)$ is a linear function of the filter coefficients, hence the error function $E(\omega)$ is linear in $\mathbf{h}$.

2. The sign of the error function is irrelevant, because you end up minimizing a squared error measure, which depends on $|E(\omega)|^2$, and which is, consequently, independent of the sign of $E(\omega)$.

3. I did my best to understand what is meant by the third question but I failed. Maybe the OP can elaborate in a comment or by editing the question.

Answer 2

It's hard to tell where to start, so please ignore what is not necessary.

I took an optimization course a number of years ago that was in an EE department using

Luenberger, David G. Linear and nonlinear programming. Reading, MA: Addison-wesley, 1984.

as one of the texts. I recall asking about Complex Variables and being told that you should just convert your problem to Real Variables. Given that Luenberger is a Engineer, one feels doubly disappointed.

When one does a least anything (squares included), you need a relationship $a \le b$ which is obvious for real variables but for Complex number $a < b $ is ambiguous. In Matlab the test $a < b $ is converted to $|a| < |b| $. You can have $|a| = |b| $ but that does not mean that $a = b $. They can differ in phase.

In complex least squares, the objective function is a real function of a complex variable. In the case $ f(a)= |a| $ or $ g(a)= |a|^2 = a \;\text{conj}(a)$ we can have $g(a)=g(b)$ where $a \ne b$. In general the Cauchy Reimann condition for a real function of a complex variable is not analytic. $\frac{d}{dx} g(x)$ is flat with respect to phase,

The is fixed by having real function of the form $g( x , \text{conj(x)})$ where $x$ and $\text{conj}(x)$ are considered independent variables. This looks strange but one can transform $x$ and $\text{conj}(x)$ to $\text{real}(x)$ and $\text{imag}(x)$ and $h( \text{real}(x), \text{imag}(x))$ is perfectly reasonable.

This device is called a Brandwood Derivative.

Brandwood, D. H. "A complex gradient operator and its application in adaptive array theory." IEE Proceedings H-Microwaves, Optics and Antennas. Vol. 130. No. 1. IET, 1983.

As an example $$ \frac{d}{dx^H} x^H R x = Rx $$

There are appendices in

Van Trees, Harry L. Optimum array processing: Part IV of detection, estimation, and modulation theory. John Wiley & Sons, 2004.

and

Kailath T, Sayed AH, Hassibi B. Linear estimation. Prentice Hall; 2000.

that cover the topic. Kailath being particularly applicable to least squares.

For more complicated optimizations of real functions of complex variables,

Sorber, Laurent, Marc Van Barel, and Lieven De Lathauwer. "Unconstrained optimization of real functions in complex variables." SIAM Journal on Optimization 22.3 (2012): 879-898.

This paper is actually worth reading.

Answer 3

Let's assume we have $ m $ points in the Fourier Domain (Discrete Fourier Domain) for our reference frequency response. We'll designate their values by $ y \in \mathbb{C}^{m} $.

Also we need a filter of $ n $ coefficients to approximate the reference response as good as it can. We'll use $ h $ for that.

We need now the Fourier Matrix, $ F \in \mathbb{C}^{m \times n} $ in order to write the following linear complex least squares problem:

$$ \arg \min_{h} \frac{1}{2} {\left\| F h - y \right\|}_{2}^{2} $$

You could easily write this also in a Sum Form.
The nice thing about it is the solution is give by the classic Least Squares solution - $ \hat{h} = {\left( {F}^{H} F \right)}^{-1} {F}^{H} y $.

Of course, in practice, you need many point in frequency domain to add more and more restrictions. You could also write a continuous version of this problem using the DTFT.