5
$\begingroup$

Can someone point me to a webpage or other resource that shows how to analytically solve the beamformer Unconstrained Array Gain expression in Henry Cox's 1987 IEEE paper "Robust Adaptive Beamforming"?

$$ \max_{\mathbf{w}} \frac{|\mathbf{w}^H\mathbf{d}|^2}{\mathbf{w}^H\mathbf{Q}\mathbf{w}} $$

Cox says:

The well-known solution is $\mathbf{w} = \alpha\mathbf{Q}^{-1}\mathbf{d}$

I'd just like to better understand this by learning how to derive this myself.

$\endgroup$
2
  • $\begingroup$ Not 100% sure, but perhaps they calculated the derivative of the expression and validated where the derivative equals 0. $\endgroup$
    – Ben
    Dec 29, 2020 at 19:34
  • $\begingroup$ The solution of this equality constrained quadratic programming problem is possible that uses a pseudoinverse, rather than simple inverse, of matrix Q. For general equality constrained QP problems, this extended solution has a benefit of relaxing the requirement for matrix Q to be strictly positive definite. Don't know if this generalization may be useful for beamformers. $\endgroup$
    – V.V.T
    Jan 1, 2021 at 10:27

3 Answers 3

5
$\begingroup$

A common way is to make use of the Schwarz inequality. First note that:

$$\frac{|w^Hd|^2}{w^HQw} = \frac{|w^HQ^{1/2}Q^{-1/2}d|^2}{w^HQw}$$

Using the Schwarz inequality on the numerator: $$\frac{|w^HQ^{1/2}Q^{-1/2}d|^2}{w^HQw} \leq \frac{(w^HQw)(d^HQ^{-1}d)}{w^HQw} = d^HQ^{-1}d$$

Thus, $$\frac{|w^HQ^{1/2}Q^{-1/2}d|^2}{w^HQw} \leq d^HQ^{-1}d$$

From this, it can easily be seen that the beamformer that achieves equality is $w = \alpha Q^{-1}d$.

Sources:

$\endgroup$
1
  • $\begingroup$ To show that this $w$ maximizes SNR, simply substitute $w = Q^{-1}d$ into the inequality above. First, expand the numerator of the left side of the inequality, noting that $Q$ is Hermitian: $$\frac{|w^HQ^{1/2}Q^{-1/2}d|^2}{w^HQw} = \frac{(w^HQ^{1/2}Q^{-1/2}d)^H(w^HQ^{1/2}Q^{-1/2}d)}{w^HQw} = \frac{d^Hww^Hd}{w^HQw} $$ Then, substituting $w = Q^{-1}d$: $$ \frac{d^Hww^Hd}{w^HQw} = \frac{d^HQ^{-1}dd^HQ^{-1}d}{d^HQ^{-1}QQ^{-1}d} = \frac{d^HQ^{-1}dd^HQ^{-1}d}{d^HQ^{-1}d} = d^HQ^{-1}d $$ Thus, this definition of $w$ achieves the maximum possible SNR indicated by the Schwartz inequality. $\endgroup$
    – Gillespie
    Feb 12, 2021 at 18:37
3
$\begingroup$

You can solve such a problem using the method of Lagrange multipliers. First note that maximizing the expression in your question is equivalent to minimizing the inverse function:

$$\min_{\mathbf{w}}\frac{\mathbf{w}^H\mathbf{Q}\mathbf{w}}{|\mathbf{w}^H\mathbf{d}|^2}\tag{1}$$

Next note that the solution of $(1)$ is invariant to scaling of $\mathbf{w}$, i.e., replacing $\mathbf{w}$ by $c\cdot\mathbf{w}$ in $(1)$ with an arbitrary scalar constant $c$ will not change the value of the function. So we may as well use a scaling such that $\mathbf{w}^H\mathbf{d}=1$ is satisfied. This scaling corresponds to a unity response for the desired signal. With this constraint, problem $(1)$ can be reformulated as

$$\min_{\mathbf{w}}\mathbf{w}^H\mathbf{Q}\mathbf{w}\qquad\textrm{s.t.}\qquad \mathbf{w}^H\mathbf{d}=1\tag{2}$$

We can solve $(2)$ using the method of Lagrange multipliers by minimizing

$$\mathbf{w}^H\mathbf{Q}\mathbf{w}-\lambda(\mathbf{w}^H\mathbf{d}-1)\tag{3}$$

Formally taking the derivative of $(3)$ with respect to $\mathbf{w}^H$ and setting it to zero gives

$$\mathbf{w}=\lambda\mathbf{Q}^{-1}\mathbf{d}\tag{4}$$

The constraint in $(2)$ is satisfied for

$$\lambda=\frac{1}{\mathbf{d}^H\mathbf{Q}^{-1}\mathbf{d}}\tag{5}$$

From $(4)$ and $(5)$ we finally obtain

$$\mathbf{w}=\frac{\mathbf{Q}^{-1}\mathbf{d}}{\mathbf{d}^H\mathbf{Q}^{-1}\mathbf{d}}\tag{6}$$

Note that the scaling in $(6)$ is optional and the general solution is given by $(4)$.

$\endgroup$
5
  • $\begingroup$ Lagrange multipliers are a great trick! Years ago, I had always thought they were a little sketchy, but I've used them to solve several constrained optimization problems. And they work well. $\endgroup$
    – Peter K.
    Dec 29, 2020 at 23:17
  • $\begingroup$ "Formally taking the derivative of (3) with respect of $w^H$": do you suggest that the Lagrangian (3) is the function of three independent variables, $w, w^H,$ and $λ$? If so, you can likewise take the derivative with respect to $w$ and, setting it to zero, arrive at another minimization equation $w^HQ=0$, can't you? $\endgroup$
    – V.V.T
    Jan 1, 2021 at 10:33
  • $\begingroup$ @V.V.T: No, this wouldn't make sense, but I understand that the version I used also looks like it didn't make sense ... This is related to the Wirtinger derivative. Please take a look at this related answer, and the other answer on math.SE that it links to. $\endgroup$
    – Matt L.
    Jan 1, 2021 at 12:11
  • $\begingroup$ I'm quite familiar with "intricacies" of complex differentiation. Struggling to connect the derivation of formula for MOE beamformer weights and the equality constrained QP problems (like, e.g., in cis.upenn.edu/~cis515/cis515-20-sl15.pdf, Def. / Prop. 18.3), I wonder if a factor 1/2 in definition of a real quadratic form matrix (page #821, or 3/39) may be offset for complex-valued matrices rightly as manifestation of these intricacies. Would you please comment on relevance of this explanation? $\endgroup$
    – V.V.T
    Jan 1, 2021 at 13:36
  • $\begingroup$ @V.V.T: Maybe it would be a good idea to formulate this as a full question, either here or maybe even better on math.SE. $\endgroup$
    – Matt L.
    Jan 1, 2021 at 14:24
1
$\begingroup$

First, a sketch of the solution for the maximum SINR beamformer problem $$ \text{max}_{\mathbf{w}} \frac{|\mathbf{w}^H\mathbf{d}|^2}{\mathbf{w}^H\mathbf{Q}\mathbf{w}} $$ Start with writing down a functional $$ \mathbf{w}^H\mathbf{Q}\mathbf{w} $$ to be minimized, and a set of constraints. Indeed, the weight vectors w and wH are considered the two independent set of variables when taking derivates with respect to these variables; therefore, the output signal energy, typically written as a squared modulus of the weights-signals coproduct, has to be written down as an analytic function, without computing the norm that takes the square root: $$ |\mathbf{w}^H\mathbf{d}|^2 = \mathbf{w}^H\mathbf{d}·\mathbf{d}^H\mathbf{w} $$ The resulting set of linear constraints is $$ \mathbf{w}^H\mathbf{d} = c \\ \mathbf{d}^H\mathbf{w} = c^* $$ and we have to write down a Lagrangian with two Lagrange multipliers, λ and μ: $$ \mathbf{w}^H\mathbf{Q}\mathbf{w}-λ(\mathbf{w}^H\mathbf{d}-c)-μ(\mathbf{d}^H\mathbf{w}-c^*) $$ Taking the two derivatives of the Lagrangian -- the first, with respect to w, and the second, with respect to wH -- we obtain the expressions for λ and μ, and, substituting these to the constraint expressions, finally arrive at the formula for weights: $$ \mathbf{w}=c\frac{\mathbf{Q}^{-1}\mathbf{d}}{\mathbf{d}^H\mathbf{Q}^{-1}\mathbf{d}} $$ To my surprize, searching a web for "a webpage or other resource that shows how to analytically solve the beamformer" per OP's request, I could find only curtailed, flawed versions of this formula's derivation, a typical document being the course notes Optimal Beamforming, a detailed and useful introduction into the subject in all the other aspects. I even suspect that the OP posted the question with the purpose to broadcast this omission of the learning resource (excuse my awkward attempt to joke).

For now, I can only recommend the learning material on general linear constraint quadratic programming to students interested in the optimal beamforming. For example, refs. https://www.math.uh.edu/~rohop/fall_06/Chapter3.pdf and https://www.cis.upenn.edu/~cis515/cis515-20-sl15.pdf . Only real-valued quadratic forms are considered in these documents, but the main results can be generalized to the complex domain.

$\endgroup$
6
  • $\begingroup$ Thank you to all who responded. Very helpful. I had no idea that 𝑤 and 𝑤𝐻 could be treated as independent variables. Many of the details here seem to be above my standard math background from electrical engineering. $\endgroup$
    – j03y_
    Jan 2, 2021 at 5:52
  • $\begingroup$ Something else I just noticed - isn't the Gain expression required to be a real number, yet the denominator 𝐰𝐻𝐐𝐰 is complex? $\endgroup$
    – j03y_
    Jan 2, 2021 at 15:11
  • $\begingroup$ Oh - I just figured it out - When Q is Hermitian, the denominator does reduce to a real number. I proved this to myself both by hand with a 2x2 Q and 2x1 w, and in Octave as well. $\endgroup$
    – j03y_
    Jan 2, 2021 at 22:03
  • $\begingroup$ "seem to be above my standard math background from electrical engineering": Wait, your questions on SE reveal, least to say, your intuitive sense of crucial issues arisen from application of math tools (SVD vs. Colesky, remember?). $\endgroup$
    – V.V.T
    Jan 2, 2021 at 23:48
  • $\begingroup$ I know a few radically-minded (and successful) engineers declaring that EE is "a branch of applied mathematics". Certainly it is not, being an autonomous discipline with a distinct field of study, uses, and tooling; but it certainly does use advanced mathematics and, in reciprocal motion, contributes to a development of math theories (e.g., see math.stackexchange.com/questions/226818/…). $\endgroup$
    – V.V.T
    Jan 2, 2021 at 23:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.