SAMV (algorithm)

Summary

SAMV (iterative sparse asymptotic minimum variance[1][2]) is a parameter-free superresolution algorithm for the linear inverse problem in spectral estimation, direction-of-arrival (DOA) estimation and tomographic reconstruction with applications in signal processing, medical imaging and remote sensing. The name was coined in 2013[1] to emphasize its basis on the asymptotically minimum variance (AMV) criterion. It is a powerful tool for the recovery of both the amplitude and frequency characteristics of multiple highly correlated sources in challenging environments (e.g., limited number of snapshots and low signal-to-noise ratio). Applications include synthetic-aperture radar,[2][3] computed tomography scan, and magnetic resonance imaging (MRI).

Definition

edit

The formulation of the SAMV algorithm is given as an inverse problem in the context of DOA estimation. Suppose an  -element uniform linear array (ULA) receive   narrow band signals emitted from sources located at locations  , respectively. The sensors in the ULA accumulates   snapshots over a specific time. The   dimensional snapshot vectors are

 

where   is the steering matrix,   contains the source waveforms, and   is the noise term. Assume that  , where   is the Dirac delta and it equals to 1 only if   and 0 otherwise. Also assume that   and   are independent, and that  , where  . Let   be a vector containing the unknown signal powers and noise variance,  .

The covariance matrix of   that contains all information about   is

 

This covariance matrix can be traditionally estimated by the sample covariance matrix   where  . After applying the vectorization operator to the matrix  , the obtained vector   is linearly related to the unknown parameter   as

 ,

where  ,  ,  ,  , and let   where   is the Kronecker product.

SAMV algorithm

edit

To estimate the parameter   from the statistic  , we develop a series of iterative SAMV approaches based on the asymptotically minimum variance criterion. From,[1] the covariance matrix   of an arbitrary consistent estimator of   based on the second-order statistic   is bounded by the real symmetric positive definite matrix

 

where  . In addition, this lower bound is attained by the covariance matrix of the asymptotic distribution of   obtained by minimizing,

 

where  

Therefore, the estimate of   can be obtained iteratively.

The   and   that minimize   can be computed as follows. Assume   and   have been approximated to a certain degree in the  th iteration, they can be refined at the  th iteration by,

 
 

where the estimate of   at the  th iteration is given by   with  .

Beyond scanning grid accuracy

edit

The resolution of most compressed sensing based source localization techniques is limited by the fineness of the direction grid that covers the location parameter space.[4] In the sparse signal recovery model, the sparsity of the truth signal   is dependent on the distance between the adjacent element in the overcomplete dictionary  , therefore, the difficulty of choosing the optimum overcomplete dictionary arises. The computational complexity is directly proportional to the fineness of the direction grid, a highly dense grid is not computational practical. To overcome this resolution limitation imposed by the grid, the grid-free SAMV-SML (iterative Sparse Asymptotic Minimum Variance - Stochastic Maximum Likelihood) is proposed,[1] which refine the location estimates   by iteratively minimizing a stochastic maximum likelihood cost function with respect to a single scalar parameter  .

Application to range-Doppler imaging

edit
 
SISO range Doppler imaging results comparison with three 5 dB and six 25 dB targets. (a) ground truth, (b) matched filter (MF), (c) IAA algorithm, (d) SAMV-0 algorithm. All power levels are in dB. Both MF and IAA methods are limited in resolution with respect to the doppler axis. SAMV-0 offers superior resolution in terms of both range and doppler.[1]

A typical application with the SAMV algorithm in SISO radar/sonar range-Doppler imaging problem. This imaging problem is a single-snapshot application, and algorithms compatible with single-snapshot estimation are included, i.e., matched filter (MF, similar to the periodogram or backprojection, which is often efficiently implemented as fast Fourier transform (FFT)), IAA,[5] and a variant of the SAMV algorithm (SAMV-0). The simulation conditions are identical to:[5] A  -element polyphase pulse compression P3 code is employed as the transmitted pulse, and a total of nine moving targets are simulated. Of all the moving targets, three are of   dB power and the rest six are of   dB power. The received signals are assumed to be contaminated with uniform white Gaussian noise of   dB power.

The matched filter detection result suffers from severe smearing and leakage effects both in the Doppler and range domain, hence it is impossible to distinguish the   dB targets. On contrary, the IAA algorithm offers enhanced imaging results with observable target range estimates and Doppler frequencies. The SAMV-0 approach provides highly sparse result and eliminates the smearing effects completely, but it misses the weak   dB targets.

Open source implementation

edit

An open source MATLAB implementation of SAMV algorithm could be downloaded here.

See also

edit

References

edit
  1. ^ a b c d e Abeida, Habti; Zhang, Qilin; Li, Jian; Merabtine, Nadjim (2013). "Iterative Sparse Asymptotic Minimum Variance Based Approaches for Array Processing" (PDF). IEEE Transactions on Signal Processing. 61 (4): 933–944. arXiv:1802.03070. Bibcode:2013ITSP...61..933A. doi:10.1109/tsp.2012.2231676. ISSN 1053-587X. S2CID 16276001.
  2. ^ a b Glentis, George-Othon; Zhao, Kexin; Jakobsson, Andreas; Abeida, Habti; Li, Jian (2014). "SAR imaging via efficient implementations of sparse ML approaches" (PDF). Signal Processing. 95: 15–26. doi:10.1016/j.sigpro.2013.08.003. S2CID 41743051.
  3. ^ Yang, Xuemin; Li, Guangjun; Zheng, Zhi (2015-02-03). "DOA Estimation of Noncircular Signal Based on Sparse Representation". Wireless Personal Communications. 82 (4): 2363–2375. doi:10.1007/s11277-015-2352-z. S2CID 33008200.
  4. ^ Malioutov, D.; Cetin, M.; Willsky, A.S. (2005). "A sparse signal reconstruction perspective for source localization with sensor arrays". IEEE Transactions on Signal Processing. 53 (8): 3010–3022. Bibcode:2005ITSP...53.3010M. doi:10.1109/tsp.2005.850882. hdl:1721.1/87445. S2CID 6876056.
  5. ^ a b Yardibi, Tarik; Li, Jian; Stoica, Petre; Xue, Ming; Baggeroer, Arthur B. (2010). "Source Localization and Sensing: A Nonparametric Iterative Adaptive Approach Based on Weighted Least Squares". IEEE Transactions on Aerospace and Electronic Systems. 46 (1): 425–443. Bibcode:2010ITAES..46..425Y. doi:10.1109/taes.2010.5417172. hdl:1721.1/59588. S2CID 18834345.