PaperlayerView exact revision on arXiv

Source-linked AI summary

Grid-free compressive beamforming

Angeliki Xenaki, Peter Gerstoft

arXiv:1504.01662v1cs.ITmath.IT

TL;DR

Discrete-grid CS can degrade when source directions do not coincide with grid points. The paper formulates DOA estimation continuously and solves the resulting problem through a dual-domain semidefinite approach. Its reported results include high-resolution experimental reconstruction and performance with non-uniform arrays and single-snapshot data.

  • Problem

    When DOAs do not coincide with angular-grid directions, basis mismatch degrades CS reconstruction.

    Source: B. Basis Mismatch · p. 3

  • Method

    The paper avoids discretizing the continuous variable by solving the dual problem over a finite set of optimization variables using semidefinite programming.

    Source: B. Primal problem · p. 4, §X · p. 9

  • Results

    Grid-free CS provides high-resolution localization with further artifact reduction in the towed-array reconstruction, and retains high resolution when only one quarter of the sensors are kept in a non-uniform configuration.

    Source: §IX · p. 9

  • Takeaways & Limitations

    The paper reports high-resolution imaging with non-uniform arrays, noisy measurements, and single-snapshot data, including performance with coherent and moving sources.

    Source: §X · p. 9

    The sparse reconstruction requires a minimum separation condition to limit ill-posedness from highly coherent steering vectors.

    Source: §V · p. 6

Abstract

from arXiv · show

The direction-of-arrival (DOA) estimation problem involves the localization of a few sources from a limited number of observations on an array of sensors, thus it can be formulated as a sparse signal reconstruction problem and solved efficiently with compressive sensing (CS) to achieve high-resolution imaging. On a discrete angular grid, the CS reconstruction degrades due to basis mismatch when the DOAs do not coincide with the angular directions on the grid. To overcome this limitation, a continuous formulation of the DOA problem is employed and an optimization procedure is introduced, which promotes sparsity on a continuous optimization variable. The DOA estimation problem with infinitely many unknowns, i.e., source locations and amplitudes, is solved over a few optimization variables with semidefinite programming. The grid-free CS reconstruction provides high-resolution imaging even with non-uniform arrays, single-snapshot data and under noisy conditions as demonstrated on experimental towed array data.

I. INTRODUCTION

DOA estimation from limited array observations can be treated as sparse reconstruction, but discretized angular grids cause basis mismatch. The paper motivates grid-free CS and sets out the discrete model and sparse-reconstruction approach.

I. INTRODUCTION

  • Prior CS work reports high-resolution acoustic imaging and improved matched-field processing and passive fathometry in ocean acoustics.The cited applications include localization in complex environments and inference of sediment-layer interfaces.Source: §I · p. 1
  • When DOAs fall between grid directions, basis mismatch can cause spectral leakage and inaccurate estimates; finer grids reduce mismatch but increase computational complexity.The cost is especially relevant in large two- or three-dimensional problems.Source: §I · p. 1
  • Grid-free CS uses a continuous angular spectrum and atomic-norm sparsity, with semidefinite programming and polynomial rooting for DOA recovery.The introduction also reports high-resolution reconstruction with non-uniform arrays and noisy measurements, including experimental single-snapshot data.Source: §I · p. 1

II. DISCRETE DOA ESTIMATION

  • The discrete model assumes far-field, narrowband plane waves and known sound speed, then maps amplitudes on angular-grid directions to sensor measurements as y = Ax.The model includes additive noise.Source: §II · p. 2

A. Sparse signal reconstruction

  • Sparse reconstruction constrains the underdetermined problem; unlike the non-sparse minimum-ℓ2 solution, CS uses ℓ1 minimization, with a residual bound for noisy measurements.The cited CS equivalence result is stated for sufficiently sparse signals and sensing matrices with sufficiently incoherent columns.Source: A. Sparse signal reconstruction · p. 2

B. Basis Mismatch

A discrete angular grid can misrepresent off-grid sources and degrade CS reconstruction. The paper instead formulates source locations and amplitudes continuously, mapping that signal to array observations.

B. Basis Mismatch

  • When sources do not match the selected angular grid, the signal may not appear sparse in the chosen DFT basis, degrading CS reconstruction.Figure 1 varies source positions and grid spacing to illustrate the discretization setting.Source: B. Basis Mismatch · p. 3, Figure 1 · p. 3
  • Adaptive grid refinement can improve precision by refining detected source regions, but only a continuous formulation avoids basis mismatch, particularly for moving sources.Finer discretization also raises computational complexity.Source: B. Basis Mismatch · pp. 2–3

III. CONTINUOUS DOA ESTIMATION

  • The continuous model represents each source by a complex amplitude at a DOA on the sine spectrum and maps the resulting signal to sensor measurements through a linear operator.The measurement model also accommodates additive noise.Source: §III · p. 3

IV. GRID-FREE SPARSE RECONSTRUCTION

The reconstruction procedure promotes sparsity in a continuous optimization variable, using the atomic norm to formulate DOA estimation without discretizing that variable. The dual formulation connects the measurements to a bounded beamformed response across the angular spectrum.

IV. GRID-FREE SPARSE RECONSTRUCTION

  • The reconstruction procedure promotes sparsity directly on a continuous optimization variable.This addresses the underdetermined problem without imposing a discrete grid on that variable.Source: §IV · p. 3, B. Primal problem · p. 4

A. Atomic norm

  • The atomic norm is a convex sparsity measure for continuous signals that corresponds to the ℓ1-norm on a discrete grid.It extends the discrete formulation’s sparsity-promoting role to the continuous signal.Source: A. Atomic norm · p. 3

B. Primal problem

  • The primal formulation uses atomic-norm minimization to estimate the continuous signal, but is infinite dimensional and cannot be solved directly.Solving the dual avoids discretizing the continuous variable, whereas finer discretization would increase computational complexity.Source: B. Primal problem · p. 4

C. Dual problem

  • The dual selects a vector maximally aligned with the measurements while bounding its beamformed amplitude across the angular spectrum.At an existing source direction, the beamformed dual vector equals the normalized source amplitude; strong duality equates the primal minimum with the dual maximum.Source: C. Dual problem · p. 4

D. Dual problem using semidefinite programming

The dual problem reduces an infinite-unknown reconstruction to a finite set of optimization variables. Its infinitely many inequality constraints are handled through a bounded trigonometric polynomial and finite-dimensional linear matrix inequalities.

D. Dual problem using semidefinite programming

  • The dual problem initially has finitely many optimization variables but infinitely many inequality constraints, making it intractable.Its dual variables form a degree-(M − 1) trigonometric polynomial.Source: D. Dual problem using semidefinite… · p. 4
  • A uniform amplitude bound on the dual polynomial lets the inequality constraint be replaced by finite-dimensional linear matrix inequalities and solved by semidefinite programming.Source: D. Dual problem using semidefinite… · p. 4
  • The dual uses (M + 1)^2/2 optimization variables to solve a problem with infinitely many unknown parameters.That count is half the number of elements in the Hermitian matrix appearing in the inequality constraint.Source: D. Dual problem using semidefinite… · p. 4

E. Support detection through the dual polynomial

The dual polynomial identifies the source support through its unit-amplitude directions, which are recovered by rooting a nonnegative polynomial. Once support is found, the method recovers amplitudes and has a source-count bound, with an additional separation requirement for complex amplitudes.

E. Support detection through the dual polynomial

F. Reconstruction of the primal solution x

V. MAXIMUM RESOLVABLE DOAS

  • At most ⌊(M − 1)/2⌋ sources can be resolved; for M = 21, exceeding that bound yields inaccurate reconstruction, resolving only 7 of 11 sources.For positive amplitudes, the bound suffices for uniqueness; complex amplitudes additionally require minimum DOA separation, and violating it produces spurious sources.Source: §V · p. 6, Figure 4 · p. 6

VI. NON-UNIFORM ARRAYS

For non-uniform arrays, an added optimization constraint handles inactive sensors, and grid-free CS reconstructs sources despite degradation in CBF. With noisy measurements, the method estimates support and amplitudes, improving resolution while allowing some noise-related spurious sources.

VI. NON-UNIFORM ARRAYS

  • With 13 randomly selected sensors from a 21-sensor ULA, grid-free CS reconstructs the sources exactly while CBF degrades under stronger sidelobes.The example includes a strong source toward endfire.Source: §VI · p. 7, Figure 5 · p. 7

VII. GRID-FREE RECONSTRUCTION WITH NOISE

  • For noisy measurements, the method estimates the dual polynomial by semidefinite programming, recovers support, then estimates amplitudes; at 20 dB SNR it improves resolution over CBF but shows weak spurious sources.The noisy formulation bounds the measurement noise norm by ϵ and replaces infinite-dimensional constraints with finite matrix inequalities.Source: §VII · p. 7, Figure 6 · p. 7

VIII. DOA ESTIMATION WITH POLYNOMIAL ROOTING

Polynomial-rooting DOA methods derive spectra from the cross-spectral matrix and, for ULAs, can recover directions from roots on the unit circle. They require array regularity and, for robust cross-spectral estimates, many snapshots; eigendecomposition-based methods also have difficulty with coherent arrivals.

A. Spectral version of DOA estimation methods

  • MVDR, MUSIC, and minimum-norm methods use the cross-spectral matrix or its eigendecomposition, with spectra based on different beamforming or subspace criteria.MVDR minimizes output power while preserving the look-direction signal; MUSIC uses signal/noise-subspace orthogonality, and minimum-norm uses a vector in the noise subspace.Source: §VIII · p. 7, A. Spectral version of DOA estimation… · p. 8

B. Root version of DOA estimation methods

  • For a ULA, the null spectrum is a trigonometric polynomial, so its unit-circle roots can be used to estimate DOAs and then amplitudes.The root formulation applies to the MVDR and minimum-norm null spectra described here.Source: B. Root version of DOA estimation… · p. 8
  • Root-based methods require regular array geometry and many snapshots for robust cross-spectral estimates; eigendecomposition-based methods also fail to discern coherent arrivals without smoothing.Forward/backward smoothing can mitigate the coherent-arrival issue but still requires regular geometry and additional sensors.Source: B. Root version of DOA estimation… · p. 8

IX. EXPERIMENTAL RESULTS

The experiments show that grid-free CS retains high-resolution DOA imaging with non-uniform arrays and single-snapshot data, while the conclusion also reports robustness to noise and moving or coherent sources. The method uses a continuous formulation solved in the dual domain with semidefinite programming, then recovers DOAs by polynomial rooting.

IX. EXPERIMENTAL RESULTS

  • The experiment compares single-snapshot CS reconstructions with CBF, and the conclusion identifies robustness to noisy measurements as part of the method’s supported scope.The experimental data are from towed-array acoustic measurements in the North-East Pacific.Source: §IX · p. 8, §X · p. 9
  • With 16 non-uniform sensors, both discrete-grid and grid-free CS retain high-resolution DOA estimates without significant reconstruction degradation, unlike CBF.The comparison retains one quarter of the sensors; the two array configurations have the same aperture and resolution.Source: §IX · p. 9, Figure 7 · p. 9
  • Grid-free CS gives high resolution and further reduces artifacts over discrete-grid CS in the 64-sensor uniform-array comparison.The reported comparison attributes the additional artifact reduction to polynomial rooting.Source: Figure 7 · p. 9, §IX · p. 9

X. CONCLUSION

  • The continuous sparsity-promoting problem is solved in the dual domain by semidefinite programming, and DOAs are recovered through polynomial rooting.The conclusion states that the optimization handles infinitely many unknowns using a few optimization variables.Source: §X · p. 9
  • Grid-free CS provides high-resolution imaging with non-uniform arrays, noisy measurements, and single-snapshot data, including coherent or moving sources.The conclusion contrasts this scope with polynomial-rooting methods that require many snapshots and have degraded resolution for moving sources.Source: §X · p. 9

APPENDIX A: CONVEX OPTIMIZATION PROBLEMS

Appendix A reviews primal and dual formulations of convex optimization, including how the Lagrangian produces a concave dual function and a convex dual problem. It also defines the domain, feasible points, and optimal value used in these formulations.

1. Primal problem

  • A generic primal optimization problem minimizes an objective subject to inequality and equality constraints; its domain comprises points where the objective and constraints are defined.A point in the domain is feasible when it satisfies the constraints; convexity requires a convex objective and inequality functions with affine equality functions.Source: §1 · p. 10

2. The Lagrangian

  • The Lagrangian augments the objective with weighted constraint functions, using dual variables for the inequality and equality constraints.The inequality multipliers are λ and the equality multipliers are ν.Source: §2 · p. 10

3. The dual function

  • The dual function minimizes the Lagrangian over the primal variable and is concave in the dual variables, even when the primal problem is nonconvex.For nonnegative inequality multipliers, it provides lower bounds on the primal optimal value.Source: §3 · p. 10

4. Dual problem

  • The dual problem maximizes the dual function over feasible dual variables to obtain its best lower bound on the primal minimum.The dual problem is convex because its objective is concave and its constraints are convex.Source: §4 · p. 10

5. Weak duality

Weak duality makes the dual maximum a lower bound on the primal minimum, while Slater’s condition can establish equality for convex problems. The section also gives a Schur-complement criterion for positive semidefiniteness.

5. Weak duality

  • The dual maximum is a lower bound on the primal minimum, and their nonnegative difference is the duality gap.The weak-duality inequality holds even when the primal problem is nonconvex.Source: §5 · pp. 10–11

6. Slater’s condition and strong duality

  • For a convex problem, a strictly feasible point satisfies Slater’s condition and yields strong duality; with the stated weaker qualification, strong duality reduces to feasibility when constraints are linear.Under Slater’s condition, a dual-feasible point attains the primal optimal value.Source: §6 · p. 11

7. Schur complement

  • When the leading block A is positive definite, the partitioned matrix X is positive semidefinite exactly when its Schur complement S is positive semidefinite.The section defines the Schur complement for invertible A.Source: §7 · p. 11

APPENDIX B: BOUNDED TRIGONOMETRIC POLYNOMIALS

Appendix B reviews trigonometric polynomials and matrix conditions for nonnegative or uniformly bounded polynomial amplitudes. These results connect amplitude bounds to autocorrelation matrices and linear matrix inequalities.

1. Trigonometric polynomials

  • A trigonometric polynomial of degree L−1 is represented using the basis vector a(ω) and its coefficient vector h.The basis vector is defined over ω in [−π, π].Source: §1 · p. 11

2. Nonnegative trigonometric polynomials

  • The squared magnitude R(ω) = |H(ω)|2 is a nonnegative trigonometric polynomial whose coefficients can be calculated from the coefficient autocorrelation matrix.The coefficients are conjugate symmetric, so R(ω) is Hermitian.Source: §2 · p. 11

3. Bounded trigonometric polynomials

  • For bounded polynomials, the pointwise magnitude inequality implies an ordering of their coefficient autocorrelation matrices, expressible through a Schur complement.The appendix introduces this result as a relation between polynomial bounds and positive semidefinite matrix constraints.Source: §3 · p. 11
  • A pointwise bound |H(ω)| ≤ γ can be represented by two linear matrix inequalities for the uniformly bounded polynomial.The appendix relates bounds on maximum polynomial amplitude to the ℓ∞-norm.Source: §3 · p. 12

4. Roots of real nonnegative trigonometric polynomials

A bounded trigonometric polynomial yields a real nonnegative polynomial whose unit-circle roots are limited and correspond to points where |H(ω)| = 1. The appendices describe the implementation and the noisy dual formulation.

4. Roots of real nonnegative trigonometric polynomials

  • P(ω) has degree 2(L −1), at most L −1 distinct unit-circle roots, and each such root satisfies |H(ω)| = 1.The constructed polynomial is real-valued and nonnegative, so it cannot have single roots on the unit circle.Source: §4 · p. 12

APPENDIX C: IMPLEMENTATION IN MATLAB

APPENDIX D: DUAL PROBLEM WITH NOISE

  • For measurements contaminated by additive noise n satisfying ∥n∥2 ≤ ε, the primal atomic-norm minimization problem is reformulated as a dual problem, formulated by maximizing the dual function over dual variables c.Here c are dual variables for y − F_Mx − n = 0, and ξ ≥ 0 is the multiplier for ∥n∥2 − ε ≤ 0; the dual function is the infimum of L(x, c, ξ) over x. The optimal noise vector is n_o = c/(2ξ).Source: Appendix D · pp. 12–13
Loading 1504.01662v1…