PaperlayerView exact revision on arXiv

Source-linked AI summary

Identification of Parametric Underspread Linear Systems and Super-Resolution Radar

Waheed U. Bajwa, Kfir Gedalyahu, Yonina C. Eldar

arXiv:1008.0851v2cs.ITmath.IT

TL;DR

The paper asks what input bandwidth and temporal support suffice to identify parametric underspread linear systems from a single observation. It specifies a pulse-train input and polynomial-time recovery procedure, and concludes that the required time–bandwidth product scales with the square of the number of delay–Doppler pairs.

  • Problem

    The paper addresses how to choose input bandwidth and temporal support to identify parametric underspread linear systems from a single observation.

    Source: §I · p. 3

  • Method

    The paper specifies a pulse-train input and a polynomial-time recovery procedure for systems described by finite sets of delays and Doppler shifts.

    Source: §VIII · p. 28

  • Results

    For sufficiently underspread parametric systems, the time–bandwidth product is proportional to the square of the total number of delay–Doppler pairs.

    Source: §VIII · p. 28

  • Takeaways & Limitations

    The recovery procedure achieves infinitesimally fine resolution in delay–Doppler space when the available temporal degrees of freedom meet the stated condition.

    Source: §V · p. 17

Abstract

from arXiv · show

Identification of time-varying linear systems, which introduce both time-shifts (delays) and frequency-shifts (Doppler-shifts), is a central task in many engineering applications. This paper studies the problem of identification of underspread linear systems (ULSs), whose responses lie within a unit-area region in the delay Doppler space, by probing them with a known input signal. It is shown that sufficiently-underspread parametric linear systems, described by a finite set of delays and Doppler-shifts, are identifiable from a single observation as long as the time bandwidth product of the input signal is proportional to the square of the total number of delay Doppler pairs in the system. In addition, an algorithm is developed that enables identification of parametric ULSs from an input train of pulses in polynomial time by exploiting recent results on sub-Nyquist sampling for time delay estimation and classical results on recovery of frequencies from a sum of complex exponentials. Finally, application of these results to super-resolution target detection using radar is discussed. Specifically, it is shown that the proposed procedure allows to distinguish between multiple targets with very close proximity in the delay Doppler space, resulting in a resolution that substantially exceeds that of standard matched-filtering based techniques without introducing leakage effects inherent in recently proposed compressed sensing-based radar methods.

I. INTRODUCTION

The section studies single-observation identification of finite-delay–Doppler underspread linear systems, including input conditions, a polynomial-time pulse-train recovery procedure, and its application to super-resolution radar. It also establishes notation and conventions for the analysis.

I. INTRODUCTION

  • Unlike prior constructive identifiability results for arbitrary underspread systems –, the paper characterizes the input bandwidth and temporal support needed for finite-parametric systems.The prior proofs require infinite-bandwidth inputs; the paper treats parametric systems directly in the analog domain to avoid delay–Doppler quantization.Source: §I · pp. 3–4
  • Sufficiently underspread parametric systems are identifiable from one observation when the input time–bandwidth product is proportional to the square of the number of delay–Doppler pairs.The paper gives a constructive proof and specifies a finite train of pulses as an input.Source: §I · pp. 3–4
  • The polynomial-time recovery procedure combines sub-Nyquist delay estimation with recovery of frequencies from sums of complex exponentials to estimate delays, Doppler shifts, and attenuation factors.Small input bandwidth supports delay recovery, while the pulse train's small temporal support supports recovery of Doppler shifts and attenuation factors.Source: §I · p. 4
  • The proposed approach yields radar target resolution substantially beyond standard matched filtering without the leakage effects inherent in compressed sensing-based radar methods.The introduction identifies direct analog-domain treatment without delay–Doppler quantization as key to avoiding leakage.Source: §I · p. 4
  • Because arbitrary underspread-system responses can be represented by the parametric form as the number of pairs tends to infinity, the result also gives a constructive identifiability proof for sufficiently underspread systems.As with earlier results –, this interpretation suggests that identifying arbitrary underspread systems requires inputs with infinite bandwidth and temporal support.Source: §I · p. 5

Notation

  • Vector elements are written a_n, and matrix elements are written A_ij.Boldface lowercase and uppercase letters denote vectors and matrices, respectively.Source: §I · p. 5
  • The superscripts ∗, T, and H denote conjugation, transposition, and conjugate transposition, respectively.Source: §I · p. 5
  • The continuous-time and discrete-time Fourier transforms are defined, and the discrete-time transform is periodic in ω with period 2π/T.Source: §I · p. 5
  • A† denotes the Moore–Penrose pseudoinverse of matrix A.Source: §I · p. 5

II. PROBLEM FORMULATION AND MAIN RESULTS

The paper formalizes identification of parametric underspread linear systems from a known input and gives sufficient conditions for recovery from one observation. Its theorem bounds the required time–bandwidth product and outlines a polynomial-time recovery strategy.

II. PROBLEM FORMULATION AND MAIN RESULTS

  • The system response is modeled using a finite set of delay–Doppler pairs, each with an associated complex attenuation factor.The model permits repeated delays, which can be expressed using distinct delays and their associated Doppler shifts.Source: §II · pp. 5–6
  • The assumed delay–Doppler footprint lies in a rectangular region, with delay spread below the pulse support and Doppler spread much smaller than its bandwidth.These conditions are stated as [A1]–[A3].Source: §II · p. 6
  • The proposed probe is a finite train of pulses built from a unit-energy prototype pulse with bandwidth W and essentially finite temporal support.The parameter N is proportional to the input's time–bandwidth product and represents its available temporal degrees of freedom.Source: §II · p. 6
  • A parametric ULS completely described by total K is identifiable in polynomial time from a single observation if [A1]–[A3] hold, |xn| > 0 for every n = 0, ..., N − 1, and TW ≥ 2π(K + 1)^2.Source: §II · p. 7
  • The recovery strategy first uses sub-Nyquist sampling results to recover delays, then uses frequency recovery from complex exponentials to estimate Doppler shifts and attenuation factors.The theorem combines conditions on input bandwidth and temporal support.Source: §II · p. 7

III. POLYNOMIAL-TIME IDENTIFICATION OF ULSS

The recovery procedure is organized into sampling and recovery stages. Its output is rewritten using the assumption that νmaxT ≪ 1, approximating each Doppler modulation as nearly constant within a pulse interval.

III. POLYNOMIAL-TIME IDENTIFICATION OF ULSS

  • The procedure is conceptually divided into sampling and recovery stages.Fig. 2 schematizes the polynomial-time recovery procedure.Source: §III · p. 8
  • The output is rewritten using νmaxT ≪ 1, which makes each Doppler modulation approximately constant over a pulse interval.The approximation applies on t ∈ [(n − 1)T, nT).Source: §III · p. 8
  • The rewrite defines sequences ai[n] for each distinct delay.The section uses these sequences in describing the recovery procedure.Source: §III · p. 8

A. The Sampling Stage

The sampling stage converts the system output into low-rate measurements designed for recovering parametric underspread systems. It combines low-pass filtering, uniform sampling, and a correction step to form measurements whose structure depends on the unknown delays.

A. The Sampling Stage

  • The sampling architecture may use one uniform-sampling channel, simplifying the analog front end.Stable invertibility requires conditions on the prototype pulse and low-pass-filter kernel.Source: A. The Sampling Stage · pp. 9, 11
  • The output is low-pass filtered with impulse response s∗(−t) and then uniformly sampled to form the recovery measurements.The filter also serves as the system-identification hardware front end and rejects out-of-band noise and interference.Source: A. The Sampling Stage · p. 9
  • The filtered samples are split into p sequences cℓ[n], each at rate 1/T, corresponding to a total sampling rate of p/T.This is a serial-to-parallel representation of the samples at the filter output.Source: A. The Sampling Stage · p. 9
  • After correction, the measurements form a linear model whose matrix depends on the unknown set of delays, enabling subspace methods to recover those delays.The sampling-stage decomposition also supports an implementation using three correction stages, including an FFT.Source: A. The Sampling Stage · pp. 10, 12

B. The Recovery Stage

The recovery stage separates parameter estimation into two steps: first finding the delays, then using those delays to estimate the associated Doppler shifts and attenuation factors.

B. The Recovery Stage

  • The procedure first recovers delays τ from d[n] using subspace methods, then uses the recovered delays to obtain the Doppler shifts and attenuation factors.These are the two steps of the recovery stage.Source: B. The Recovery Stage · p. 12

1) Recovery of the Delays:

The recovery procedure estimates delays first, then estimates Doppler shifts and attenuation factors for each delay. Sufficient conditions establish when the parametric system is uniquely identifiable from one observation.

1) Recovery of the Delays:

  • ESPRIT with an additional smoothing stage recovers delays τ from d[n], after which the recovered delays support estimation of Doppler shifts and attenuation factors.The delay-recovery algorithm is given in Table I.Source: 1) Recovery of the Delays · p. 12

2) Recovery of the Doppler-Shifts and Attenuation Factors:

  • For each delay, Doppler shifts are recovered as frequencies in a weighted complex-exponential sum; annihilating filters work at N = 2Kν,i, while cited subspace methods are more noise-robust but require more samples.Once the Doppler shifts are recovered, the attenuation factors are obtained from the corresponding measurements.Source: 2) Recovery of the Doppler-Shifts and… · pp. 13–14

IV. SUFFICIENT CONDITIONS FOR IDENTIFICATION

  • Theorem 2 gives sufficient conditions N ≥ 2Kν,max and W ≥ 4πKτ, and assumes Kτ and Kν,max, or upper bounds, are known at the transmitter.The theorem states unique identification from a single observation when its conditions hold.Source: §IV · p. 16
  • Under Theorem 2's assumptions, Section III's recovery procedure with samples at t = 2nπ/W uniquely identifies H from one observation when the known input x(t) satisfies TW ≥ 2π(K + 1)^2.Source: §IV · p. 16

V. DISCUSSION

The discussion situates the proposed recovery procedure among prior identification methods and states its resolution and sampling guarantees. It also contrasts the method with quantized-grid and exhaustive-search approaches.

V. DISCUSSION

  • The discussion connects the recovery procedure to super-resolution radar target detection.It identifies radar as an application of the results.Source: §V · p. 17
  • The procedure achieves infinitesimally fine delay–Doppler resolution when the available temporal degrees of freedom are on the order of Ω(K^2), for sufficiently underspread systems.The guarantee applies to a single observation and does not restrict the distribution of delay–Doppler pairs.Source: §V · pp. 17–18
  • The numerical experiments confirm recovery when T W ≥ 2π(K + 1)^2 and report that close-pair resolution depends primarily on SNR, with graceful degradation under noise.The discussion presents these experiments as confirmation of the theoretical analysis.Source: §V · p. 17
  • Prior grid-based methods, require T W = Ω(K^2/log T W) and limit resolution to W^-1 in delay and T^-1 in Doppler.The discussion notes their time–bandwidth scaling is about Ω(K^2).Source: §V · pp. 17–18
  • Unlike, the analysis makes the time–bandwidth requirement explicit and gives a polynomial-time algorithm without restrictions on pair distributions.The cited comparison says assumes sampling is given and uses exhaustive search in a K-dimensional space.Source: §V · p. 18

VI. APPLICATION: SUPER-RESOLUTION RADAR

The paper applies parametric ULS recovery to radar, where off-grid targets cause leakage under quantization and matched filtering has limited resolution. In the nine-target example, the proposed recovery identifies all targets while matched-filter peaks miss most true centers.

VI. APPLICATION: SUPER-RESOLUTION RADAR

  • The radar application follows because a monostatic radar’s noiseless, clutter-free received signal has the parametric form, with each delay–Doppler pair corresponding to a distinct target echo.The resulting procedure can distinguish targets with close radial positions or similar radial velocities.Source: §VI · p. 19
  • Off-grid targets spread energy across nearby quantized delay–Doppler cells through sinc kernels, producing the leakage effect.This leakage can cause missed detections and false alarms and makes the original delays and Doppler shifts unreliable to identify.Source: §VI · p. 20
  • Matched-filter resolution is tied to the ambiguity-function support and is typically on the order of W^-1 in delay and T^-1 in Doppler.The paper states this limits separation of closely spaced targets.Source: §VI · pp. 20–21
  • The proposed recovery identifies all nine targets, while matched-filter peaks are not centered on the true targets for most of them.Fig. 4 compares both methods for nine closely spaced targets.Source: Figure 4 · p. 20, §VI · p. 21

VII. NUMERICAL EXPERIMENTS

The numerical experiments examine noise robustness and implementation choices for recovery of a six-pair parametric ULS. The section specifies the simulated system, probing signal, recovery methods, and error metric.

VII. NUMERICAL EXPERIMENTS

  • The experiments use a ULS with six delay–Doppler pairs, grouped as Kτ = 2 and Kν,1 = Kν,2 = 3, with unit amplitudes and random phases.The pair locations are shown in Fig. 5.Source: §VII · pp. 21–22
  • Recovery uses ESPRIT for delays and the matrix-pencil method for Doppler shifts, assuming both methods have the correct model orders.The setup also specifies a prototype pulse with constant frequency response over the working band.Source: §VII · p. 22
  • The performance metric is normalized mean-squared error for estimated delays and Doppler shifts, averaged over 100 noise realizations.The section also considers truncated digital filters, finite samples, probing-sequence choice, and model-order mismatch.Source: §VII · pp. 21–22

1) Robustness to Noise:

The noise experiment evaluates delay and Doppler estimation error across SNR levels. The proposed procedure’s resolution depends primarily on SNR, and its performance degrades gracefully in noise.

1) Robustness to Noise:

  • The proposed procedure’s ability to resolve delay–Doppler pairs depends primarily on SNR and degrades gracefully in the presence of noise.Fig. 6 plots the MSE of estimated delays and Doppler shifts as a function of SNR.Source: 1) Robustness to Noise · p. 22

2) Effects of Truncated Digital-Correction Filter Banks:

The experiments show that filter truncation and finite sampling eventually impose error floors, while longer filters, more samples, and a raised-cosine sampling filter can sustain accurate delay and Doppler estimates at high SNR.

2) Effects of Truncated Digital-Correction Filter Banks:

  • Truncated filter lengths determine both computational delay and computational load.The correction filters generally have infinite impulse responses, so practical implementation requires truncation.Source: 2) Effects of Truncated… · pp. 22–23
  • For every fixed filter length, truncation error eventually exceeds additive-noise error as SNR rises.The resulting error floors are shown in Fig. 7.Source: 2) Effects of Truncated… · p. 23
  • 49-tap filters provide good estimation accuracy up to 60 dB SNR, while 35-tap filters yield good estimates below 50 dB.Source: 2) Effects of Truncated… · p. 23

3) Effects of Finite Number of Samples:

4) Effects of the Probing Sequence:

The paper examines how probing-sequence choice and model-order mismatch affect recovery, then concludes that sufficiently underspread parametric systems are identifiable under stated input conditions. Its simulations report robustness to noise and implementation issues when those conditions hold.

4) Effects of the Probing Sequence:

5) Effects of Model-Order Mismatch:

  • Under model-order mismatch, the experiment recovers the first three delays and their Doppler-shifts, while the fourth delay is recovered but its Doppler-shifts are not properly identified.Source: 5) Effects of Model-Order Mismatch · p. 27
  • The sequential method can still recover a delay when N < 2Kν,i; the failure is confined to Doppler-shifts associated with that delay.The delay itself is recovered correctly if the input bandwidth is not too small.Source: 5) Effects of Model-Order Mismatch · p. 27

VIII. CONCLUSION

  • Sufficiently underspread parametric systems are identifiable when input time–bandwidth product is proportional to the square of the number of delay–Doppler pairs.The paper also specifies a pulse-train input and a polynomial-time recovery procedure.Source: §VIII · p. 28
  • The simulations report robustness to noise and implementation issues when the input time–bandwidth product meets the required conditions.Source: §VIII · p. 28
  • The identification method can be used for super-resolution target detection using radar.Source: §VIII · p. 28

Related papers

Loading 1008.0851v2…