SAMV (algorithm)

SAMV (iterative sparse asymptotic minimum variance) 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 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, 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 formula_1-element uniform linear array (ULA) receive formula_2 narrow band signals emitted from sources located at locations formula_3, respectively. The sensors in the ULA accumulates formula_4 snapshots over a specific time. The formula_5 dimensional snapshot vectors are
where formula_7 is the steering matrix, formula_8 contains the source waveforms, and formula_9 is the noise term. Assume that formula_10, where formula_11 is the Dirac delta and it equals to 1 only if formula_12 and 0 otherwise. Also assume that formula_9 and formula_14 are independent, and that formula_15, where formula_16. Let formula_17 be a vector containing the unknown signal powers and noise variance, formula_18.
The covariance matrix of formula_19 that contains all information about formula_20 is
This covariance matrix can be traditionally estimated by the sample covariance matrix formula_22 where formula_23. After applying the vectorization operator to the matrix formula_24, the obtained vector formula_25 is linearly related to the unknown parameter formula_20 as
formula_27,
where formula_28, formula_29, formula_30, formula_31, and let formula_32
where formula_33
is the Kronecker product.
SAMV algorithm.
To estimate the parameter formula_20 from the statistic formula_35, we develop a series of iterative SAMV approaches based on the asymptotically minimum variance criterion. From, the covariance matrix formula_36 of an arbitrary consistent estimator of formula_37 based on the second-order statistic formula_35 is bounded by the real symmetric positive definite matrix
where formula_40. In addition, this lower bound is attained by the covariance matrix of the asymptotic distribution of formula_41 obtained by minimizing,
where
formula_43
Therefore, the estimate of formula_20 can be obtained iteratively.
The formula_45 and formula_46 that minimize formula_47 can be computed as follows. Assume formula_48 and formula_49 have been approximated to a certain degree in the formula_50th iteration, they can be refined at the formula_51th iteration by,
where the estimate of formula_24 at the formula_50th iteration is given by formula_56 with formula_57.
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. In the sparse signal recovery model, the sparsity of the truth signal formula_58 is dependent on the distance between the adjacent element in the overcomplete dictionary formula_59, 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, which refine the location estimates formula_60 by iteratively minimizing a stochastic maximum likelihood cost function with respect to a single scalar parameter formula_61.
Application to range-Doppler imaging.
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, and a variant of the SAMV algorithm (SAMV-0). The simulation conditions are identical to: A formula_62-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 formula_63 dB power and the rest six are of formula_64 dB power. The received signals are assumed to be contaminated with uniform white Gaussian noise of formula_65 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 formula_63 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 formula_63 dB targets.
Open source implementation.
An open source MATLAB implementation of SAMV algorithm could be downloaded here.