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 environment (e.g., limited number of snapshots, low signal-to-noise ratio. Applications include synthetic-aperture radar[2][3], computed tomography scan, and magnetic resonance imaging (MRI).
Definition
The formulation of the SAMV algorithm is given as an inverse problem in the context of DOA estimation. Suppose an M-element uniform linear array (ULA) receive K narrow band signals emitted from sources located at locations \( {\displaystyle \mathbf {\theta } =\{\theta _{a},\ldots ,\theta _{K}\}} \), respectively. The sensors in the ULA accumulates N snapshots over a specific time. The \( M \times 1 \) dimensional snapshot vectors are
\( {\displaystyle \mathbf {y} (n)=\mathbf {A} \mathbf {x} (n)+\mathbf {e} (n),n=1,\ldots ,N} \)
where \( {\displaystyle \mathbf {A} =[\mathbf {a} (\theta _{1}),\ldots ,\mathbf {a} (\theta _{K})]} \) is the steering matrix, \( {\displaystyle {\bf {x}}(n)=[{\bf {x}}_{1}(n),\ldots ,{\bf {x}}_{K}(n)]^{T}} \) contains the source waveforms, and \( {\displaystyle {\bf {e}}(n)} \) is the noise term. Assume that \( {\displaystyle \mathbf {E} \left({\bf {e}}(n){\bf {e}}^{H}({\bar {n}})\right)=\sigma {\bf {I}}_{M}\delta _{n,{\bar {n}}}} \), where \( {\displaystyle \delta _{n,{\bar {n}}}} \) is the Dirac delta and it equals to 1 only if \( {\displaystyle n={\bar {n}}} \) and 0 otherwise. Also assume that \( {\displaystyle {\bf {e}}(n)} \) and \( {\displaystyle {\bf {x}}(n)} \) are independent, and that \( {\displaystyle \mathbf {E} \left({\bf {x}}(n){\bf {x}}^{H}({\bar {n}})\right)={\bf {P}}\delta _{n,{\bar {n}}}} \), where \( {\displaystyle {\bf {P}}=\operatorname {Diag} ({p_{1},\ldots ,p_{K}})} \). Let \( {\displaystyle {\bf {p}}} \) be a vector containing the unknown signal powers and noise variance, \( {\displaystyle {\bf {p}}=[p_{1},\ldots ,p_{K},\sigma ]^{T}} \).
The covariance matrix of \( {\displaystyle {\bf {y}}(n)} \) that contains all information about p {\displaystyle {\boldsymbol {\bf {p}}}} {\displaystyle {\boldsymbol {\bf {p}}}} is
\( {\displaystyle {\bf {R}}={\bf {A}}{\bf {P}}{\bf {A}}^{H}+\sigma {\bf {I}}.}
This covariance matrix can be traditionally estimated by the sample covariance matrix \( {\displaystyle {\bf {R}}_{N}={\bf {Y}}{\bf {Y}}^{H}/N} \) where \( {\displaystyle {\bf {Y}}=[{\bf {y}}(1),\ldots ,{\bf {y}}(N)]} \). After applying the vectorization operator to the matrix \( {\displaystyle {\bf {R}}} \), the obtained vector \( {\displaystyle {\bf {r}}({\boldsymbol {\bf {p}}})=\operatorname {vec} ({\bf {R}})} \) is linearly related to the unknown parameter \( {\displaystyle {\boldsymbol {\bf {p}}}} \) as
\( {\displaystyle {\bf {r}}({\boldsymbol {\bf {p}}})=\operatorname {vec} ({\bf {R}})={\bf {S}}{\boldsymbol {\bf {p}}}},
where \( {\displaystyle {\bf {S}}=[{\bf {S}}_{1},{\bar {\bf {a}}}_{K+1}]} \), \( {\displaystyle {\bf {S}}_{1}=[{\bar {\bf {a}}}_{1},\ldots ,{\bar {\bf {a}}}_{K}]} \) , \( {\displaystyle {\bar {\bf {a}}}_{k}={\bf {a}}_{k}^{*}\otimes {\bf {a}}_{k}} \), \( {\displaystyle k=1,\ldots ,K} \), and let \( {\displaystyle {\bar {\bf {a}}}_{K+1}=\operatorname {vec} ({\bf {I}})} \) where \( \otimes \) is the Kronecker product.
SAMV algorithm
To estimate the parameter \( {\displaystyle {\boldsymbol {\bf {p}}}} \) from the statistic \( {\displaystyle {\bf {r}}_{N}} \), we develop a series of iterative SAMV approaches based on the asymptotically minimum variance criterion. From [1], the covariance matrix \( {\displaystyle \operatorname {Cov} _{\boldsymbol {p}}^{\operatorname {Alg} }} \) of an arbitrary consistent estimator of \( {\boldsymbol {p}} \) based on the second-order statistic \( {\displaystyle {\bf {r}}_{N}} \) is bounded by the real symmetric positive definite matrix
\( {\displaystyle \operatorname {Cov} _{\boldsymbol {p}}^{\operatorname {Alg} }\geq [{\bf {S}}_{d}^{H}{\bf {C}}_{r}^{-1}{\bf {S}}_{d}]^{-1},}
where \( {\displaystyle {\bf {S}}_{d}={\rm {d}}{\bf {r}}({\boldsymbol {p}})/{\rm {d}}{\boldsymbol {p}}} \). In addition, this lower bound is attained by the covariance matrix of the asymptotic distribution of \( {\displaystyle {\hat {\bf {p}}}} \) obtained by minimizing,
\( {\displaystyle {\hat {\boldsymbol {p}}}=\arg \min _{\boldsymbol {p}}f({\boldsymbol {p}}),} \)
where \( {\displaystyle f({\boldsymbol {p}})=[{\bf {r}}_{N}-{\bf {r}}({\boldsymbol {p}})]^{H}{\bf {C}}_{r}^{-1}[{\bf {r}}_{N}-{\bf {r}}({\boldsymbol {p}})].} \)
Therefore, the estimate of \( {\displaystyle {\boldsymbol {\bf {p}}}} \) can be obtained iteratively.
The \( {\displaystyle \{{\hat {p}}_{k}\}_{k=1}^{K}} \) and \( {\hat {\sigma }} \) that minimize f ( p ) {\displaystyle f({\boldsymbol {p}})} {\displaystyle f({\boldsymbol {p}})} can be computed as follows. Assume \( {\displaystyle {\hat {p}}_{k}^{(i)}} \) and \( {\displaystyle {\hat {\sigma }}^{(i)}} \) have been approximated to a certain degree in the i {\displaystyle i} ith iteration, they can be refined at the (i+1)th iteration by,
\( {\displaystyle {\hat {p}}_{k}^{(i+1)}={\frac {{\bf {a}}_{k}^{H}{\bf {R}}^{-1{(i)}}{\bf {R}}_{N}{\bf {R}}^{-1{(i)}}{\bf {a}}_{k}}{({\bf {a}}_{k}^{H}{\bf {R}}^{-1{(i)}}{\bf {a}}_{k})^{2}}}+{\hat {p}}_{k}^{(i)}-{\frac {1}{{\bf {a}}_{k}^{H}{\bf {R}}^{-1{(i)}}{\bf {a}}_{k}}},\quad k=1,\ldots ,K} \)
\( {\displaystyle {\hat {\sigma }}^{(i+1)}=\left(\operatorname {Tr} ({\bf {R}}^{-2^{(i)}}{\bf {R}}_{N})+{\hat {\sigma }}^{(i)}\operatorname {Tr} ({\bf {R}}^{-2^{(i)}})-\operatorname {Tr} ({\bf {R}}^{-1^{(i)}})\right)/{\operatorname {Tr} {({\bf {R}}^{-2^{(i)}})}},} \)
where the estimate of \( {\displaystyle {\bf {R}}}\) at the ith iteration is given by \( {\displaystyle {\bf {R}}^{(i)}={\bf {A}}{\bf {P}}^{(i)}{\bf {A}}^{H}+{\hat {\sigma }}^{(i)}{\bf {I}}} \) with \( {\displaystyle {\bf {P}}^{(i)}=\operatorname {Diag} ({\hat {p}}_{1}^{(i)},\ldots ,{\hat {p}}_{K}^{(i)})}. \)
Beyond scanning grid accuracy
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 x\( {\displaystyle \mathbf {x} (n)} \) is dependent on the distance between the adjacent element in the overcomplete dictionary \( {\displaystyle {\bf {A}}} \) , 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 \( {\displaystyle {\boldsymbol {\bf {\theta }}}=(\theta _{1},\ldots ,\theta _{K})^{T}} \) by iteratively minimizing a stochastic maximum likelihood cost function with respect to a single scalar parameter \( \theta _{k} \).
Application to range-Doppler imaging
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 30 {\displaystyle 30} 30-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 5 {\displaystyle 5} 5 dB power and the rest six are of 25 {\displaystyle 25} 25 dB power. The received signals are assumed to be contaminated with uniform white Gaussian noise of \( {\displaystyle 0} \) 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 5 {\displaystyle 5} 5 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 5 dB targets.
Open source implementation
Free and open-source software portal
An open source MATLAB implementation of SAMV algorithm could be downloaded here.
See also
Array processing
Matched filter
Periodogram
Filtered backprojection (Radon transform)
MUltiple SIgnal Classification (MUSIC), a popular parametric superresolution method
Pulse-Doppler radar
Super-resolution imaging
Compressed sensing
Inverse problem
Tomographic reconstruction
References
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.
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.
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.
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.
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.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
