Just Stuff

Just another WordPress.com weblog

Archive for March 2009

Blocking Matrices

leave a comment »

Proof that the Blocking Matrices do Indeed Block Signals from Specified Directions.

For some/certain signal processing tasks we wish to generate beam patterns with nulls in specified directions (or equivalently; filters with narrow notches at specified frequencies). Typically these can be used to null out stationary interference sources, directions to multipath images of a desired source, …

We assume that we have a number of sensors (M )which may be array elements, subarrays or formed beams and we wish to null signals from directions \theta_1, ..., \theta_k, and k < M, and responses {\bf{b}}(\theta_i) for a source in direction \theta_i (being a column vector of complex signals one element for each sensor). In a narrowband system we may assume there are simply complex numbers representing the sensor amplitude and phase response. We let {\bf{\widehat{b}}}(\theta_i) denote the normalised versions of these signals.

It is obvious (when pointed out anyway) that the matrix:

{\bf{A}}={\bf{I}}_{M\times M} - {\bf{B}} ({\bf{B}}^H{\bf{B}})^{^{-1}} {\bf{B}}^H

is a blocking matrix for directions \theta_1, ..., \theta_k (where {{{\bf{B}}}} is the matrix with \widehat{\bf{b}}(\theta_i)  for its columns). The space of possible sensor outputs constitutes a (complex) vector space of dimension M and the subspace  \text{span}[{\bf{b}}(\theta_i), i=1,\dots ,k]  is the null space of {\bf{A}} and {\bf{A}} behaves like the identity transformation on the orthogonal complement of the null space.

To see that this is a blocking matrix for \widehat{\bf{b}}(\theta_i) we need just consider:

{\bf{AB}} = \left[{\bf{I}}_{M\times M} - {\bf{B}} ({\bf{B}}^H{\bf{B}})^{^{-1}} {\bf{B}}^H\right] {\bf{B}}

so:

{\bf{AB}} = {\bf{B}} - {\bf{B}} ({\bf{B}}^H{\bf{B}})^{^{-1}} {\bf{B}}^H {\bf{B}} ={\bf{0}}

Now the columns of {\bf{AB}} are the vectors {\bf{A\widehat{b}}}(\theta_i) and so these are zeros vectors as expected.

To see that {\bf{A}} behaves like the identity on the orthogonal complement consider {\bf{x}} in the orthogonal complement of the space spanned by the columns of {\bf{B}}. Then {\bf{B}}^H{\bf{x}}={\bf{0}} since each component of this is the dot product of a column of {\bf{B}} and {\bf{x}} and so zero. Hence:

{\bf{Ax}} = \left[{\bf{I}}_{M\times M} - {\bf{B}} ({\bf{B}}^H{\bf{B}})^{^{-1}} {\bf{B}}^H\right] {\bf{x}}

={\bf{x}}+{\bf{B}} ({\bf{B}}^H{\bf{B}})^{^{-1}} {\bf{B}}^H {\bf{x}}

={\bf{x}}

(I hope that is all clear, WordPress LaTeX seems to have started deleting all the \ characters from the LaTeX strings again so there may still be some omissions from when I have tried to restore them)

Advertisements

Written by CaptainBlack

March 25, 2009 at 12:23

Posted in DSP, Maths and Stuff

Tagged with ,

CaptainBlack’s Weakest Link Recording

leave a comment »

Yesterday (11the March 2009) I attended a recording of the Weakest Link Game show as a contestant. Unfortunately I was voted off on the second round, not unfairly as I got the answers to both my questions wrong.

My early departure while not unfair could be construed as unlucky (if not somewhat unlikely!). When preparing for the weakest link I viewed several recent shows on the BBC iPlayer to estimate the number of questions I could typically answer on each round. This gave figures of between 90 and 95% for the first two rounds and something like 70 to 75% for subsequent rounds. This activity was conducted mainly to determine what my banking strategy should be, with these numbers I had decided that I should not bank the teams winnings before my question on the first two rounds, but always on subsequent rounds. It might be interesting to investigate optimal banking strategies but I did not have time for that so I settled for the above rule of thumb.

I had a total of four questions, two on each round, of which I got one right (no I can’t remember that question). The question that I got wrong on the first round was (something like): A trowel is most like what common item of cutlery? My first thought was that a trowel was not like any of the common items of cutlery (fork, knife, spoon) and as the trowel I had in mind was a builders trowel and I use mine like a large pallet knife I opted for knife. After some consultation with friends in the office we concluded that the question setters may have had a gardeners trowel in mind, which as it is dished makes some sense of the “correct” answer of a spoon. I suppose there is a possibility that the question read “garden trowel” but if so I did not hear the “garden”.  On the second round my first question was the second name of the man involved in a celebrity wedding (her name and his first name given). After hearing the answer I am still no wiser as to who they were (and can’t  google for them as I don’t recall their names). The last question was the name of the band responsible for a recent-ish album release (album name given), in this case at least I had heard of the band though am not knowingly familiar with their work. As I knew that the Eagles had released a new album fairly recently (Long Road Out of Eden) I offered them as my answer, the correct answer was “Guns N’ Roses”. There must have been something in the question to suggest that the band was a “classic” otherwise “Eagles” would not have suggested itself as an answer.

As questions like these should represent no more than 10% of all questions in these rounds, I suppose I was just unlucky (or was I? 😉 ).

In the first round we banked a total of £50, we had got up to £800 but then the guy who had the £1000 question received a question like my trowel question (one lacking sufficient reference to allow the victim to make the necessary connections. It was something like: What does the abbreviation CRES stand for on an addressed envelope? Seeing this written down makes this much easier but in the show with no other reference making the connection to crescent was tricky)

Anne grilled me as she does most contestants, She described by job as sexy, I would have described it as cool but sexy is close enough, and asked what I actually do, to which I replied that I mostly sit around drinking coffee, scratching my head and looking puzzled. I was asked if I dyed my hair, the answer is no, but why did she ask, my hair is grey at the sides.

She also asked for a mathematical joke, but I offered a philosophical one, then fluffed it (it was supposed to be the Descartes joke).

It was a very enjoyable experience being on The Weakest Link, a real adrenalin rush. The other players are all friendly (even when planning on stabbing you in the back; I’m thinking of you Denis with one “n”).

Written by CaptainBlack

March 14, 2009 at 08:40

Posted in Blogroll

Tagged with

Cauchy’s Bound for the Roots of a Polynomial

with 4 comments

Preamble

This post serves a number of purposes, the first to demonstrate the use of LaTeX in WordPress, the second to provide a convenient location for the proof of this result which while elementary seems difficult to find clearly stated and proven on-line.

Background

When searching for the roots of a polynomial it is advantageous to have some idea of the part of the real line or complex plane in which they lie. Once the roots are localised in this manner numerical techniques can be employed to find them.

There are a number of ways of localizing roots, particularly real roots, from the rational roots theorem that provides a list a candidates for the rational roots of a polynomial, through Descartes’ rule of signs which provides bounds on the number of positive and negative roots, through various bounds on the roots, of which the Cauchy bound is an example, through to Sturm sequences. All of these methods have their uses, but here I want to give the Cauchy bound.

Cauchy’s Bound on the Roots of a Polynomial

Let:

P(x)=x^n + a_{n-1}x^{n-1}+ ... + a_1 x+a_0

be a monic polynomial of degree n, then if x is a root of P(x), that is a solution of P(x)=0:

|x| \le 1+\max_{i=0,..,n-1} |a_i|

Proof

We will start by assuming that x is a solution of P(x)=0 that has absolute value greater than 1, since if it were otherwise the bound would hold trivially.  Now  rewrite P(x)=0 as:

x^n=-a_0-a_1x- .. -a_{n-1}x^{n-1}

Now if we write h=\max_{i=0,..,n-1} |a_i| then since:

|x^n| \le |a_0|+|a_1||x|+ ... + |a_{n-1}||x^{n-1}|

as |x|>1 and for real  n we have |x^n|=|x|^n we get:

|x|^n \le h [1+|x|+ .. +|x|^{n-1}]

hence the expression inside the square brackets is a finite geometric series so:

|x|^n \le h \frac{|x|^n-1}{|x|-1}

Therefore as |x|>1:

|x|-1 \le h \frac{|x|^n-1}{|x^n|} = h \left( 1-\frac{1}{|x|^n} \right).

Then:

|x|-1 \le h.

and so |x| \le 1+h, which proves what was to be proven.

Example

Consider P(x)=x^2+3x+14, the Cauchy bound for its the roots is 15, and the roots are (approximately) x=-1.5\pm 3.428 i, and |x|\approx 3.741 \le 15 as expected.

[Conclusions on LaTeX on wordpress: the results look OK, but the system is temperamental, at least twice now having stripped out the back slashes from the LaTeX, also on occasion it fails to parse LaTeX code that it parsed earlier.]

Written by CaptainBlack

March 8, 2009 at 11:52

Posted in Maths and Stuff

Tagged with , ,

Review of “The Fred Jane Naval Wargame (1906)”, John Curry (editor)

leave a comment »

This book is part of John Curry series on the History of wargaming and comprises a collection of articles related to the Fred T Jane wargame, and other related material (Published by John Curry Events and Lulu, ISBN 978-1-4092-4407-7).

The main parts of the book are: Background material comprising a short biography of Fred Jane, and introduction to his rules, a fast play variant of the 1905/6 rules by Bob Cordery. The main material comprises the rules of the 1905/06 game, The Royal naval wargame of 1921, and Fred Jane’s 1914 work “Your Navy as a Fighting Machine”.

In general the work provides a window in to a disappeared world which is fascinating. The mechanism of time space and movement of the Jane’s game will be familiar in most respects to the modern wargamer but the gunfire system is what differentiates the game from most of its modern counterparts. Jane’s own explanation for the form of the gunnery system is to teach the effects of guns and armour on naval combat. In this it differs from the main emphasis of most modern games which are more concerned with the tactical and strategic side of naval warfare and in which gunnery is happily treated at a more abstract level. With the models use by Jane the modern gamer would feel instantly at home, they being to a scale of 1:2400, but made of cork.

In a sense the 1921 RN game is not a game in the sense that the term is commonly used today, but is a system for tactical exercises conducted on paper and with models, and the competitive element is deprecated. The object is to develop and evaluate tactics, and the most plausible outcome is sought. Thus all the tables on weapons effectiveness at the end are purely advisory, the umpires are going to decide in practice. This approach possibly provides a context in which reports of the Japanese gaming of the Midway campaign may be made sense of [6][7] (RAdm Ugagi over-ruled the dice which would have resulted in a US air strike sinking both Kaga and Akagi so that only Kaga was sunk and Akagi received only light damage, even then Kaga reappeared at later stages of the gamed operations). The main value to the modern reader other than for the historical interest is that the tables and other rules give the professional opinion of the RN such matters of interest to modern rule designers for the WW 1 and 2 period, at a period when that opinion was be based on operational experience.

An interesting item in the 1921 game is the evaluation of the effectiveness of search plans by overlaying the plan on tracks of a number of target tracks. This is an obvious antecedent of the similar technique used in World war 2 in operational research, which is one of the three main origins of the Monte-Carlo method used extensivly today in operational research and analysis (the others being the use of sampling experiments in statistics, and the modelling of diffusion equations at Los Alamos).
The text of “Your Navy as a Fighting Machine” which given it’s provenance in the first year of The Great War is fascinating in its view of the balance between speed protection and offense in RN and German capital ships. Also strange to modern eyes will be FTJ’s insistence that a naval officer was in reality no better paid than a bus driver, can this really be true?

One negative aspect of this work is the large number of typographic errors which to my eye look like uncorrected Optical Character Recognition errors. Though at least one is inherited from the original publication, this is the description of a ship model for the game as being 15 inches in length, this must be from the original as the exact same phrase occurs in Don Featherstone’s paraphrase/quote of the same source (form context it is evident that the models were 1:2400 scale and so the ship in question was about 1½ inches long, so we are looking at a typo for 1.5  inches, which in itself would be an unusual way of expressing  1½  inches at the period). (This refers to the first version of this book, I understand from the author that this was a typo inherited from Don Featherstone’s book and it found its way into that due to a poor copy of the original article in The Engineer and has now been corrected)

References:
[1] Featherstone D., “Naval War Games”, Stanley Paul 1965
[2] Dunn P., “Sea Battle Games”, Model and Allied Publications 1970
[3] Kimbal G.E. and Morse P.M., “Methods of Operations Research”, Pininsular Publishing 1970 (and Dover reprint 2008)
[4] Waddington C.H., “O.R. in World war 2: Operational Research Against the U-Boat, Elek 1973
[5] Koopman B.O,, “Search and Screening” Pergamon Press 1980
[6] Wilson A., “War Gaming”, Pelican 1970
[7] Prange G.W., “Miracle at Midway”, Penguin 1983

Written by CaptainBlack

March 1, 2009 at 16:48

Posted in Blogroll

Tagged with ,