2013 IEEE Workshop on Signal Processing Systems

REAL POLYNOMIAL FORM OF MUSIC FOR UNIFORM LINEAR ARRAY
Xiang Cao∗ , Jingmin Xin

Yoshifumi Nishio

Xi’an Jiaotong University
Institute of Artiﬁcial Intelligence andRobotics
Xi’an 710049, China

The University of Tokushima
Department of Electrical and Electronic
Engineering
Tokushima 770-8506, Japan

ABSTRACT

coefﬁcients. Here, we have to point out that the interested
spatial frequency in Root-MUSIC lies in the interval [−π, π]instead of [0, π]. Since only half of ﬁeld-of-view is considered, the real coefﬁcients polynomial in [5] has the same
degree with standard Root-MUSIC. In this paper, we improve
the result and give the real polynomial form of Root-MUSICin [−π, π]. The same mapping idea also appears in [6] toestimate single target. The interested range is mapped into
real line by a tangent function, while the transformation function is not monotonic within target range. That is to say,the target may not be uniquely determined from the inverse
transformation.
In this paper, a polynomial form with real coefﬁcientsof spectral music is presented. Our method treats the whole
range of interest in uniform linear array. The complexity ofspectral music can be reduced by replacing a large numberof search points by real roots belonging to [−1, 1]. Furthermore, we propose a higher order Root-MUSIC whose variable is only deﬁned on the unit upper semicircle. The similar Root-MUSIC then is transformed into real polynomial
form. The process of solving this polynomial just involves
real arithmetic [7]. Our method also can be used in unitary
Root-MUSIC [8] and unitary MUSIC [9].

This paper presents real polynomial form of multiple signal
characterization (MUSIC) with uniform linear array (ULA).
Firstly, the proposed method can reduce the computationalburden of spectral music by taking the place of a large number of search points by several real roots of polynomial.
Secondly, to transform Root-MUSIC algorithm into polynomial with real coefﬁcients, a higher order Root-MUSIC
whose variable is only deﬁned on the unit upper semicircle ispresented. Furthermore, this paper also improves the results
obtained by J.Selva in 2005.
Index Terms— Parameter estimation, uniform linear array (ULA), array signal processing
1. INTRODUCTION
The multiple signal characterization (MUSIC) algorithm fordirection ﬁnding [1] has been advanced for many years. To
a certain degree, the more search points one use, the moreaccurate results one will obtain. The main computational burden locate the process of spectral search. Thus, many efﬁcient methods are proposed to reduce the search complexityof spectral music.
A called C-MUSIC recently appears in [2]. The approachﬁrstly divided the total interested observation ﬁeld into several equal segments. The virtual source positions can be generated by spectral search over one segment and the ﬁnal estimation values will be selected from these candidates. It showsfrom Figs. 4 and 5 of [2] that the smaller number of segments
may result in the better estimation quality. However, it meansthat C-MUSIC needs more search points to achieve a certain
accuracy.
To avoid the tremendous computation load of spectral
search, Root-MUSIC [3],[4] is proposed. The search-freemethod has an improved resolution threshold. Taking advantage of conformal transformation, the author of [5] translated
the Root-MUSIC into an univariate polynomial with real
∗ Xiang Cao is also with the Department of Electrical and Electronic Engineering, The University of Tokushima,Tokushima 770-8506, Japan

978-1-4673-6238-2/13 $31.00 © 2013 IEEE

366

2. DATA MODEL
Assume p far-ﬁeld narrowband signals {sk } impinging on a
Uniform linear array (ULA) with M (M > p) sensors. The
output vector y(t) of the array at time t can be written asy(t) = A(θ)s(t) + n(t),(1)

where s(t) is the vector of incident signals and n(t) is thevector of additive noises. The so-called array steering matrix
and steering vector have the following form:
A(θ) = [a(θ1 ), a(θ2 ), · · · , a(θp )]

(2)

T

2π
2π
a(θi ) = 1, ej λ d sin(θi ) , · · · , ej λ (M −1)d sin(θi ) ,(3)

here, (·)T denotes transpose operator, d and λ stand for the
distance between two consecutive sensors and the identical
wavelength for all signals, respectively. The restriction of(DOAs) θ1 , · · · , θp lie in the intervalDirections-of-arrival− π2 , π2 for the purpose of eliminating the ambiguity of ULA[10].
Next, we deﬁne spatial frequency ωi = 2π
λ d sin(θi ).
Then, (3) becomesTa(ωi ) = 1, ejωi , · · · , ej(M −1)ωi .

(4)

For guaranteeing the uniqueness of a(ωi ), i = 1, 2, · · · , p,
the spatial frequency ωi are in [−π, π] instead of [0, π] in [5].
In other words, the author in [5] only consider the half of the
DOA range of interest. Since the one-to-one correspondence
between ωi and θi , we only focus on the problem of estimating parameters ωi , i = 1, 2, · · · , p in this paper.
3. REAL POLYNOMIAL FORM OF SPECTRAL
MUSIC
Under the assumptions of the uncorrelated signals and thewhite Gaussian noise, the array covariance matrix can be decomposed into
H
R = E{y(t)y H (t)} = U s Λs U H
s + U n Λn U n .

(5)

It is clear that the columns of A(θ) have the maximum projection on the signal subspace U s and are orthogonal to thenoise subspace U n . With this observation, two natural estimation criterions are to ﬁnd the local maxima or minima [1],viz.
ω̂ = arg max f1 (ω) = arg max aH (ω)U s U H
s a(ω)ωω(6)orω̂ = arg min f2 (ω) = arg min aH (ω)U n U H
n a(ω).
ω
ω

(7)

z=e

,

u = −j(8)

the real point ω belonging to the domain [−π, π] can bemapped to the unique complex point z belonging to the unit

367

z−j
.
z+j

(9)

The above function is a one-to-one mapping that takes theunit upper semicircle to the interval [−1, 1] of real line[5],[6],[13]. Substituting (8) into (9), we get the relationship between ω ∈ [−π, π] and u ∈ [−1, 1] as follows:ω 
u = tan.
(10)
4This is a monotonic function in [−π, π] and its range is[−1, 1]. Thus, once the variable u is estimated, the uniquespatial frequency ω can be obtained by ω = 4 arctan u.
For this purpose, the array vector response a(ω) must beconnected to u.
jω
Using z = −j u−j= −z 2 ( the two equations
u+j and e
can be easily obtained from (8) and (9) ), we get[a(ω)]m = ej(m−1)ω = (−1)m−1 z 2(m−1)

2(m−1)u−j=, m = 1, 2, · · · , M. (11)u+j2(M −1)

Multiplying by (u + j)(here, we note u = −j ), theabove equation then becomes(u + j)2(M −1)2(m−1)

2(M −m)[a(ω)]m = (u − j)(u + j)= cm,2M −2 u2M −2 + · · · + cm,0= cTm v(u), m = 1, 2, · · · , M (12)where the (2M − 1) × 1 coefﬁcient vector cm = [cm,0 , cm,1 ,· · · , cm,2M −2 ]T can be calculated by convolution operation [6],[14], v(u) = [1, u, · · · , u2M −2 ]T is unknown real
vector. Let us deﬁne an M × (2M − 1) matrix C =[c1 , c2 , · · · , cM ]T , the array steering vector a(ω) can be
expresseda(ω) = (u + j)

The total number of complex ﬂops in (6) is Jp(2M + 1)
and the one in (7) is J(M − p)(2M + 1) [11], where J (J 
M > p) is the number of spectral search points. Nevertheless,the subspace decomposition in (5) costs O(M 2 p) complex
ﬂops [12],[2]. We can conclude that the main computationalload of spectral MUSIC is the search steps. Consequently, it isnecessary to reduce the complexity of spectral search process.
Next, we will deduce the real polynomial form of spectral
music with the help of conformal transformation. By deﬁning
a translation
π
j( ω
2+2)

upper semicircle. Furthermore, let us introduce a conformaltransformation2(1−M )

Cv(u).

(13)

Meanwhile,a function’s differential in its local extremum
is zero. We can obtain [5]∂f1 (ω)= 2Re aH (ω)W U s U H
s a(ω) = 0,
∂ω

(14)

where Re{} is a real operator and diagonal matrix W =diag[0, j, · · · , j(M − 1)]. Applying (13),(14), v H (u) =v T (u) and dropping the scalar givesv T (u)Re C H W U s U H
s C v(u) = 0.

(15)This is an univariate polynomial of degree 4(M − 1) with real
coefﬁcients. A similar polynomial with degree 2(M − 1) was
also presented in [5] because the author only consider ω ∈

5HDOSRO\QRPLDO
6SHFWUDO086,&



















4. REAL POLYNOMIAL BASED ROOT-MUSICIn ULA, the Root-MUSIC always has more resolution compared with spectral MUSIC [4]. Thus, it is interesting to look
for a real polynomial form of Root-MUSIC. Using z = ejω ,ω ∈ [0, π] and (9), a real polynomial with degree 2(M − 1)
has been obtained in [5]. If we consider the whole domainω ∈ [−π, π], the conformal transformation equation (9) will
not exist in z = ejω , but exists in (8).
Thus, we can deﬁne the mth element of vector a(z) as
follows:[a(z)]m = (−1)m−1 z 2(m−1) , m = 1, 2, · · · , M.

(16)

The function f2 (ω) in (7) then becomesf2 (z) = aH (z)U n U H
n a(z) = 0.

(17)This is a polynomial of degree 4(M − 1) with complex coefﬁcients and the variable z is deﬁned on the unit upper semicircle instead of the entire unit circle. Recalling (11)-(15) and2(1−M )
using a(z) = (u + j)
Cv(u) , we getv T (u)C H U n U H
n Cv(u) = 0.

(18)

The roots of polynomial in (17) appear in reciprocal pairsz, z1∗ [10] and could not be on the unit circle because of theeffects of noise. The pair roots are related to u by conformaltransformation (9),u1 = −jz−j
1 − jz ∗.
, u2 = −jz+j
1 + jz ∗(19)

Obviously, we have u1 = u∗2 . It is reasonable to conclude thatthe roots in (18) also appear in conjugate pairs like (u, u∗ ). As
a consequence, the equation (18) is a real coefﬁcients polynomial, namelyv T (u)Re C H U n U H
n C v(u) = 0.

(20)

Next, we will analyze how to estimate the spatial frequency ωi , i = 1, 2, · · · , p from the conjugate roots (ui , u∗i ) ,

368





086,&6SHFWUXP[0, π]. However, our interesting targets are in ω ∈ [−π, π][10].
Observing the equation (15), we can ﬁnd that the function is similar to the Root-MUSIC in [3]. The polynomial in
Root-MUSIC is 2(M − 1)-degree complex coefﬁcients and2(M − 1) complex roots have to be solved in complex domain. Nevertheless in (15), we only need to calculate the realroots belonging to [−1, 1] in real domain. For real polynomial, the process of solution can avoid all complex arithmetic
using Bairstow’s method [7]. In practice, ﬁnding roots of afunction usually involve iteration. The operation in (15) isO(16M 2 ) real ﬂops per iteration, while the Root-MUSIC requires O(24M 2 ) real ﬂops per iteration (1 complex ﬂop = 6
real ﬂops) even though polynomial have degree 2(M − 1).






ω







Fig. 1. MUSIC spectrum with 1000 points and Real polynomial spectrum with 14 points. The number of snapshots
N = 100, SNR = 5dB
i = 1, 2, · · · , 2(M − 1) of above polynomial. Assumingz = a + jb, b ≥ 0, the equation (9) becomesu = −j−2a − j a2 + b2 − 1
a + jb − j.
=
2
a + jb + j
a2 + (b + 1)

(21)

When the roots z in (17) are close to the unit circle, the imaginary part of u must tend to zero. Therefore, p real parts ofui can be picked up through comparing the absolution valueof imaginary part of ui , i = 1, 2, · · · , 2(M − 1). The spatial frequency will be given by ωi = 4 arctan [Re (ui )] , i =1, 2, · · · , p.
Note that, although the polynomial in (20) have 4(M −1)degree, its coefﬁcients are real and roots appear in conjugate
pairs. Thus, we only need to solve 2(M −1) roots. The wholeprocess just involve real arithmetic.
5. EXPERIMENTS
In this section, two examples were conducted by computer
simulation. In all scenarios, two equal-power uncorrelated
signals are considered and a ULA have 9 sensors. Meanwhile,
we set spatial frequency ω1 = −0.3, ω2 = 1.2. Here, ω1 can
not be solved in [5].
Example 1: Performance of real polynomial based on
spectral MUSICWe ﬁrstly should calculate ωi = 4 arctan ui , i =1, 2, . . . , Q (ui ∈ [−1, 1] can be obtained by solving thereal polynomial (15)). Then, evaluating the extremumof (6) at ωi , i = 1, 2, · · · , Q can pick up the ﬁnal valueω̂k , k = 1, 2, · · · , p. The computational complexity of theabove process is O(8M 2 + 16QM 2 ) + 6Qp(2M + 1) real
ﬂops [6].



5HDOSRO\QRPLDO
5HDO,PDJSRO\QRPLDO
5RRW086,&





This work was supported in part by the National Natural Science Foundation of China under Grant 61172162, the State
Key Development Program for Basic Research of China under Grant 2010CB327902 and the Suzhou Natural Science
Foundation under Grant SYG201224.




506(

7. ACKNOWLEDGMENT



8. REFERENCES

[1] R. O. Schmidt, “Multiple emitter location and signal
parameter estimation,” IEEE Trans. Antennas Propag.,vol. 53, pp. 276–280, Mar. 1986.




 











615











[2] F. G. Yan, M. Jin, and X. Qao, “Low-complexity doa
estimation based on compressed music and its performance analysis,” IEEE Trans. Signal Process., vol. 61,
pp. 1915–1930, Apr. 2013.

Fig. 2. RMSE of spatial frequency ω=-0.3. The number ofsnapshots N = 100[3] A. J. Barabell, “Improving the resolution performanceof eigenstructure-based direction-ﬁnding algorithms,”
in Proc. ICASSP, Boston, MA, May 1983, pp. 336–339.

In this example, 14 real roots of the polynomial (15) lie inthe domain [−1, 1]. Figure. 1 shows that the proposed method
can capture the extremal point. In addition, our method requires about 21984 real ﬂops, while the spectral MUSIC requires 36000 complex ﬂops. In other words, the computation load of real polynomial algorithm is roughly equal to thespectral MUSIC with 100 search points.
Example 2: Performance of real polynomial based on
Root-MUSICIn the second case, we mainly test the validity of real coefﬁcients polynomial (20). For this purpose, let us introduce
the imaginary part of matrix H = C H U n U H
n C. After simple derivation, we obtain[4] B. D. Rao and K. V. S. Hari, “Performance analysis ofroot-music,” IEEE Trans. Acoust.,Speech, Signal Process., vol. 37, pp. 1939–1949, Dec. 1989.

v T (u) {Re {H} + Im {H}} v(u) = 0.

(22)This approach using (22) named real-imag polynomial andwas indicated by red line in Figure. 2. It is worth pointing
out that (20) and (22) give the same results. That is to say,the coefﬁcients of polynomial (18) are real. Meanwhile, thebehavior of our method have been improved a little at lower
signal-to-noise ratio (SNR) than Root-MUSIC [3].
6. CONCLUSIONS
An univariate polynomial with real coefﬁcients is presented
for reducing the search points in spectral MUSIC. The realroots belonging to [−1, 1] only need to be solved and the process of solution can avoid all complex arithmetic. On theother hand, for improving the results in [5], we propose a similar Root-MUSIC whose variable is deﬁned on the unit uppersemicircle. Then, the complex equation is also transformed
into real polynomial form.

369[5] J. Selva, “Computation of spectral and root music
through real polynomial rooting,” IEEE Trans. Signal
Process., vol. 53, pp. 1923–1927, May 2005.
[6] J. X. Wu, T. Wang, and Z. Bao, “Fast realization of maximum likelihood angle estimation with small adaptive
uniform linear array,” IEEE Trans. Antennas Propag.,vol. 58, pp. 3951–3960, Dec. 2010.
[7] W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P.
Flannery, Numerical recipes in C, Cambridge Univ.
Press, Cambridge, U.K., 1997.
[8] M. Pesavento, A. B. Gershman, and M. Haardt, “Unitary root-music with a real-valued eigendecomposition: a theoretical and experimental performance study,”IEEE Trans. Signal Process., vol. 48, pp. 1306–1314,
May 2000.
[9] K. C. Huarng and C. C. Yeh, “A unitary transformation
method for angle-of-arrival estimation,” IEEE Trans.
signal process., vol. 39, pp. 975–977, Apr. 1991.
[10] P. Stoica and R. L. Moses, Spectral analysis of signals,
Prentice-Hall, 2005.
[11] D. S. Watkins, Fundamentals of matrix computations,Wiley, 2004.
[12] Y. Zhang and B. P. Ng, “Music-like doa estimation without estimating the number of sources,” IEEE Trans. Signal Process., vol. 58, pp. 1668–1676, Mar. 2010.

[13] L. Blanco, J. Serra, and M. Nájar, “Conformal transformation for efﬁcient root-toa estimation,” in Proc. ISCCSP, Malta, Mar. 2008, pp. 1314–1319.
[14] M. Costa and V. Koivunen, “Incorporating array nonidealities into adaptive capon beamformer for source tracking,” in Proc. SAM, Hoboken,NJ, Jun. 2012, pp. 445–
448.

370