PaperlayerView exact revision on arXiv

Source-linked AI summary

Gridless DOA Estimation and Root-MUSIC for Non-Uniform Arrays

Mark Wagner, Yongsung Park, Peter Gerstoft

arXiv:2003.04457v1eess.SP

TL;DR

Gridless DOA and root-MUSIC traditionally require ULA measurements because their Vandermonde and Toeplitz foundations do not directly apply to NUAs. The paper introduces irregular Toeplitz matrices and irregular Vandermonde decomposition, then solves the resulting NUA gridless problem with alternating projections. Simulations report robust, high-resolution NUA performance and similar ULA performance to ADMM, with advantages over gridded methods at high SNR.

  • Problem

    Gridless DOA and root-MUSIC are traditionally limited to ULA measurements because they rely on Toeplitz covariance structure and Vandermonde decomposition.

  • Method

    The paper generalizes these methods to NUAs using irregular Toeplitz matrices, irregular Vandermonde decomposition, and alternating projections for the resulting non-convex optimization.

  • Results

    AP gridless is robust to noise, high resolution, and superior to grid-based techniques at high SNR, while achieving similar ULA performance to ADMM.

  • Takeaways & Limitations

    Irregular Vandermonde decomposition extends gridless DOA and root-MUSIC directly to NUA measurements without interpolation.

Abstract

from arXiv · show

The problem of gridless direction of arrival (DOA) estimation is addressed in the non-uniform array (NUA) case. Traditionally, gridless DOA estimation and root-MUSIC are only applicable for measurements from a uniform linear array (ULA). This is because the sample covariance matrix of ULA measurements has Toeplitz structure, and both algorithms are based on the Vandermonde decomposition of a Toeplitz matrix. The Vandermonde decomposition breaks a Toeplitz matrix into its harmonic components, from which the DOAs are estimated. First, we present the `irregular' Toeplitz matrix and irregular Vandermonde decomposition (IVD), which generalizes the Vandermonde decomposition to apply to a more general set of matrices. It is shown that the IVD is related to the MUSIC and root-MUSIC algorithms. Next, gridless DOA is generalized to the NUA case using IVD. The resulting non-convex optimization problem is solved using alternating projections (AP). A numerical analysis is performed on the AP based solution which shows that the generalization to NUAs has similar performance to traditional gridless DOA.

I. INTRODUCTION

Gridless DOA avoids grid mismatch but traditionally relies on Toeplitz structure from uniformly sampled measurements. This paper extends the framework to NUAs using irregular matrix decompositions and an alternating-projections solver.

  • Motivation: Gridless methods use atomic-norm sparsity to estimate continuous DOAs without restricting candidates to a predefined grid.They are the continuous analog of gridded compressive DOA and address errors caused by grid mismatch.
  • Existing gridless DOA: CCS formulates gridless DOA as finding a lowest-rank Toeplitz matrix that explains the measurements, then recovers frequencies through Vandermonde decomposition.The decomposition parameters correspond to the signal frequencies and, in DOA estimation, to the DOAs.
  • Existing gridless DOA: Traditional gridless DOA and root-MUSIC are limited to regularly sampled measurements from uniform linear arrays.Their limitation follows from the Toeplitz and Vandermonde structure available for ULAs.
  • NUA extensions: Prior NUA extensions commonly interpolate the NUA manifold to a ULA manifold, but interpolation can be inaccurate across the full array field of view.Such methods may require interpolation over multiple sectors of the array manifold.
  • Contributions: The paper introduces irregular Toeplitz matrices and irregular Vandermonde decomposition to extend gridless DOA and root-MUSIC directly to NUA measurements without interpolation.The DOAs are recovered from the irregular Vandermonde components of the irregular Toeplitz matrix.
  • Optimization: The NUA extension is non-convex, so the proposed solution uses alternating projections rather than an easily unavailable convex relaxation.Alternating projections iteratively projects an initial estimate between two or more sets.

II. BACKGROUND: DOA ESTIMATION FOR ULAS

The measurement model considers narrowband far-field sources observed by sensors at known line positions. ULA sensor positions produce steering matrices with Vandermonde structure, enabling Toeplitz covariance decomposition.

  • Model framework: The model contains M sensors, K uncorrelated far-field narrowband sources, L snapshots, and Gaussian measurement noise.Source angles are represented by θ, while sensor positions are collected in r and measured in half-wavelength units.
  • Model framework: The array steering matrix models the phase pattern across sensors for each arrival angle, and the goal is to recover the angles from sensor positions and measurements.Its columns are steering vectors defined over the angular field of view.
  • Vandermonde structure: A ULA has sensor positions given by scaled and shifted integer locations, with half-wavelength spacing corresponding to α = 1 and β = 0.Under this geometry, the steering matrix has Vandermonde structure.
  • Toeplitz decomposition: A Hermitian symmetric Toeplitz matrix is parameterized by its first column and can be decomposed into Vandermonde components.The decomposition is unique when the Toeplitz matrix is not full rank.

C. Root-MUSIC and Vandermonde Decoposition

Root-MUSIC estimates DOAs from the roots of a polynomial formed from the ULA sample covariance matrix. Its decomposition and root structure rely on the signal and noise subspaces associated with the covariance matrix.

  • Root-MUSIC: Root-MUSIC forms a polynomial from the ULA sample covariance matrix and maps selected complex roots to DOA estimates.In the noiseless case, the roots are the Vandermonde-decomposition parameters, and the method is valid only for ULA measurements.
  • Subspaces: The sample covariance matrix separates signal and noise subspaces through eigendecomposition, with the latter approximated when measurement noise is present.At least K snapshots are required to form a rank-K approximation and estimate both subspaces.
  • Null spectrum: For a ULA, steering vectors can be represented by Vandermonde columns, allowing the noise-subspace null spectrum to be expanded as a polynomial in z.The polynomial structure enables efficient root calculation.
  • Root selection: Root-MUSIC selects the K roots inside the unit circle with largest magnitude and converts them to DOA estimates.With noise, estimate accuracy depends on how well the true noise subspace is approximated.
  • Caveat: The null-spectrum polynomial uses roots off the unit circle as estimates even though the spectrum was derived only on the unit circle.The paper characterizes this as a mathematical trick rather than a physically meaningful step.
  • Vandermonde connection: In the noise-free case, the covariance matrix has rank K and Toeplitz structure, while its K double roots lie on the unit circle and encode the Vandermonde parameters.With noise, root-MUSIC approximates the parameters of a noisy Toeplitz matrix.

D. Gridless DOA for Uniform Linear Arrays

Gridless DOA minimizes the number of continuous steering-vector atoms explaining the measurements. For ULAs, this becomes a rank-constrained Toeplitz optimization whose solution yields DOAs through Vandermonde decomposition or root-MUSIC.

  • Atomic formulation: Gridless DOA estimates the DOAs by minimizing the atomic ℓ0 norm of atoms generated by the array-steering manifold.The atoms are rank-one matrices constructed from steering vectors over all possible angles.
  • Atomic formulation: The atomic formulation represents the noiseless signal as a linear combination of a small number of constrained rank-one atoms.The number of atoms corresponds to the sparse signal representation over the continuous angle manifold.
  • ULA optimization: For a ULA, the steering matrix is Vandermonde and the atomic ℓ0 problem becomes a rank-constrained optimization over a positive semidefinite Toeplitz matrix.The Toeplitz matrix captures the low-rank covariance structure needed for recovery.
  • DOA recovery: After optimizing the Toeplitz matrix, the DOAs are recovered using Vandermonde decomposition or root-MUSIC.Thus the optimization estimates a full-rank covariance matrix from a single snapshot by exploiting low-rank Toeplitz structure.
  • Convex relaxation: The rank minimization problem is non-convex and is commonly replaced by a trace-based semidefinite-program relaxation solvable with general optimization methods.ADMM is provided as a solver for the relaxed formulation.

III. EXTENSION TO NON-UNIFORM ARRAY GEOMETRIES

The paper generalizes Vandermonde and Toeplitz structure to irregular sensor positions, enabling root-MUSIC and gridless DOA estimation for non-uniform arrays.

  • III. EXTENSION TO NON-UNIFORM ARRAY GEOMETRIES: Irregular Toeplitz matrices are constructed from irregular Vandermonde components and can be decomposed back into those components through IVD.The decomposition interprets sensor locations as sampling positions of a spectrally sparse signal whose frequencies relate to DOAs.
  • III. EXTENSION TO NON-UNIFORM ARRAY GEOMETRIES: Irregular Vandermonde matrices incorporate sensor positions into harmonic components associated with NUA measurements.The additional sensor-position vector distinguishes IVD from the conventional Vandermonde decomposition.
  • III. EXTENSION TO NON-UNIFORM ARRAY GEOMETRIES: For NUA geometries, the irregular null spectrum can be discontinuous at ∠z = π because the array manifold differs at the extreme DOAs.The paper contrasts this behavior with exceptional half-wavelength-spaced ULA geometry.
  • III. EXTENSION TO NON-UNIFORM ARRAY GEOMETRIES: The irregular null spectrum no longer has an easily rootable polynomial form, so DOA estimates are obtained from local minima evaluated on the unit circle.The selected minima correspond to arguments of roots near the unit circle and provide DOA estimates through the stated mapping.
  • III. EXTENSION TO NON-UNIFORM ARRAY GEOMETRIES: When the matrix belongs to the irregular Toeplitz set, all roots of interest lie on the unit circle and the spectrum reconstructs the irregular Vandermonde matrix.The source powers are then recovered from the resulting decomposition.

C. Irregular Toeplitz Structure

The irregular Toeplitz structure extends the diagonal-invariant structure of ULA covariance matrices to sensor locations with nonuniform pairwise differences.

  • C. Irregular Toeplitz Structure: For ULA sensors, repeated position differences along diagonals produce the conventional Toeplitz structure.For NUAs, covariance entries instead sample complex exponentials at elements of the sensor-position distance matrix.
  • C. Irregular Toeplitz Structure: The irregular Toeplitz set is convex for any sensor-position vector γ.Convex combinations of matrices generated by irregular Vandermonde components remain in the same set.

D. IVD and Irregular Root-MUSIC

IVD provides the decomposition needed for irregular root-MUSIC and NUA gridless DOA, while alternating projections solve the resulting non-convex formulation.

  • D. IVD and Irregular Root-MUSIC: IVD is presented as a computationally efficient extension of root-MUSIC to NUA measurements.It takes sensor positions, noise-subspace dimension, and a matrix as inputs, returning harmonics and source-power weights.
  • D. IVD and Irregular Root-MUSIC: Irregular root-MUSIC estimates DOAs directly from NUA measurements using the IVD framework.Accurate noise-subspace estimation requires at least as many snapshots as DOAs, L ≥ K.
  • D. IVD and Irregular Root-MUSIC: The NUA gridless DOA problem is formulated using rank-constrained irregular Toeplitz matrices and recovers DOAs and source powers through IVD.The formulation modifies the gridless DOA optimization so its solution belongs to the irregular Toeplitz set.

1) Projection to the Toeplitz Set:

The projection framework constructs approximate irregular Toeplitz matrices from unit-circle minima, while enforcing positive semidefiniteness through eigenvalue projection.

  • 1) Projection to the Toeplitz Set:: ULA Toeplitz projection replaces entries along each diagonal with their mean.This is the regular-array counterpart of projection onto the irregular Toeplitz set.
  • 1) Projection to the Toeplitz Set:: Projection onto the rank-constrained irregular Toeplitz set uses approximate parameters obtained from local minima of the irregular null spectrum on the unit circle.The corresponding source-power matrix is then estimated and used to reconstruct a matrix in the desired set.
  • 1) Projection to the Toeplitz Set:: The positive-semidefinite projection is defined through the eigendecomposition of the input matrix.The positive-semidefinite matrix set forms a convex cone.

C. Alternating Projections for NUA Gridless DOA

The paper solves the non-convex NUA gridless DOA problem with alternating projections between positive-semidefinite and structured rank-constrained sets. Upon convergence, irregular Vandermonde decomposition retrieves DOAs, while convergence and global optimality remain limited by non-convexity and initialization.

  • Alternating projections: Alternating projections iteratively project an estimate between the positive-semidefinite set and the structured rank-constrained set.The rank-constrained set is non-convex, so convergence is not generally guaranteed.
  • DOA recovery: After convergence, irregular Vandermonde decomposition of the upper-left matrix subblock retrieves the DOAs, defining the method called AP gridless.The algorithm is initialized with an arbitrary estimate and iterates until a stopping criterion is met.
  • Assumptions: AP gridless requires prior knowledge of the number of sources K, or a search over K values to select the sparsest adequate reconstruction.Source-number estimation methods can alternatively be used to estimate K.
  • ULA comparison: AP ULA replaces the irregular Toeplitz projection with a Toeplitz projection and is restricted to uniform linear-array measurements.This provides the ULA counterpart used in the numerical comparisons.
  • Convergence limitations: Convergence to a global minimum is guaranteed only when initialization is sufficiently close to the global minimizer; otherwise, convergence may reach a local minimum.The paper therefore leaves accuracy analysis to numerical simulation.
  • Numerical evaluation: Figure 4 evaluates RMSE versus SNR for AP Gridless, AP ULA, ADMM, SBL, and LASSO over 250 trials of high-SNR single-snapshot measurements.The experiments use M = 20, K = 3, and L = 1, with all algorithms run to convergence.

V. SIMULATION

Simulations compare AP gridless with ULA, NUA, gridded, and subspace methods across noise, array size, snapshots, and source separation. AP gridless performs strongly for NUAs, while its resolution depends on snapshot quality and source coherence.

  • AP gridless maintains excellent high-SNR performance for NUA measurements and outperforms gridded techniques except at low SNR, where LASSO can be similar.
  • In low-SNR multi-snapshot ULA measurements, AP gridless and AP ULA perform slightly worse than ADMM, suggesting greater noise robustness for ADMM.
  • Irregular root-MUSIC nearly matches AP gridless for multi-snapshot NUA measurements at lower computational cost.
  • When L ≥ K, root-MUSIC and irregular root-MUSIC match gridless methods with reduced computational cost, eliminating the benefit of gridless techniques in that regime.
  • AP gridless struggles to resolve nearby DOAs for single snapshots and coherent sources, whereas it is exact with incoherent sources when the noise subspace is accurately estimated.
  • The irregular Toeplitz projection is AP gridless’s computational bottleneck because it requires a spectral search over the irregular null spectrum.

VI. CONCLUSION

The paper introduces irregular Vandermonde decomposition for irregularly sampled signals and uses it to extend gridless DOA and root-MUSIC to NUAs. An alternating-projections solver provides a non-convex implementation with strong simulated performance.

  • Irregular Vandermonde decomposition generalizes Vandermonde decomposition to irregularly sampled signals and decomposes covariance matrices into harmonic components.
  • The decomposition extends both gridless DOA and root-MUSIC from ULAs to NUAs by operating directly on irregular Toeplitz representations.
  • AP gridless solves the non-convex NUA gridless DOA problem, matches ADMM on ULAs, and is robust, high-resolution, and superior to grid-based methods at high SNR.

APPENDIX A ADMM FOR GRIDLESS DOA

Appendix A formulates ADMM for multiple-snapshot ULA gridless DOA by relaxing rank minimization and iteratively updating constrained variables. Its updates include Toeplitz, measurement, and positive-semidefinite projections.

  • ADMM is applied after replacing the non-convex rank-minimization problem with a convex relaxation.
  • The formulation uses the measurement matrix Y, a Toeplitz matrix T(u), auxiliary matrix Q, and user-defined parameter τ.
  • ADMM iteratively optimizes each variable independently, with closed-form updates for Q, u, and the estimated measurement matrix.
  • The S update projects onto the positive-semidefinite cone, while T^-1 returns the first column of the nearest Toeplitz matrix.
  • For convex problems, ADMM is known to converge at a linear rate.
Loading 2003.04457v1…