The main objective of this dissertation work is to reduce the computational complexity of the AP algorithm which is an effective algorithm for the maximum likelihood localization of radiating sources by a passive array of sensors. Since the AP algorithm is iterative in nature, there ar two ways for achieving this purpose. One is to reduce the number of iterations to convergence. The other is to reduce the computational complexity per iteration for the main iteration process and the computational complexity per stop for the initialization procedures.
First, we investigate an improved initialization procedure that reduces the number of iterations to convergence and also guarantees a global convergence. For this purpose, we first develop the sequential estimation approach that lowers the detection threshold of the MUSIC algorithm noticeably through the effective removal of spatial interferences among sources. Computer simulation is done to demonstrate the detection and estimation performance of the proposed MUSIC algorithm, and also to compare the results with those of the conventional algorithm. By modifying the algorithm slightly, we also derive the improved initialization procedure that reduces the number of iterations to convergence and can also guarantees a global convergence. Computer simulation results are included to compare the AP algorithm using the improved initialization procedure with the original AP algorithm in the estimation performance and in the convergence behavior. Further, we develop a recursive computational procedure (RCP) for the sequential MUSIC algorithm and for improved initialization. The procedure reduces significantly the computational complexity per step of the proposed algorithm and the proposed initialization procedure, by transforming the computation of Hermitian forms into that of inner products of vectors only.
Second, we study three different algorithms that can reduce significantly the computational complexity per iteration of the AP algorithm. We also consider simple computational procedures for the initialization procedures of these algorithms. First, in the recursive projection (RP) algorithm, we obtain recursive relations that transform the computation of Hermitian form into that of inner products of vectors only, by utilizing a projection matrix updating formula. In the case of two sources, we develop a simple computational algorithm that can further reduce the computational complexity per iteration by obtaining a simple form of the projection matrix in every iteration. Utilizing the RCP for the improved initialization procedure, we develop a recursive computational procedure that again can reduce significantly the computational complexity per step of the original initialization procedure. Combining the improved initialization procedure based on the RCP with the original one based on the RCP appropriately, we then develop another simple computational procedure for improved initialization, which can be used efficiently for the RP algorithm.
Next, in the maximum eigenvector approximation (MEA) algorithm, we first transform the Hermitian maximization problem in every iteration into a constrained matrix 2-norm problem. We then approximate the constrained matrix 2-norm problem to the problem for maximizing the modules of the projection of steering vectors onto the maximum eigenvector subspace. Using this approximation, we reduce the computation of the Hermitian form for the numerator into that of the inner product of vectors. We validate the approximation under several conditions on the signals, the array, and the precomputed parameters. We further validate the approximation by performing computer simulations. We also transform the computation of the Hermitian form for the denominator to that of the inner products of vectors only, by utilizing a recursive relation for the denominator in the RP algorithm. In the case of two sources, we again reduce further the computational complexity for the denominator by utilizing a simple relation for the denominator of the RP algorithm for the two sources. Applying the approximation to the initialization procedure, we develop a simple computational procedure which does not require any computation of Hermitian forms.
Lastly, in the confined search (CS) algorithm, presuming that, in every iteration, the angular range over which a new estimate can vary from the corresponding previous estimate is limited to within one half beamwidth from the corresponding previous estimate, we confine the search range to within one half beamwidth in either side from the previous estimate of the same parameter. Further, by representing the projection matrix in every iteration as the sum of the outer products of its eigenvectors associated with nonzero eigenvalues, we develop a CS algorithm in which the average computational complexity per search point is not dependent on the number of sensors but dependent on the number of sources only. By applying the confined search scheme to the MEA algorithm, we also develop an MEA algorithm with the confined search. The approximated CS algorithm does not require any additional memory for the main iteration process.
본 논문의 주된 목적은 passive sensor array를 이용한 방사성 신호원의 위치 추정을 위한 ML 방식의 효율적인 계산 알고리듬인 AP 알고리듬의 계산량을 줄이는 것이다. AP 알고리듬의 반복성 때문에, 계산량의 감축은 크게 두가지 방향에서 행하여 지는데, 하나는 수렴하기까지의 반복 횟수를 줄이는 것이며, 다른 하나는 각 반복에서 필요한 계산량을 줄이는 것이다.
먼저, 수렴하기까지의 반복 횟수를 줄이기 위하여, 순차적인 예측방법에 의하여 인접한 신호들 사이의 간섭을 효과적으로 제거함으로서 MUSIC 알고리듬의 detection threshold를 현저하게 낮추는 sequential MUSIC 알고리듬을 제시하였다. Computer simulation에 의하여 이 알고리듬의 고해상 특성을 보여 주었다. 이 알고리듬의 고해상 특성을 이용하여, 수렴하기까지의 반복 횟수를 상당히 많이 줄일 수 있으며, 동시에 local convergence 현상을 거의 대부분 해결할 수 있는 AP 알고리듬의 향상된 초기화과정을 제시하였다. 이 초기화과정의 향상된 성능은 computer simulation에 의하여 입증되었다. 아울러, projection matrix updating formula를 이용하여 각 search point 당 $O(2p^2)$의 계산량을 O(2p)만큼으로 줄이는 sequential MUSIC 알고리듬과 향상된 초기화과정의 효율적인 연산과정을 제안하였다.
다음으로, AP 알고리듬의 각 반복에서 필요한 계산량을 크게 줄이는 세가지 방법과 그들의 효율적인 초기화과정을 제안하였다. 첫 번째 방법으로, projection matrix updating formula를 이용하여 Hermitian form의 계산을 vector들 간의 내적계산으로 대체하여, 각 search point 당 $O(2p^2)$의 계산량을 O(4p)만큼으로 줄이는 RP 알고리듬을 제안하였다. 신호가 두 개인 경우에 projection matrix의 간단한 형태를 이용하여 각 search point 당 $O(2p^2)$의 계산량을 O(2p)만큼으로 줄이는 효율적인 계산 알고리듬을 제안하였다. 또한 RP 알고리듬에 적합한 원래의 초기화과정과 향상된 초기화과정의 효율적인 연산과정을 제안하였다.
두 번째 방법으로, AP 알고리듬의 각 반복에서 변형된 covariance matrix를 그 matrix의 최대 eigenvalue에 해당하는 eigenvector의 외적으로 근사시킴으로서 Hermitian form의 계산을 vector들 간의 내적계산으로 대체하여 각 search point 당 $O(2p^2)$의 계산량을 O(3p)만큼으로 줄이는 MEA 알고리듬을 제안하였다. 앞의 방법과 같이, 신호가 두 개인 경우에 projection matrix의 간단한 형태를 이용하여 각 search point 당 $O(2p^2)$의 계산량을 O(2p)만큼으로 줄이는 효율적인 계산 알고리듬을 제안하였다. 또한 이러한 근사법을 초기화과정에 적용하여 첫 단계에서 Hermitian form의 계산을 피할 수 있는 방법을 제안하였다.
마지막 방법으로, AP 알고리듬의 각 반복에서 search 구간을 동일한 parameter의 이전의 예측치로부터 양쪽으로 절반의 beamwidth에 해당하는 영역내로 제한하여, 전체적으로 아주 많은 양의 계산을 줄이는 CS 알고리듬을 제안하였다. 이러한 search 구간 제한을 원래의 AP 알고리듬에 적용하여 각 search point 당 $O(2p^2)$의 계산량을 평균적으로 O(2(q-1))만큼으로 줄이는 exact CS 알고리듬을 얻었고, MEA 알고리듬에 적용하여 각 search point 당 평균적으로 O(q)만큼으로 줄이는 approximate CS 알고리듬을 얻었다. 일반적으로, sensor들의 갯수 p는 신호의 갯수 q보다 아주 크기 때문에, 이 방법을 이용하면 다른 방법들, 특히 앞의 두 방법과 비교하여 전체적으로 아주 많은 양의 계산을 줄일 수 있다.
