SAMV (algorithm)

SAMV (iterative Sparse Asymptotic Minimum Variance) is an parameter-free superresolution algorithm for spectral estimation and direction-of-arrival (DOA) estimation in signal processing. The name was coined in 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 SNR). Applications include SAR imaging and various source localization.

Definition

The formulation of the SAMV algorithm is given in the context of DOA estimation. Suppose an $M$-element uniform linear array (ULA) receives $K$ narrow band signals impinging from sources located at $\mathbf {\theta } =\{\theta _{a},\cdots ,\theta _{K}\}$, and accumulates $N$ snapshots. The $M\times 1$ dimensional snapshot vectors can be modeled as

$\mathbf {y} (n)=\mathbf {A} \mathbf {x} (n)+\mathbf {e} (n),n=1,\cdots ,N$

where $\mathbf {A} =[\mathbf {a} (\theta _{1}),\cdots ,\mathbf {a} (\theta _{K})]$ is the steering matrix, ${\bf {x}}(n)=[{\bf {x}}_{1}(n),\ldots ,{\bf {x}}_{K}(n)]^{T}$ contains the source waveforms, and ${\bf {e}}(n)$ is the noise term. Assume that $\mathbf {E} \left({\bf {e}}(n){\bf {e}}^{H}({\bar {n}})\right)=\sigma {\bf {I}}_{M}\delta _{n,{\bar {n}}}$, where $\delta _{n,{\bar {n}}}$ is the Dirac delta and it equals to 1 only if $n={\bar {n}}$ and 0 otherwise. We also assume that ${\bf {e}}(n)$ and ${\bf {x}}(n)$ are independent, and that $\mathbf {E} \left({\bf {x}}(n){\bf {x}}^{H}({\bar {n}})\right)={\bf {P}}\delta _{n,{\bar {n}}}$, where ${\bf {P}}={\mbox{Diag}}({p_{1},\ldots ,p_{K}})$. Let ${\bf {p}}$ be a vector containing the unknown signal powers and noise variance, ${\bf {p}}=[p_{1},\ldots ,p_{K},\sigma ]^{T}$.

The covariance matrix of ${\bf {y}}(n)$ that contains all information about ${\boldsymbol {\bf {p}}}$ is given by

${\bf {R}}={\bf {A}}{\bf {P}}{\bf {A}}^{H}+\sigma {\bf {I}}$.

This covariance matrix is traditionally estimated by the sample covariance matrix ${\bf {R}}_{N}={\bf {Y}}{\bf {Y}}^{H}/N$ where ${\bf {Y}}=[{\bf {y}}(1),\cdots ,{\bf {y}}(N)]$. After applying the vectorization operator to the matrix ${\bf {R}}$, the obtained vector ${\bf {r}}({\boldsymbol {\bf {p}}})={\mbox{vec}}({\bf {R}})$ is linearly related to the unknown parameter ${\boldsymbol {\bf {p}}}$ as

${\bf {r}}({\boldsymbol {\bf {p}}})={\mbox{vec}}({\bf {R}})={\bf {S}}{\boldsymbol {\bf {p}}}$,

where ${\bf {S}}=[{\bf {S}}_{1},{\bar {\bf {a}}}_{K+1}]$, ${\bf {S}}_{1}=[{\bar {\bf {a}}}_{1},\cdots ,{\bar {\bf {a}}}_{K}]$, ${\bar {\bf {a}}}_{k}={\bf {a}}_{k}^{*}\otimes {\bf {a}}_{k}$, $k=1,\cdots K$, and let ${\bar {\bf {a}}}_{K+1}={\mbox{vec}}({\bf {I}})$.

SAMV algorithm

To estimate the parameter ${\boldsymbol {\bf {p}}}$ from the statistic ${\bf {r}}_{N}$, we develop a series of iterative SAMV approaches based on the asymptotically minimum variance criterion. From , the covariance matrix ${\bf {Cov}}_{\boldsymbol {p}}^{\mbox{Alg}}$ of an arbitrary consistent estimator of ${\boldsymbol {p}}$ based on the second-order statistic ${\bf {r}}_{N}$ is bounded by the real symmetric positive definite matrix

${\bf {Cov}}_{\boldsymbol {p}}^{\mbox{Alg}}\geq [{\bf {S}}_{d}^{H}{\bf {C}}_{r}^{-1}{\bf {S}}_{d}]^{-1}$,

where ${\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 ${\hat {\bf {p}}}$ obtained by minimizing,

${\hat {\boldsymbol {p}}}=\arg \min _{\boldsymbol {p}}f({\boldsymbol {p}})$,

where $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 ${\boldsymbol {\bf {p}}}$ can be obtained iteratively.

The $\{{\hat {p}}_{k}\}_{k=1}^{K}$ and ${\hat {\sigma }}$ that minimize $f({\boldsymbol {p}})$ can be computed as follows. Assume ${\hat {p}}_{k}^{(i)}$ and ${\hat {\sigma }}^{(i)}$ have been approximated to a certain degree in the $i$th iteration, they can be refined at the $(i+1)$th iteration by,

${\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}}}$, $k=1,\cdots ,K$

${\hat {\sigma }}^{(i+1)}=\left(\mathrm {Tr} ({\bf {R}}^{-2^{(i)}}{\bf {R}}_{N})+{\hat {\sigma }}^{(i)}\mathrm {Tr} ({\bf {R}}^{-2^{(i)}})-\mathrm {Tr} ({\bf {R}}^{-1^{(i)}})\right)/{\mathrm {Tr} {({\bf {R}}^{-2^{(i)}})}}$,

where the estimate of ${\bf {R}}$ at the $i$th iteration is given by ${\bf {R}}^{(i)}={\bf {A}}{\bf {P}}^{(i)}{\bf {A}}^{H}+{\hat {\sigma }}^{(i)}{\bf {I}}$ with ${\bf {P}}^{(i)}={\mbox{Diag}}({\hat {p}}_{1}^{(i)},\cdots ,{\hat {p}}_{K}^{(i)})$.

Beyond scanning grid accuracy

The resolution of most power-based sparse source localization techniques is found to be limited by the fineness of the direction grid that covers the location parameter space. In the sparse signal recovery model, the sparsity of the truth signal $\mathbf {x} (n)$ is dependent on the distance between the adjacent element in the overcomplete dictionary ${\bf {A}}$, therefore, the difficulty of choosing the optimum overcomplete dictionary (i.e., particularly, the DOA scanning direction grid) arises. Since the computational complexity is 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, which refine the location estimates ${\boldsymbol {\bf {\theta }}}=(\theta _{1},\cdots ,\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.

A typical application with the SAMV algorithm in SISO Radar/Sonar Range-Doppler imaging problem. Since this imaging problem is essentially a single-snapshot application, only algorithms that work with single snapshot are included in this comparison, namely, Matched filter (MF, another alias of the Periodogram approach), IAA, SAMV-0. The simulation conditions are identical to : A $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$ dB power and the rest six are of $25$ dB power. The received signals are assumed to be contaminated with uniform white Gaussian noise of $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$ 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, which agree well with our previous comment on its sensitivity to SNR.

See also

• Matched filter
• Periodogram
• Array processing
• Pulse-Doppler radar
• MUltiple SIgnal Classification (MUSIC), a popular parametric superresolution method