PaperlayerView exact revision on arXiv

Source-linked AI summary

Joint Sparse Recovery Method for Compressed Sensing with Structured Dictionary Mismatches

Zhao Tan, Peng Yang, Arye Nehorai

arXiv:1309.0858v3cs.IT

TL;DR

Compressed sensing dictionaries can be mismatched in applications such as off-grid DOA estimation, motivating recovery methods that account for structured column perturbations. The paper uses joint-sparse recovery with analytical error bounds and fast first-order algorithms, and reports improved reconstruction and DOA accuracy in passive and active sensing.

  • Problem

    Traditional compressed sensing assumes a known dictionary, but real applications involve structured dictionary mismatches, including off-grid effects in DOA estimation.

  • Method

    The paper jointly recovers the sparse signal and mismatch variables, derives a performance bound, and implements fast first-order algorithms.

  • Results

    Numerical examples show better reconstruction results than existing methods and improved DOA estimation accuracy in passive and active sensing.

  • Takeaways & Limitations

    Joint sparse recovery provides a practical framework for compressed sensing with structured mismatches and off-grid DOA targets.

Abstract

from arXiv · show

In traditional compressed sensing theory, the dictionary matrix is given a priori, whereas in real applications this matrix suffers from random noise and fluctuations. In this paper we consider a signal model where each column in the dictionary matrix is affected by a structured noise. This formulation is common in direction-of-arrival (DOA) estimation of off-grid targets, encountered in both radar systems and array processing. We propose to use joint sparse signal recovery to solve the compressed sensing problem with structured dictionary mismatches and also give an analytical performance bound on this joint sparse recovery. We show that, under mild conditions, the reconstruction error of the original sparse signal is bounded by both the sparsity and the noise level in the measurement model. Moreover, we implement fast first-order algorithms to speed up the computing process. Numerical examples demonstrate the good performance of the proposed algorithm, and also show that the joint-sparse recovery method yields a better reconstruction result than existing methods. By implementing the joint sparse recovery method, the accuracy and efficiency of DOA estimation are improved in both passive and active sensing cases.

I. INTRODUCTION

The paper addresses compressed sensing when dictionary columns have structured mismatches, using joint sparsity to recover the signal and mismatch variables. It develops performance guarantees, fast first-order algorithms, and DOA applications for off-grid targets.

  • Problem formulation: Real applications may provide an imperfect dictionary, modeled as D = A + E with known A and unknown E.The paper focuses on structured column mismatches of the form d_i = a_i + β_i b_i.
  • Algorithms: FISTA is implemented for bounded and unbounded mismatch parameters to improve efficiency on large-dimensional problems.The paper contrasts this first-order approach with slower interior-point methods.
  • Proposed approach: Joint sparsity models the signal and mismatch variables as sharing the same support, with nonzero terms occurring in pairs.This structure is exploited through a joint-sparse recovery formulation.
  • Theory: The method provides a performance guarantee when the sensing matrix A and mismatch matrix B satisfy certain constraints.The paper analyzes reconstruction error for the joint-sparse recovery method.
  • DOA applications: The framework is extended to passive and active DOA estimation with off-grid targets, where discretization can substantially degrade compressed-sensing performance.The method exploits first-order sensing-model derivatives and joint sparsity between the original signal and mismatch parameters.
  • Evaluation: Numerical examples report that the proposed method outperforms existing compressed-sensing methods for structured dictionary mismatches.The paper applies the approach to passive and active sensing scenarios.

II. GENERAL STRUCTURED DICTIONARY MISMATCHES MODEL

The paper reformulates structured dictionary mismatch recovery as a joint-sparse optimization over the signal and mismatch-induced variables. It derives recovery guarantees under joint-RIP conditions and relates reconstruction error to measurement noise.

  • Joint-sparse formulation: The mismatch model introduces p = β ⊙s and x = [s^T, p^T]^T, making the signal and mismatch components jointly sparse.Because p_i is zero whenever s_i is zero, both components share a support set.
  • Recovery theory: Theorem II.1 gives exact recovery under a joint restricted isometry condition for the noiseless model.The theorem assumes x = [s^T, p^T]^T with p = s ⊙β and s having at most K nonzero terms.
  • Optimization: The original non-convex recovery problem is relaxed using the mixed ℓ2/ℓ1 norm.The resulting formulation is equivalent to the constrained joint-sparse problem for an appropriate regularization parameter.
  • Noisy recovery: With measurement noise, the recovery theorem assumes σ2K < 0.1907 and ∥Φ^T w∥∞,1 ≤ λ.The resulting bound depends on the best K joint-sparse approximation and constants determined by σ2K.
  • Error interpretation: For a K-sparse signal, p = β ⊙s makes x joint K-sparse, so the approximation term vanishes and error depends only on the noise level characterized by λ.The paper separately discusses obtaining an error bound for the original signal s.
  • Mismatch recovery: The mismatch parameters can be recovered either by taking β̂_i = p̂_i/ŝ_i or by solving the original optimization after recovering ŝ.The first route uses the joint-sparse optimization solution directly.

III. DOA ESTIMATION WITH OFF-GRID TARGETS

The paper models off-grid DOA targets by augmenting a discretized sensing model with first-order mismatch terms. Joint-sparse recovery estimates both the original signal and grid mismatch, while bounded mismatch constraints and fast optimization address practical computation.

  • Grid model: Traditional DOA compressed sensing discretizes the region of interest into a grid, assigning signal coefficients to grid locations matching target parameters.The grid uses step size 2r, and the model is exact only when targets lie on grid points.
  • Off-grid mismatch: Off-grid targets create modeling error that deteriorates reconstruction accuracy when actual parameters do not coincide with grid points.The paper identifies this mismatch as a central limitation of the traditional model.
  • Mismatch model: A first-order Taylor expansion represents off-grid effects through a mismatch parameter β = ϕ − θ.The model assumes target locations are within r of grid points and separated by more than 2r.
  • Recovery: The original signal and grid mismatch are estimated by solving the joint-sparse optimization problem.The formulation sets p = β ⊙s and penalizes the joint sparsity of s and p.
  • Constraints and computation: Because β lies in [−r, r], the off-grid formulation can incorporate an additional bounded constraint.For sufficiently large problems, the paper uses a fast algorithm to reduce computational burden.

B. Merging Process for Representation Ambiguity

Grid mismatch can create ambiguous duplicate DOA estimates near interval midpoints, so the method merges nearby recovered components into one interpolated target. The paper also uses FISTA-based first-order optimization, with smoothing and continuation to balance approximation accuracy and convergence speed.

  • Representation ambiguity: Targets near an interval midpoint can produce two nonzero reconstructed terms because measurement noise creates representation ambiguity.The ambiguity arises when the true DOA is near the midpoint between adjacent grid points.
  • Merging process: The method linearly interpolates and merges two recovered DOAs within one interval into a single target.The merged magnitude is s = sa + sb, and the DOA is weighted by the recovered magnitudes.
  • FISTA implementation: FISTA is introduced as a proximal first-order method to reduce the computational cost of solving the joint-sparse problems.The bounded formulation requires additional handling because of its convex constraints.
  • FISTA implementation: The bounded formulation is smoothed by approximating the ℓ2,1 term with a Moreau envelope before applying FISTA.The smoothed gradient is Lipschitz continuous, enabling the first-order update.

B. FISTA for compressed sensing with structured dictionary mismatches

The paper develops FISTA implementations for joint sparse recovery under structured dictionary mismatches, handling nonsmooth penalties and bounded constraints through smoothing, proximal projections, and continuation.

  • Joint sparse recovery: FISTA is applied to joint sparse recovery, while the bounded formulation requires incorporating positive and bounded constraints as an indicator function.The constraint set is F = {s ≥0, −rs ≤p ≤rs}.
  • Smoothed bounded recovery: The nonsmooth ℓ2,1 penalty is approximated by a Moreau envelope so the resulting objective has a Lipschitz-continuous gradient.The approximation becomes more accurate as µ decreases.
  • Proximal implementation: The proximal operator for the indicator constraint is implemented as a projection onto the feasible set and can be computed element-wise.Each pair is projected onto a two-dimensional convex cone.
  • Algorithms: The paper provides separate FISTA procedures for joint sparse recovery and its bounded variant.The bounded version needs extra smoothing and constraint-projection steps.
  • Continuation: Smaller µ improves approximation accuracy but increases the Lipschitz constant, causing slower convergence.Continuation addresses this trade-off by solving sequentially with decreasing smoothing parameters and warm starts.

V. PASSIVE AND ACTIVE SENSING APPLICATIONS

The paper formulates passive array and active MIMO radar sensing as sparse recovery problems over discretized spatial grids. Off-grid targets are modeled through structured dictionary mismatch terms, enabling joint sparse recovery of angular locations.

  • Passive sensing: The passive sensing model uses a nonuniform linear array with linearly placed sensors and a discretized angular region of interest.The steering vector is defined from sensor locations and wavelength.
  • Passive sensing: The passive model represents targets with a sparse signal whose nonzero entries correspond to occupied angular grid points.The received measurements include white Gaussian noise under the stated uncorrelated-target assumption.
  • Active sensing: The active sensing model describes a MIMO radar with transmitters, receivers, grid points, propagation delays, and target reflection factors.The formulation assumes narrow-band synchronized operation and uses far-field approximations.
  • Active sensing: The active model stacks receiver measurements over snapshots and expresses them as a linear sparse signal model with measurement noise.The targets are assumed stationary or moving slowly relative to the sampling process.
  • Compressed sensing model: Compressed measurements from multiple receivers are stacked into one vector and represented using receiver-specific sensing matrices.Random matrices reduce the measurement dimension before joint recovery.
  • Structured mismatch model: Off-grid targets are represented by perturbing the nominal grid and incorporating the difference between actual and nominal angles into the dictionary model.The resulting matrix B is used in the joint-sparse optimization to detect angular locations.

VI. NUMERICAL EXAMPLES

Numerical experiments evaluate joint sparse recovery under dictionary mismatches and compare it with alternating minimization and P-BPDN. The reported results favor the joint sparse method in reconstruction quality and computational effort, including passive and active sensing scenarios.

  • First experiment: The first experiment generates data and mismatch parameters from Gaussian distributions using the measurement model.The comparison includes the FISTA-based joint sparse method and alternating minimization.
  • First experiment: The joint sparse method provides better reconstruction with less computational effort than alternating minimization in the first experiment.The paper uses this example to evaluate performance when dictionary mismatches exist.
  • Passive and active sensing: The final two experiments compare joint sparse recovery with P-BPDN under passive and active sensing scenarios.The paper notes that P-BPDN is equivalent to the reconstruction method proposed in reference.

A. Randomly Generated Data

Numerical experiments compare joint-sparse recovery with alternating minimization and P-BPDN across randomly generated data and nonuniform-array DOA estimation. The joint-sparse methods generally achieve lower error or comparable accuracy with substantially shorter runtimes.

  • Randomly Generated Data: FISTA-based joint-sparse recovery performs uniformly better than alternating minimization as the number of measurements varies.The signal reconstruction error is evaluated as ∥s − ˆs∥2/∥s∥2 over 50 Monte Carlo iterations.
  • Randomly Generated Data: 0.26s versus 15.61s: FISTA-based joint-sparse recovery is substantially faster than alternating minimization in the measurement comparison.
  • Randomly Generated Data: Joint-sparse recovery has uniformly smaller reconstruction error than alternating minimization as sparsity increases from 2 to 12.This comparison uses 50 measurements.
  • Nonuniform Linear Array Using Off-grid Compressed Sensing: BJS yields better DOA estimation accuracy than P-BPDN across both SNR and time-sample comparisons.The experiments vary SNR from −10 dB to 10 dB with T = 1000, and vary T while fixing SNR at 0 dB.
  • Nonuniform Linear Array Using Off-grid Compressed Sensing: 4.92s versus 63.09s: FISTA with continuation reaches the same DOA estimation error as BJS's interior-point method much faster.Both methods achieve a DOA estimation error of 5.5 × 10−4.

C. MIMO Radar Using Off-grid Compressed Sensing

The MIMO radar experiments evaluate joint sparse recovery for off-grid DOA estimation under closely spaced targets and changing dynamic range. The proposed method achieves better reconstruction and DOA estimation performance than P-BPDN, with fast FISTA-based implementations and applications to passive and active sensing.

  • Experimental setup: The experiments compare FISTA-based joint sparse recovery with P-BPDN in a MIMO radar scenario.The system uses 30 transmitters and 10 receivers, with randomly generated sensor locations and QPSK waveforms.
  • Experimental setup: The first simulation evaluates two closely spaced targets over SNRs from −10 dB to 10 dB using 50 Monte Carlo iterations.Target locations are randomly generated from [16.5°, 17.5°] and [18.5°, 19.5°], with equal signal power.
  • DOA estimation: The proposed method achieves consistent DOA estimation performance in the closely located two-target experiment.The figure reports average DOA estimation error in degrees.
  • DOA estimation: The joint sparse method yields better reconstruction performance than P-BPDN for location estimation.This comparison concerns the MIMO radar off-grid compressed-sensing experiment.
  • Dynamic range: The joint sparse method performs better than P-BPDN as the dynamic range changes, and both figures show improved DOA estimation accuracy over P-BPDN.The changing-dynamic-range experiment fixes σa = 1 and varies σb.
  • Method and scope: The framework uses bounded joint sparse recovery and FISTA, with numerical demonstrations in both passive and active sensing applications.The conclusion also reports more satisfactory results when structured dictionary mismatches exist and identifies further analysis of DOA accuracy as future work.

APPENDIX

The appendix develops the proof of the reconstruction-error bound for joint sparse recovery. It combines J-RIP, tail decompositions, optimality conditions, and a condition on the J-RIP parameter to control the error.

  • Proof setup: The proof introduces J-RIP as the matrix property used to analyze joint sparse recovery.The first lemma derives a relation for vectors with disjoint support sets from J-RIP.
  • Proof setup: The reconstruction error h is defined as ˆx − x, where ˆx solves (JS) and x is the original signal.The proof partitions coefficients according to their largest joint magnitudes.
  • Tail decomposition: The coefficient support is partitioned into T0, T1, and subsequent sets ordered by decreasing joint magnitude.T0 contains the k largest coefficients, while T1, T2, and later sets contain successive groups of size K.
  • Tail decomposition: A tail-bounding lemma relates the ℓ2 norm of the reconstruction-error tail to its ℓ2/ℓ1 norm.The appendix then combines this tail control with optimality conditions for (JS).
  • Optimality conditions: The proof uses two optimality conditions for (JS) together with the measurement model y = Φx + w.These conditions bound the reconstruction error and the error outside the principal support set.
  • Main bound: The main proof first bounds h on T01 using J-RIP and then shows that h outside T is essentially small.The argument treats joint sparsity and derives a performance bound for an unconstrained optimization problem.
Loading 1309.0858v3…