Number of sources in DOA estimation

Hi everyone,

I have a question relating to direction-of-arrival (DOA) estimation
for MIMO systems. When using an antenna array, would it be possible to
estimate the DOA of more multipath sources than the number of antennas
in the array? The DOA estimation algorithms used are those based on
second-order statistics: subspace-based methods like MUSIC and maximum
likelihood methods like SAGE.

I would think that extracting more inputs (multipath sources) than
outputs (responses of indivual antennas of the array) from a system
seems doubtful. However, you can tell SAGE for example to extract a
number of DOAs that is greater than the number of antenna sensors. I
wonder if it would be reliable to do that?

Thank you very much for your replies.

Greetings,
Emmeric

On Dec 16, 10:31 am, Emmeric <emmeric.tan...@intec.ugent.be> wrote:
> Hi everyone,
>
> I have a question relating to direction-of-arrival (DOA) estimation
> for MIMO systems. When using an antenna array, would it be possible to
> estimate the DOA of more multipath sources than the number of antennas
> in the array? The DOA estimation algorithms used are those based on
> second-order statistics: subspace-based methods like MUSIC and maximum
> likelihood methods like SAGE.
>
> I would think that extracting more inputs (multipath sources) than
> outputs (responses of indivual antennas of the array) from a system
> seems doubtful. However, you can tell SAGE for example to extract a
> number of DOAs that is greater than the number of antenna sensors. I
> wonder if it would be reliable to do that?
>
> Thank you very much for your replies.
>
> Greetings,
> Emmeric

Not using the usual second-order method.  The rank of your covariance
matrix is <= the number of antennas, so how can you estimate a
larger-dimensional subspace than the rank of your matrix?

> Not using the usual second-order method. �The rank of your covariance
> matrix is <= the number of antennas, so how can you estimate a
> larger-dimensional subspace than the rank of your matrix?

Thanks, I thought it would be mathematically impossible using subspace-
based methods.

However, for maximum likelihood methods (SAGE), one could still choose
to find the maximum of the likelihood function for a number of DOAs
that is greater than the number of antennas. But I assume some of
those DOAs would then contribute nothing in the maximum search
operation, and hence be false positives?

On 16 Des, 16:31, Emmeric <emmeric.tan...@intec.ugent.be> wrote:
> Hi everyone,
>
> I have a question relating to direction-of-arrival (DOA) estimation
> for MIMO systems. When using an antenna array, would it be possible to
> estimate the DOA of more multipath sources than the number of antennas
> in the array? The DOA estimation algorithms used are those based on
> second-order statistics: subspace-based methods like MUSIC and maximum
> likelihood methods like SAGE.

Have a look at the methods. With MUSIC the covariance matrix is
represented as two different substaces, in which case one needs
at least one more dimension of the total vector space than
the number sources. Which in turn is intimately related to the
number of sensors in the array.

I don't know the SAGE method, but you need to do a similar
analyis: Is there a relation between the number of sources
and the number of senors? If so, there is a hard limut that
can not be violated, or the method will break down.

> I would think that extracting more inputs (multipath sources) than
> outputs (responses of indivual antennas of the array) from a system
> seems doubtful. However, you can tell SAGE for example to extract a
> number of DOAs that is greater than the number of antenna sensors. I
> wonder if it would be reliable to do that?

Again, you need to do the analysis. If there is a relation
between the numbers of sources and sensors, the output will
be garbage. If there is no siuch relation, you will need to
do some sort of sensitivity analysis, as with DFT-based
beamformers where you need to look at wavelengths, lobewidths,
array lengths etc.

Rune

On 17 dec, 17:54, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 16 Des, 16:31, Emmeric <emmeric.tan...@intec.ugent.be> wrote:
>
> > Hi everyone,
>
> > I have a question relating to direction-of-arrival (DOA) estimation
> > for MIMO systems. When using an antenna array, would it be possible to
> > estimate the DOA of more multipath sources than the number of antennas
> > in the array? The DOA estimation algorithms used are those based on
> > second-order statistics: subspace-based methods like MUSIC and maximum
> > likelihood methods like SAGE.
>
> Have a look at the methods. With MUSIC the covariance matrix is
> represented as two different substaces, in which case one needs
> at least one more dimension of the total vector space than
> the number sources. Which in turn is intimately related to the
> number of sensors in the array.
>
> I don't know the SAGE method, but you need to do a similar
> analyis: Is there a relation between the number of sources
> and the number of senors? If so, there is a hard limut that
> can not be violated, or the method will break down.
>
> > I would think that extracting more inputs (multipath sources) than
> > outputs (responses of indivual antennas of the array) from a system
> > seems doubtful. However, you can tell SAGE for example to extract a
> > number of DOAs that is greater than the number of antenna sensors. I
> > wonder if it would be reliable to do that?
>
> Again, you need to do the analysis. If there is a relation
> between the numbers of sources and sensors, the output will
> be garbage. If there is no siuch relation, you will need to
> do some sort of sensitivity analysis, as with DFT-based
> beamformers where you need to look at wavelengths, lobewidths,
> array lengths etc.
>
> Rune

Thank you. I'm not sure about the relation between number of sources
and sensors in SAGE, but I'll look into it. Though a maximum
likelihood method, SAGE seems to rely on the same basic signal model
of the subspace-based methods, with a separate signal and noise
subspace.

The reason I'm asking these questions is that I've been given a
mathematical model which artificially increases the dimension of the
covariance matrix. For example, if I have 10 antenna sensors, the
covariance matrix would have dimension 10 by 10. The mathematical
model would increase the dimension of the covariance matrix to for
example 15 by 15. This would allow to estimate a maximum of 14 paths
instead of 9. The problem is that I have my doubts that the rank of
the covariance matrix can effectively be increased beyond 10, seeing
there is only data available from 10 sensors.

Greetings,
Emmeric

On 18 Des, 11:17, Emmeric <emmeric.tan...@intec.ugent.be> wrote:
> On 17 dec, 17:54, Rune Allnor <all...@tele.ntnu.no> wrote:
>  Though a maximum
> likelihood method, SAGE seems to rely on the same basic signal model
> of the subspace-based methods, with a separate signal and noise
> subspace.

The 'SA' in the acrony wouldn't by any chance mean 'Simulated
Annealing'?

> The reason I'm asking these questions is that I've been given a
> mathematical model which artificially increases the dimension of the
> covariance matrix. For example, if I have 10 antenna sensors, the
> covariance matrix would have dimension 10 by 10. The mathematical
> model would increase the dimension of the covariance matrix to for
> example 15 by 15.

<shudder!>

> This would allow to estimate a maximum of 14 paths
> instead of 9. The problem is that I have my doubts that the rank of
> the covariance matrix can effectively be increased beyond 10, seeing
> there is only data available from 10 sensors.

I agree with you in that this seems like dodgy stuff. It would
be very interesting to see how that dimension expansion is done.
That kind of stuff would, at the very least, introduce severe
bias to the covariance estmates which in turn might warp
the DoA estimates. The worst-case scenario (and, unfortunately,
a very likely one) is that this expansion is totally arbitrary
with respect to the data (that is, deterministic) and thus
introduces pure garbage in the analysis.

Just proceed with caution. Test these methods to destruction,
use the system with more sources than sensors and see how well
it performs. If possible, set up a large-scale simulation where
you test the methods with known DoAs and see how well the
known parameters are detected by the methods under different
conditions. Do this both for well-defined parameters (e.g. 3
signals and 10 sensors) and expanded parameters (13 signals and
10 sensors).

Remember, these types of methods have been subjected to
great hype over the past several decades, so you need lots
of data to convince your boss or supervisor about any poor
performance of such kinds of things.

Rune

> The 'SA' in the acrony wouldn't by any chance mean 'Simulated
> Annealing'?

SAGE stands for Space Alternating Generalized Expaction-maximization.

> I agree with you in that this seems like dodgy stuff. It would
> be very interesting to see how that dimension expansion is done.
> That kind of stuff would, at the very least, introduce severe
> bias to the covariance estmates which in turn might warp
> the DoA estimates. The worst-case scenario (and, unfortunately,
> a very likely one) is that this expansion is totally arbitrary
> with respect to the data (that is, deterministic) and thus
> introduces pure garbage in the analysis.

For the generic DoA estimation algorithms, a certain signal model is
adopted, which looks like: array response vector = steering
matrix*source vector + noise vector. It seems to me that in the new
mathematical model, the response of one and the same antenna is
repeated a number of times in the array response vector, and each of
these repetitions is set equal to a different expression in the right
hand side of the signal model. These expressions look similar, but are
nonetheless different. I think this is what artificially increases the
rank of the covariance matrix in the right hand side of the signal
model. But the whole thing does not seem to be mathematically sound to
me, I think you cannot equate the same variabele (an antenna response)
with different mathematical expressions in a signal model.

> Just proceed with caution. Test these methods to destruction,
> use the system with more sources than sensors and see how well
> it performs. If possible, set up a large-scale simulation where
> you test the methods with known DoAs and see how well the
> known parameters are detected by the methods under different
> conditions. Do this both for well-defined parameters (e.g. 3
> signals and 10 sensors) and expanded parameters (13 signals and
> 10 sensors).
>
> Remember, these types of methods have been subjected to
> great hype over the past several decades, so you need lots
> of data to convince your boss or supervisor about any poor
> performance of such kinds of things.

I did know about the history of these methods, I just started looking
into them. To me, there seem to be a lot of DoA estimation algorithms
and then again a lot of extensions to these algorithms, with
literature dating back to the early 80's.

> Rune

On 18 Des, 13:40, Emmeric <emmeric.tan...@intec.ugent.be> wrote:

> > I agree with you in that this seems like dodgy stuff. It would
> > be very interesting to see how that dimension expansion is done.
> > That kind of stuff would, at the very least, introduce severe
> > bias to the covariance estmates which in turn might warp
> > the DoA estimates. The worst-case scenario (and, unfortunately,
> > a very likely one) is that this expansion is totally arbitrary
> > with respect to the data (that is, deterministic) and thus
> > introduces pure garbage in the analysis.
>
> For the generic DoA estimation algorithms, a certain signal model is
> adopted, which looks like: array response vector = steering
> matrix*source vector + noise vector.

Seems correct.

> It seems to me that in the new
> mathematical model, the response of one and the same antenna is
> repeated a number of times in the array response vector, and each of
> these repetitions is set equal to a different expression in the right
> hand side of the signal model.

One instance of this is the DFT-based beamformer on the
Uniform Linear Array, where the pattern is cylinder
symmetric around the array axis.

> These expressions look similar, but are
> nonetheless different. I think this is what artificially increases the
> rank of the covariance matrix in the right hand side of the signal
> model.

Careful with the terminology now. The steering matrix can
very well be of a high order. Again, using the DFT-based
beamformer as example one can increase the order of the
steering matrix e.g. by zero-padding the signal.

The essential part here is if the data covariance matrix
is augmented.

Could you please post a link to some documentation for
the SAGE DoA estimator?

> But the whole thing does not seem to be mathematically sound to
> me, I think you cannot equate the same variabele (an antenna response)
> with different mathematical expressions in a signal model.

You can use the same data as input to different algoritms
and get different estimates for the same signal property.
This is the essence of DSP: Use the measurements you can get
to infer something about a quantity you want to observe.

If there are several ways to process the same data to obtain
estimates for the DoA, there will be several estimates for
the DoA.

> > Just proceed with caution. Test these methods to destruction,
> > use the system with more sources than sensors and see how well
> > it performs. If possible, set up a large-scale simulation where
> > you test the methods with known DoAs and see how well the
> > known parameters are detected by the methods under different
> > conditions. Do this both for well-defined parameters (e.g. 3
> > signals and 10 sensors) and expanded parameters (13 signals and
> > 10 sensors).
>
> > Remember, these types of methods have been subjected to
> > great hype over the past several decades, so you need lots
> > of data to convince your boss or supervisor about any poor
> > performance of such kinds of things.
>
> I did know about the history of these methods, I just started looking
> into them. To me, there seem to be a lot of DoA estimation algorithms
> and then again a lot of extensions to these algorithms, with
> literature dating back to the early 80's.

Correct. There was one early paper by Pisarenko in the
early '70s (1973?) and then Ralph O Schmidt published on
MUSIC around 1977. Around 1980-82 there were similar methods
published by Tufts and Kumaresan and in 1989 Roy and Kailath
published ESPRIT. Since then, everybody and his brother have
played with these methods, but - interstingly! - it seems that
very few operational systems actually use them.

Rune

> Careful with the terminology now. The steering matrix can
> very well be of a high order. Again, using the DFT-based
> beamformer as example one can increase the order of the
> steering matrix e.g. by zero-padding the signal.
>
> The essential part here is if the data covariance matrix
> is augmented.

It just seems to me that the augmentation is maybe not done correctly.
To be a bit more specific, to me the model seems to go like this: if
h_k is the response of the k-th antenna of the array, then one line
(row) of the matrix model states that h_k = sum_i (s_i*exp
(j*k*theta_i)), while a bit further, another line says that h_k =
sum_i (s_i*exp(j*(k-1)*theta_i)). If I measure h_k and I get for
example h_k = 0.3 + j*0.2, then 0.3 + j*0.2 = sum_i (s_i*exp
(j*k*theta_i)) will give me a set of DoA estimates theta_i, while
solving 0.3 + j*0.2 = sum_i (s_i*exp(j*(k-1)*theta_i)) will give me
another set of DoA estimates theta_i. Then, both sets of estimates are
thrown together and it is stated each of the estimates is the DoA of a
separate source.

>
> Could you please post a link to some documentation for
> the SAGE DoA estimator?
>

The following paper talks about an efficient implemenation of the SAGE
algorithm (a login is possibly required, I cannot find a freely
available version on the web):

http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V18-46MD8B0-5&_user=794998&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000043466&_version=1&_urlVersion=0&_userid=794998&md5=90a474d9c680380fc452221e58bfbae7

> Correct. There was one early paper by Pisarenko in the
> early '70s (1973?) and then Ralph O Schmidt published on
> MUSIC around 1977. Around 1980-82 there were similar methods
> published by Tufts and Kumaresan and in 1989 Roy and Kailath
> published ESPRIT. Since then, everybody and his brother have
> played with these methods, but - interstingly! - it seems that
> very few operational systems actually use them.

I think we'll also go with the vanilla versions of MUSIC, ESPRIT,
SAGE, ... The numerous extended algorithms in literature would require
a lot of effort to understand and implement, and their benefit (e.g.,
concerning resolution) is not always immediately clear to us.

>
> Rune