Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
SAMV (algorithm)
open-in-new
<h2 id="definition">Definition</h2> <p>The formulation of the SAMV algorithm is given as an <a href="/facts/Inverse_problem/Fe01pQ9E">inverse problem</a> in the context of DOA estimation. Suppose an M {\displaystyle M} -element <a href="/facts/Sensor_array/LEuhQDY5">uniform linear array</a> (ULA) receive K {\displaystyle K} narrow band signals emitted from sources located at locations θ = { θ a , … , θ K } {\displaystyle \mathbf {\theta } =\{\theta _{a},\ldots ,\theta _{K}\}} , respectively. The sensors in the ULA accumulates N {\displaystyle N} snapshots over a specific time. The M × 1 {\displaystyle M\times 1} dimensional snapshot vectors are </p> y ( n ) = A x ( n ) + e ( n ) , n = 1 , … , N {\displaystyle \mathbf {y} (n)=\mathbf {A} \mathbf {x} (n)+\mathbf {e} (n),n=1,\ldots ,N} <p>where A = [ a ( θ 1 ) , … , a ( θ K ) ] {\displaystyle \mathbf {A} =[\mathbf {a} (\theta _{1}),\ldots ,\mathbf {a} (\theta _{K})]} is the <a href="/facts/Phased_array/5wvA9WLV">steering matrix</a>, x ( n ) = [ x 1 ( n ) , … , x K ( n ) ] T {\displaystyle {\bf {x}}(n)=[{\bf {x}}_{1}(n),\ldots ,{\bf {x}}_{K}(n)]^{T}} contains the source waveforms, and e ( n ) {\displaystyle {\bf {e}}(n)} is the noise term. Assume that E ( e ( n ) e H ( n ¯ ) ) = σ I M δ n , n ¯ {\displaystyle \mathbf {E} \left({\bf {e}}(n){\bf {e}}^{H}({\bar {n}})\right)=\sigma {\bf {I}}_{M}\delta _{n,{\bar {n}}}} , where δ n , n ¯ {\displaystyle \delta _{n,{\bar {n}}}} is the <a href="/facts/Dirac_delta_function/V8PjRP8T">Dirac delta</a> and it equals to 1 only if n = n ¯ {\displaystyle n={\bar {n}}} and 0 otherwise. Also assume that e ( n ) {\displaystyle {\bf {e}}(n)} and x ( n ) {\displaystyle {\bf {x}}(n)} are independent, and that E ( x ( n ) x H ( n ¯ ) ) = P δ n , n ¯ {\displaystyle \mathbf {E} \left({\bf {x}}(n){\bf {x}}^{H}({\bar {n}})\right)={\bf {P}}\delta _{n,{\bar {n}}}} , where P = Diag ( p 1 , … , p K ) {\displaystyle {\bf {P}}=\operatorname {Diag} ({p_{1},\ldots ,p_{K}})} . Let p {\displaystyle {\bf {p}}} be a vector containing the unknown signal powers and noise variance, p = [ p 1 , … , p K , σ ] T {\displaystyle {\bf {p}}=[p_{1},\ldots ,p_{K},\sigma ]^{T}} . </p><p>The <a href="/facts/Covariance_matrix/kLhgjHC6">covariance matrix</a> of y ( n ) {\displaystyle {\bf {y}}(n)} that contains all information about p {\displaystyle {\boldsymbol {\bf {p}}}} is </p> R = A P A H + σ I . {\displaystyle {\bf {R}}={\bf {A}}{\bf {P}}{\bf {A}}^{H}+\sigma {\bf {I}}.} <p>This covariance matrix can be traditionally estimated by the sample covariance matrix R N = Y Y H / N {\displaystyle {\bf {R}}_{N}={\bf {Y}}{\bf {Y}}^{H}/N} where Y = [ y ( 1 ) , … , y ( N ) ] {\displaystyle {\bf {Y}}=[{\bf {y}}(1),\ldots ,{\bf {y}}(N)]} . After applying the <a href="/facts/Vectorization_(mathematics)/P9a2895l">vectorization operator</a> to the matrix R {\displaystyle {\bf {R}}} , the obtained vector r ( p ) = vec ( R ) {\displaystyle {\bf {r}}({\boldsymbol {\bf {p}}})=\operatorname {vec} ({\bf {R}})} is linearly related to the unknown parameter p {\displaystyle {\boldsymbol {\bf {p}}}} as </p><p> r ( p ) = vec ( R ) = S p {\displaystyle {\bf {r}}({\boldsymbol {\bf {p}}})=\operatorname {vec} ({\bf {R}})={\bf {S}}{\boldsymbol {\bf {p}}}} , </p><p>where S = [ S 1 , a ¯ K + 1 ] {\displaystyle {\bf {S}}=[{\bf {S}}_{1},{\bar {\bf {a}}}_{K+1}]} , S 1 = [ a ¯ 1 , … , a ¯ K ] {\displaystyle {\bf {S}}_{1}=[{\bar {\bf {a}}}_{1},\ldots ,{\bar {\bf {a}}}_{K}]} , a ¯ k = a k ∗ ⊗ a k {\displaystyle {\bar {\bf {a}}}_{k}={\bf {a}}_{k}^{*}\otimes {\bf {a}}_{k}} , k = 1 , … , K {\displaystyle k=1,\ldots ,K} , and let a ¯ K + 1 = vec ( I ) {\displaystyle {\bar {\bf {a}}}_{K+1}=\operatorname {vec} ({\bf {I}})} where ⊗ {\displaystyle \otimes } is the Kronecker product. </p> <h2 id="samv-algorithm">SAMV algorithm</h2> <p>To estimate the parameter p {\displaystyle {\boldsymbol {\bf {p}}}} from the statistic r N {\displaystyle {\bf {r}}_{N}} , we develop a series of iterative SAMV approaches based on the asymptotically minimum variance criterion. From <a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> the covariance matrix Cov p Alg {\displaystyle \operatorname {Cov} _{\boldsymbol {p}}^{\operatorname {Alg} }} of an arbitrary consistent estimator of p {\displaystyle {\boldsymbol {p}}} based on the second-order statistic r N {\displaystyle {\bf {r}}_{N}} is bounded by the real symmetric positive definite matrix </p> Cov p Alg ≥ [ S d H C r − 1 S d ] − 1 , {\displaystyle \operatorname {Cov} _{\boldsymbol {p}}^{\operatorname {Alg} }\geq [{\bf {S}}_{d}^{H}{\bf {C}}_{r}^{-1}{\bf {S}}_{d}]^{-1},} <p>where S d = d r ( p ) / d p {\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 p ^ {\displaystyle {\hat {\bf {p}}}} obtained by minimizing </p> p ^ = arg min p f ( p ) , {\displaystyle {\hat {\boldsymbol {p}}}=\arg \min _{\boldsymbol {p}}f({\boldsymbol {p}}),} <p>where f ( p ) = [ r N − r ( p ) ] H C r − 1 [ r N − r ( p ) ] . {\displaystyle f({\boldsymbol {p}})=[{\bf {r}}_{N}-{\bf {r}}({\boldsymbol {p}})]^{H}{\bf {C}}_{r}^{-1}[{\bf {r}}_{N}-{\bf {r}}({\boldsymbol {p}})].} </p><p>Therefore, the estimate of p {\displaystyle {\boldsymbol {\bf {p}}}} can be obtained iteratively. </p><p>The { p ^ k } k = 1 K {\displaystyle \{{\hat {p}}_{k}\}_{k=1}^{K}} and σ ^ {\displaystyle {\hat {\sigma }}} that minimize f ( p ) {\displaystyle f({\boldsymbol {p}})} can be computed as follows. Assume p ^ k ( i ) {\displaystyle {\hat {p}}_{k}^{(i)}} and σ ^ ( i ) {\displaystyle {\hat {\sigma }}^{(i)}} have been approximated to a certain degree in the i {\displaystyle i} th iteration, they can be refined at the ( i + 1 ) {\displaystyle (i+1)} th iteration by </p> p ^ k ( i + 1 ) = a k H R − 1 ( i ) R N R − 1 ( i ) a k ( a k H R − 1 ( i ) a k ) 2 + p ^ k ( i ) − 1 a k H R − 1 ( i ) a k , k = 1 , … , K {\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} σ ^ ( i + 1 ) = ( Tr ( R − 2 ( i ) R N ) + σ ^ ( i ) Tr ( R − 2 ( i ) ) − Tr ( R − 1 ( i ) ) ) / Tr ( R − 2 ( i ) ) , {\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)}})}},} <p>where the estimate of R {\displaystyle {\bf {R}}} at the i {\displaystyle i} th iteration is given by R ( i ) = A P ( i ) A H + σ ^ ( i ) I {\displaystyle {\bf {R}}^{(i)}={\bf {A}}{\bf {P}}^{(i)}{\bf {A}}^{H}+{\hat {\sigma }}^{(i)}{\bf {I}}} with P ( i ) = Diag ( p ^ 1 ( i ) , … , p ^ K ( i ) ) {\displaystyle {\bf {P}}^{(i)}=\operatorname {Diag} ({\hat {p}}_{1}^{(i)},\ldots ,{\hat {p}}_{K}^{(i)})} . </p> <h2 id="beyond-scanning-grid-accuracy">Beyond scanning grid accuracy</h2> <p>The resolution of most <a href="/facts/Compressed_sensing/aR5DQm3n">compressed sensing</a> based source localization techniques is limited by the fineness of the direction grid that covers the location parameter space.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> In the sparse signal recovery model, the sparsity of the truth signal x ( n ) {\displaystyle \mathbf {x} (n)} is dependent on the distance between the adjacent element in the overcomplete dictionary A {\displaystyle {\bf {A}}} , therefore, the difficulty of choosing the optimum <a href="/facts/Sparse_dictionary_learning/bSDPXQ3D">overcomplete dictionary</a> 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,<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> which refine the location estimates θ = ( θ 1 , … , θ K ) T {\displaystyle {\boldsymbol {\bf {\theta }}}=(\theta _{1},\ldots ,\theta _{K})^{T}} by iteratively minimizing a stochastic <a href="/facts/Maximum_likelihood_estimation/0Yq2dpQD">maximum likelihood</a> cost function with respect to a single scalar parameter θ k {\displaystyle \theta _{k}} . </p> <h2 id="application-to-range-doppler-imaging">Application to range-Doppler imaging</h2> <p>A typical application with the SAMV algorithm in <a href="/facts/Single-input_single-output_system/Bk9Vyswk">SISO</a> <a href="/facts/Radar/jk9BTbFA">radar</a>/<a href="/facts/Sonar/245ooRW7">sonar</a> <a href="/facts/Pulse-Doppler_radar/Ibbq5nJS">range-Doppler imaging</a> problem. This imaging problem is a single-snapshot application, and algorithms compatible with single-snapshot estimation are included, i.e., <a href="/facts/Matched_filter/Tl8Bm687">matched filter</a> (MF, similar to the <a href="/facts/Periodogram/JMjH2MU0">periodogram</a> or <a href="/facts/Radon_transform/JskFJRMS">backprojection</a>, which is often efficiently implemented as <a href="/facts/Fast_Fourier_transform/caT7UUCh">fast Fourier transform</a> (FFT)), IAA,<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> and a variant of the SAMV algorithm (SAMV-0). The simulation conditions are identical to:<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> A 30 {\displaystyle 30} -element polyphase <a href="/facts/Pulse_compression/a8PE1dA1">pulse compression</a> 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} dB power and the rest six are of 25 {\displaystyle 25} dB power. The received signals are assumed to be contaminated with uniform white Gaussian noise of 0 {\displaystyle 0} dB power. </p><p>The <a href="/facts/Matched_filter/Tl8Bm687">matched filter</a> detection result suffers from severe smearing and <a href="/facts/Spectral_leakage/yFqfjdDr">leakage</a> effects both in the Doppler and range domain, hence it is impossible to distinguish the 5 {\displaystyle 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 {\displaystyle 5} dB targets. </p> <h2 id="open-source-implementation">Open source implementation</h2> <p>An open source <a href="/facts/MATLAB/qPjLISCk">MATLAB</a> implementation of SAMV algorithm could be downloaded <a href="https://qilin-zhang.github.io/_pages/zips/Iterative_Sparse_Asymptotic_Minimum_Variance_Based_Approach_Matlab_Codes.zip?raw=true">here</a>. </p> <h2 id="see-also">See also</h2> <ul> <li>Free and open-source software portal</li><li>Science portal</li></ul> <ul><li><a href="/facts/Array_processing/97cb0hmk">Array processing</a> – Area of research in signal processing</li> <li><a href="/facts/Matched_filter/Tl8Bm687">Matched filter</a> – Filters used in signal processing that are optimal in some sense.</li> <li><a href="/facts/Periodogram/JMjH2MU0">Periodogram</a> – Estimate of the spectral density of a signal</li> <li><a href="/facts/Radon_transform/JskFJRMS">Filtered backprojection</a> – Integral transform (Radon transform)</li> <li><a href="/facts/MUSIC_(algorithm)/58Nv6XnY">MUltiple SIgnal Classification</a> – Algorithm used for frequency estimation and radio direction finding (MUSIC), a popular parametric <a href="/facts/Super-resolution_imaging/npt0E08g">superresolution</a> method</li> <li><a href="/facts/Pulse-Doppler_radar/Ibbq5nJS">Pulse-Doppler radar</a> – Type of radar system</li> <li><a href="/facts/Super-resolution_imaging/npt0E08g">Super-resolution imaging</a> – Any technique to improve resolution of an imaging system beyond conventional limits</li> <li><a href="/facts/Compressed_sensing/aR5DQm3n">Compressed sensing</a> – Signal processing technique</li> <li><a href="/facts/Inverse_problem/Fe01pQ9E">Inverse problem</a> – Process of calculating the causal factors that produced a set of observations</li> <li><a href="/facts/Tomographic_reconstruction/rk84hL6s">Tomographic reconstruction</a> – Estimate object properties from a finite number of projections</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>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. <a href="/wiki/Jian_Li_(engineer)" target="_blank">/wiki/Jian_Li_(engineer)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>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. Bibcode:2014SigPr..95...15G. doi:10.1016/j.sigpro.2013.08.003. S2CID 41743051. <a href="/wiki/Jian_Li_(engineer)" target="_blank">/wiki/Jian_Li_(engineer)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>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. <a href="/wiki/Jian_Li_(engineer)" target="_blank">/wiki/Jian_Li_(engineer)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>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. Bibcode:2014SigPr..95...15G. doi:10.1016/j.sigpro.2013.08.003. S2CID 41743051. <a href="/wiki/Jian_Li_(engineer)" target="_blank">/wiki/Jian_Li_(engineer)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>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. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>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. <a href="/wiki/Jian_Li_(engineer)" target="_blank">/wiki/Jian_Li_(engineer)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>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. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>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. <a href="/wiki/Jian_Li_(engineer)" target="_blank">/wiki/Jian_Li_(engineer)</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>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. <a href="/wiki/Jian_Li_(engineer)" target="_blank">/wiki/Jian_Li_(engineer)</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>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. <a href="/wiki/Jian_Li_(engineer)" target="_blank">/wiki/Jian_Li_(engineer)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> </ol>