A discretization-free sparse and parametric approach for linear array signal processing

Zai Yang; Lihua Xie; Cishen Zhang

Source-linked AI summary

A discretization-free sparse and parametric approach for linear array signal processing

Zai Yang, Lihua Xie, Cishen Zhang

arXiv:1312.7695v2Dec 30, 2013cs.IT

TL;DR

Sparse DOA methods commonly discretize the continuous direction range, introducing modeling and computational concerns. The paper proposes SPA, which combines covariance fitting with convex optimization to estimate sparse parameters without discretization. SPA is presented as statistically grounded, applicable to arbitrary snapshot counts, and robust to source correlation, with simulations demonstrating its performance against existing methods.

Problem
Existing sparse DOA methods approximate the continuous direction range with grids, which can introduce modeling error and increased computation from dense sampling.
Method
SPA uses SPICE covariance-fitting criteria, semidefinite programming, and postprocessing to estimate sparse source parameters continuously for uniform and sparse linear arrays.
Results
SPA guarantees a sparse discretization-free estimate, is a large-snapshot realization of maximum likelihood, and is statistically consistent under uncorrelated sources.
Takeaways & Limitations
SPA provides improved resolution, works with arbitrary snapshot numbers, is robust to correlated sources, and requires no user-parameters.

Abstract

from arXiv · show

Direction of arrival (DOA) estimation in array processing using uniform/sparse linear arrays is concerned in this paper. While sparse methods via approximate parameter discretization have been popular in the past decade, the discretization may cause problems, e.g., modeling error and increased computations due to dense sampling. In this paper, an exact discretization-free method, named as sparse and parametric approach (SPA), is proposed for uniform and sparse linear arrays. SPA carries out parameter estimation in the continuous range based on well-established covariance fitting criteria and convex optimization. It guarantees to produce a sparse parameter estimate without discretization required by existing sparse methods. Theoretical analysis shows that the SPA parameter estimator is a large-snapshot realization of the maximum likelihood estimator and is statistically consistent (in the number of snapshots) under uncorrelated sources. Other merits of SPA include improved resolution, applicability to arbitrary number of snapshots, robustness to correlation of the sources and no requirement of user-parameters. Numerical simulations are carried out to verify our analysis and demonstrate advantages of SPA compared to existing methods.

I. INTRODUCTION

DOA estimation is difficult because array snapshots depend nonlinearly on unknown directions, while existing parametric and sparse approaches impose practical limitations. The paper proposes SPA, a discretization-free covariance-fitting method for uniform and sparse linear arrays.

DOA estimation infers source directions from sensor-array snapshots whose dependence on the directions is nonlinear.
Parametric methods such as NLS require the source number and face nonconvex optimization that may prevent practically efficient global optimization.
MUSIC also requires the source number and has unreliable performance with few snapshots or correlated sources, whereas IAA is robust to correlation but suffers resolution limits in moderate or low SNR.
Sparse methods discretize the continuous direction range into grid points, but coarse grids create modeling error and dense grids increase computational burden.
SPA estimates parameters continuously using SPICE covariance-fitting criteria, semidefinite programming, and postprocessing, while guaranteeing a sparse parameter estimate without discretization.
The paper studies stochastic source signals and notes that its method is designed to remain robust when sources are correlated or coherent.

C. Uniform and Sparse Linear Arrays

The paper models uniform and sparse linear arrays through covariance fitting, exploiting Toeplitz structure to obtain convex semidefinite programs and then recover source parameters by postprocessing. The formulation accommodates singular sample covariance matrices and retains robustness to source correlation.

Uniform and Sparse Linear Arrays: A ULA uses uniformly spaced sensors, while an SLA is formed by selecting a subset of sensors from a corresponding ULA.
Uniform and Sparse Linear Arrays: An SLA’s coarray determines its source-detection capacity; redundancy arrays have ULA coarrays and can detect up to M −1 sources.
Covariance Fitting Criteria: The covariance-fitting formulation estimates the covariance matrix under Toeplitz and positive-semidefinite structure, with an SDP providing a convex optimization problem.
Covariance Fitting Criteria: The criteria have a large-snapshot maximum-likelihood connection and retain robustness to correlated sources through their covariance-fitting and ℓ1-related structure.
Covariance Fitting Criteria: Covariance parameterization contains diagonal redundancy, creating identifiability issues for u and σ even though covariance estimation itself is unaffected.
Covariance Fitting Criteria: For N ≥ M, the estimated covariance is bR = T(u∗)+diag(σ∗), obtained from the SDP solution.
Covariance Fitting Criteria: When N < M, the sample covariance is singular, so an alternative covariance-fitting criterion is used instead of the criterion requiring an invertible sample covariance.

2) The Case of N < M:

For N < M, the method uses an alternative criterion because the sample covariance is singular.

When N < M, the sample covariance becomes singular and the paper switches to an alternative covariance-fitting criterion.

C. SDP Formulations in the Case of Equal {σj}

For equal noise variances, the covariance model becomes Toeplitz and admits simplified semidefinite programs. Postprocessing then resolves nonuniqueness by enforcing a rank-deficient source component and enables unique sparse parameter recovery.

C. SDP Formulations in the Case of Equal {σj}: Equal noise variances make the noise covariance σI, giving the covariance R a Toeplitz structure.
C. SDP Formulations in the Case of Equal {σj}: The Toeplitz characterization removes diagonal redundancy and supports simplified SDP formulations with faster computations.
D. Postprocessing of bR: The SDP solution is postprocessed by decomposing the estimated covariance into a source component and a noise covariance estimate.
D. Postprocessing of bR: Because the decomposition is generally nonunique, SPA uses K ≤ M −1 to impose rank(T(bu)) ≤ M −1 on the source component.
D. Postprocessing of bR: The rank condition makes δ an eigenvalue of T(u*) and yields a unique decomposition through the minimum-eigenvalue construction.
D. Postprocessing of bR: Postprocessing separates sources and noise so the source covariance can be represented by as few sources as possible.
D. Postprocessing of bR: Without postprocessing, the final parameter estimate may be nonunique, lose statistical properties, and cease to be sparse.

E. Frequency and Power Solutions

SPA retrieves frequencies and powers from the postprocessed positive semidefinite Toeplitz matrix. A Vandermonde decomposition establishes uniqueness, while Prony’s method provides an efficient computational procedure.

E. Frequency and Power Solutions: A positive semidefinite Toeplitz matrix admits a Vandermonde decomposition into steering vectors weighted by positive source powers.
E. Frequency and Power Solutions: The decomposition is unique up to permutation when its rank is at most M −1, so bθ and bp are uniquely determined from T(bu).
E. Frequency and Power Solutions: The noise covariance estimate bσ is obtained from the diagonal of bR after removing the source contribution.
E. Frequency and Power Solutions: Prony’s method solves the resulting linear system by obtaining bθ from polynomial zeros and then solving for bp.
E. Frequency and Power Solutions: Algorithm 1 estimates covariance by SDP, postprocesses bR, and then computes frequencies and powers using Prony’s method.
E. Frequency and Power Solutions: SPA does not generally determine the true source count and can return spurious sources because source number and noise variances are not assumed known.

IV. SPA WITH AN SLA

SPA extends to sparse linear arrays by representing their covariance through coarray-induced Toeplitz structure and solving analogous covariance-fitting SDPs. Redundancy arrays permit the same source-count bound as ULAs, while non-redundancy arrays leave information unused.

IV. SPA WITH AN SLA: For an SLA, the steering matrix, snapshots, covariance matrix, and sample covariance are defined analogously to the ULA model.
IV. SPA WITH AN SLA: The SLA steering matrix factors through the ULA steering matrix, allowing the covariance to be expressed as TΩ(u) from Toeplitz parameters.
IV. SPA WITH AN SLA: The entries of TΩ(u) are specified by the coarray, and for redundancy arrays the mapping between T(u) and TΩ(u) is one-to-one.
IV. SPA WITH AN SLA: For the redundancy SLA Ω = {1, 2, 5, 7}, the parameter vector u has length 7 and TΩ(u) is constructed from the coarray mapping.
IV. SPA WITH AN SLA: Analogous covariance-fitting SDPs are formulated under T(u) ≥ 0 and σΩ ⪰ 0, with separate cases depending on whether N ≥ L.
IV. SPA WITH AN SLA: With equal noise variances, the SLA covariance is characterized by ΓΩT(u)ΓΩ^T and similar SDPs follow by setting σΩ = 0.
IV. SPA WITH AN SLA: The SLA SDP solution has the same identifiability issue as the ULA case and is resolved by enforcing rank(T(bu)) ≤ M −1.
IV. SPA WITH AN SLA: For non-redundancy SLAs, the implementation uses only information up to K ≤ M −1, leaving the array’s additional detectable-source information for future work.

V. PROPERTIES OF SPA

SPA is explicitly sparse and parametric: it estimates parameters continuously through reparameterization, with a frequency estimate containing at most M −1 components.

V. PROPERTIES OF SPA: SPA is parametric because it performs optimization by reparameterization rather than parameter discretization.
V. PROPERTIES OF SPA: SPA is sparse because its frequency estimator has length at most M −1.
V. PROPERTIES OF SPA: Theorem 1 formally states that the length of SPA’s frequency estimator bθ is maximally M −1.

B. Statistical Properties

SPA is statistically consistent under uncorrelated-source assumptions and asymptotically attains maximum-likelihood properties, including efficiency under stated regularity conditions.

SPA resolves its estimator-dimension issue by expanding the true parameter and estimator to a common dimension, with virtual zero-power sources preserving physical equivalence.The method effectively assumes the worst-case dimension K = M − 1 while retaining the knowledge K ≤ M − 1.
Under uncorrelated source and noise assumptions, SPA is statistically consistent as the snapshot count N increases.As N approaches infinity, the estimated covariance converges to the true covariance, yielding the unique true parameter estimate when K ≤ M − 1.
SPA is asymptotically a maximum-likelihood estimator under the paper’s Gaussian and array assumptions.The result follows by relating the covariance-fitting optimization to the global minimizer of the ML criterion for i.i.d. Gaussian snapshots.
Under K = M − 1 with strictly positive source powers and noise variances, SPA is statistically asymptotically efficient.This conclusion is obtained from the asymptotic ML and consistency results.
The estimator is asymptotically normal with asymptotically unbiased mean and covariance equal to the inverse Fisher information matrix.The covariance F −1 is identified with the Cramér–Rao lower bound.

VI. CONNECTION TO PRIOR ARTS

SPA shares SPICE’s covariance-fitting foundation but removes grid approximation, on-grid restrictions, and associated identifiability issues through continuous parametric estimation and postprocessing.

Connection to SPICE: SPICE is a discretized approximation of SPA that represents the continuous frequency range using a finite sampling grid.Its covariance is linear in the discretized power vector and noise variances, enabling convex covariance fitting.
Connection to SPICE: Grid modeling error can make SPICE inaccurate because true frequencies are not guaranteed to lie on the discretization grid.Increasing grid density can reduce this error but increases computational cost.
Connection to SPICE: SPICE can suffer on-grid, identifiability, and nonsparsity problems, whereas SPA estimates continuous parameters and guarantees a sparse estimate.The SPICE power support may be as large as the grid dimension.
Computational comparison: SPA’s computational order in array dimensions is higher than SPICE’s, but it does not depend on SPICE’s grid size eN.With dense grids, SPA can therefore be faster than SPICE; the comparison depends on the selected grid density and implementation.

B. Proposed SPICE-PP

SPICE-PP augments SPICE with covariance postprocessing so its parameter estimates are no longer restricted to the discretization grid.

SPICE-PP estimates covariance using original SPICE, then decomposes it and obtains parameters through Vandermonde decomposition.The procedure has three stages: covariance estimation, postprocessing, and parameter recovery.
The postprocessing removes the grid constraint from SPICE-PP frequency estimates.This addresses the on-grid issue while retaining the underlying SPICE covariance-fitting step.
The postprocessing technique can potentially be applied to other covariance-based methods.

C. Connection to Existing Discretization-Free Methods in the Case of N = 1

SPA also applies to single-snapshot array processing, which is mathematically equivalent to spectral analysis, while the simulations compare it with several existing DOA methods.

Connection to Existing Discretization-Free Methods in the Case of N = 1: When N = 1, array processing is mathematically equivalent to spectral analysis, linking SPA to recent atomic-norm discretization-free methods.Those methods use continuous counterparts of ℓ1-norm minimization, whereas SPA is developed primarily for multisnapshot array processing.
Simulation setup: The simulations compare SPA with SPICE, SPICE-PP, IAA, MUSIC, and OGSBI-SVD under known and unknown source-number settings.MUSIC requires the source number; the other listed methods do not.
Spectra comparisons: For uncorrelated sources, SPA always produces a sparse spectrum across tested snapshot and SNR settings, while competing methods can become dense or lose resolution.At N = 200, IAA cannot separate the first two sources at low SNR, and SPICE variants can become dense because of identifiability issues.
Spectra comparisons: With N approaching infinity and SNR = −20 dB, SPA exactly localizes the three sources, whereas SPICE variants retain resolution or modeling-error problems.The experiment uses the true covariance matrix and supports SPA’s consistency conclusion.
Spectra comparisons: SPA remains applicable with small or single snapshots, including a case where MUSIC fails.
Spectra comparisons: For coherent sources, SPA has consistently good performance, while MUSIC and SPICE can miss coherent sources and IAA has low resolution.The coherent-source setup makes source 3 an exact replica of source 1; SPA power estimates are attenuated in this case.

C. Quantitative Comparisons with SPICE

Quantitative experiments compare discretization-free SPA with discretized SPICE on ULA frequency estimation and computational cost. SPA improves with SNR toward the CRLB and avoids SPICE’s grid-dependent runtime and error floor.

C. Quantitative Comparisons with SPICE: The experiments evaluate MSE and CPU time for SPA and SPICE under multiple discretization levels, using ULA frequency estimates averaged over Monte Carlo runs.The CRLB is included as a benchmark, although computing it requires the source number, which SPA and SPICE do not use.
C. Quantitative Comparisons with SPICE: SPICE’s off-grid frequency choices impose an SNR-independent MSE lower bound of 1/(9 eN^2) for the specified source locations.The bound follows because each true frequency lies one-third of a grid interval from its nearest grid point.
C. Quantitative Comparisons with SPICE: SPA MSEs improve steadily with SNR and gradually approach the CRLBs, whereas SPICE remains bounded by discretization error at high SNR.The same performance trends hold for equal and different noise variances; SPICE postprocessing helps in some regimes but cannot remove the high-SNR modeling error.
C. Quantitative Comparisons with SPICE: SPICE runtime grows with grid size eN, while discretization-free SPA does not depend on eN.At eN = 1000, SPICE+ and SPICE are consistently slower than SPA+ and SPA, respectively.
C. Quantitative Comparisons with SPICE: With array length M varying at SNR = 10dB, SPA+ scales well and is faster than SPICE3+ for M ≤30 and consistently faster than SPICE3.SPA without the plus postprocessing was evaluated only for M ≤20 because of computational time considerations.

2) The SLA Case:

The SLA and OGSBI-SVD experiments test SPA with many sources, varying snapshots, and off-grid competitors. SPA approaches its asymptotic benchmark as snapshots increase, while retaining favorable accuracy and robustness across comparisons.

2) The SLA Case:: The SPA+ frequency and power estimates for the six-source SLA case are visualized at N = 200 and SNR = 10dB, with black circles marking the true values.The plot summarizes 1000 Monte Carlo runs.
2) The SLA Case:: For N ≥200, SPA and SPA+ can outperform their corresponding CRLB benchmarks in the reported CRLB/MSE ratios, with the gap narrowing as N increases.The ratios are larger than 1 for SPA+ or 0.9281 for SPA, and the gap approaches the asymptotic values predicted by the theorem.
D. Comparison With OGSBI-SVD: Against OGSBI-SVD, SPA becomes more accurate at high SNR when OGSBI-SVD’s first-order modeling error becomes nonnegligible.SPA is slightly slower with eN = 100 but about three times faster with eN = 200, and it remains satisfactory at SNR = −10dB where OGSBI-SVD does not.
D. Comparison With OGSBI-SVD: Across N = 1 to 200 at SNR = 10dB, SPA MSEs are less than 1.5 times OGSBI-SVD MSEs in most scenarios, and the gap vanishes as N increases.The comparison is attributed to both methods’ connection with maximum-likelihood estimation in different snapshot regimes.
E. Discussion: Resolution vs. Robustness: SPA and infinitely finely discretized SPICE can yield the same covariance estimate, but SPA always has a sparse spectrum whereas SPICE may produce a dense one.The dense SPICE decomposition can have inferior resolution, although SPICE may achieve lower MSE in the middle SNR range.