PaperlayerView exact revision on arXiv

Source-linked AI summary

Time Delay Estimation from Low Rate Samples: A Union of Subspaces Approach

Kfir Gedalyahu, Yonina C. Eldar

arXiv:0905.2429v3cs.IT

TL;DR

Time-delay estimation in multipath channels is difficult when existing methods require analog processing or high-rate sampling for adequate resolution. This paper develops a union-of-subspaces sampling framework that combines low-rate channel samples with ESPRIT to recover delays at the minimal rate, including overlapping pulses.

  • Problem

    Existing time-delay methods either operate on the analog received signal or require high sampling rates for useful time resolution.

  • Method

    The paper combines sampling theory and DOA subspace methods, manipulating low-rate samples so ESPRIT can estimate unknown multipath delays.

  • Results

    Perfect recovery is achieved at the minimal sampling rate 2K/T, which depends on the number of paths and transmission rate rather than pulse bandwidth.

  • Takeaways & Limitations

    The framework supports overlapping or infinite-length pulses and provides a sampling-theory perspective for analog signals over an infinite union of subspaces.

Abstract

from arXiv · show

Time delay estimation arises in many applications in which a multipath medium has to be identified from pulses transmitted through the channel. Various approaches have been proposed in the literature to identify time delays introduced by multipath environments. However, these methods either operate on the analog received signal, or require high sampling rates in order to achieve reasonable time resolution. In this paper, our goal is to develop a unified approach to time delay estimation from low rate samples of the output of a multipath channel. Our methods result in perfect recovery of the multipath delays from samples of the channel output at the lowest possible rate, even in the presence of overlapping transmitted pulses. This rate depends only on the number of multipath components and the transmission rate, but not on the bandwidth of the probing signal. In addition, our development allows for a variety of different sampling methods. By properly manipulating the low-rate samples, we show that the time delays can be recovered using the well-known ESPRIT algorithm. Combining results from sampling theory with those obtained in the context of direction of arrival estimation methods, we develop necessary and sufficient conditions on the transmitted pulse and the sampling functions in order to ensure perfect recovery of the channel parameters at the minimal possible rate. Our results can be viewed in a broader context, as a sampling theorem for analog signals defined over an infinite union of subspaces.

I. INTRODUCTION

The paper develops low-rate sampling methods for recovering multipath channel delays and gains, addressing high-rate or analog requirements and overlapping pulses. It combines sampling theory with ESPRIT-based subspace estimation and frames the result as sampling over an infinite union of subspaces.

  • Problem: Time delay estimation identifies the delays and gain coefficients of weighted, delayed replicas created by multipath propagation.The setting applies to known-shape pulses transmitted through media such as radar, underwater acoustic, and wireless channels.
  • Contribution: The proposed methods target perfect channel-parameter recovery from samples at a minimal rate independent of the probing-pulse bandwidth.The rate depends on the number of multipath components and the transmission rate, while the sampling schemes accommodate different sampling techniques.
  • Prior limitations: Earlier approaches commonly used analog processing or high-rate samples, with time resolution limited by pulse bandwidth and sampling considerations often left unspecified.Prior work also lacked concrete pulse and sampling conditions guaranteeing unique recovery in the low-rate setting.
  • Signal model: The signal model removes the need for non-overlapping experiments, allowing general or infinite-length pulses and interference between adjacent transmissions.This addresses settings such as constant-rate wireless communication, where adjacent symbols can produce overlapping reflections.
  • Method: Appropriate manipulation of sampling sequences converts delay recovery into a direction-of-arrival estimation problem solved with ESPRIT.The approach combines standard sampling theory with DOA algorithms to estimate unknown delays from low-rate samples.
  • Broader context: The framework connects the problem to analog compressed sensing over an infinite union of subspaces and extends sampling-theory results beyond finite unions.Relative to FRI methods, the paper states that its approach permits lower sampling rates and computational cost without stringent pulse-shape conditions.

III. SAMPLING SCHEME

For known delays, the received-signal model is treated as a finitely generated shift-invariant subspace. A multichannel filter-and-sample scheme recovers the coefficient sequences at one sample stream per generator, yielding rate K/T.

  • Known-delay model: Known-delay signals form a special case of a finitely generated shift-invariant subspace with generators given by delayed versions of the known pulse.The generators are typically chosen to form a Riesz basis for unique stable coefficient representation.
  • Sampling architecture: The sampling scheme uses K parallel channels, each filtering the signal and uniformly sampling at times t = nT.The resulting channel outputs are sampling sequences that can be processed jointly.
  • Recovery condition: An adequate multichannel filter bank recovers the coefficient sequences when the frequency-domain sampling matrix is stably invertible almost everywhere.The filter bank uses the inverse of the matrix formed from generator and sampling-filter Fourier transforms.
  • Sampling rate: K/T is the average sampling rate because K sampling sequences each operate at rate 1/T.With known delays, this corresponds intuitively to one sample per signal degree of freedom in each period T.

B. Unknown delays

The paper formulates unknown-delay recovery as a low-rate sampling problem and uses subspace methods to recover delays and channel parameters. Under conditions on the pulse and sampling filters, 2K channels achieve perfect recovery at the minimal possible rate.

  • Unknown-delay sampling scheme: The unknown-delay system uses parallel sampling channels that pre-filter x(t) and uniformly sample each output at times nT.The resulting samples are represented in the Fourier domain and then organized into matrix equations.
  • Unknown-delay sampling scheme: 2K sampling filters are sufficient, and the paper claims this is the minimal possible rate for all signals x(t).The number of channels p must satisfy p ≥ K; under stated conditions, p = 2K guarantees perfect recovery.
  • Filter and pulse conditions: A working frequency band is selected to match the pulse’s frequency occupation, while allowing support for both complex- and real-valued signals.The band is indexed by γ and the pulse need not be bandlimited.
  • Delay recovery: The recovery problem is recast in a direction-of-arrival framework using a Vandermonde measurement matrix whose structure enables subspace-based delay estimation.After the delays are recovered, the remaining signal vectors can be obtained through linear filtering relations.
  • Filter and pulse conditions: Stable invertibility of the correction system requires conditions on g(t) and on the sampling filters’ matrix S.These conditions yield a stable digital correction filter bank for reconstructing the channel parameters.
  • Implementation limitation: The correction filters are generally infinite-length digital filters, so truncation introduces a practical delay trade-off.The resulting method can have longer total delay because of the additional digital filtering stage.

C. Examples of filters

The paper introduces examples of sampling filters satisfying the recovery conditions, beginning with complex bandpass filters.

  • Examples of filters: The paper presents filter examples that satisfy the required conditions for sampling and recovery.The first example uses a set of complex bandpass filters.

1) Complex bandpass filter-bank: 

The complex bandpass filter-bank example illustrates how sampling kernels preserve information about short pulses at a low sampling rate. Direct low-rate sampling can instead produce mostly zero samples.

  • Complex bandpass filter-bank: The example demonstrates why the sampling filter is essential when short pulses are sampled below their conventional time-resolution requirements.The displayed channel outputs show the filtered signal at the sampling instants.
  • Complex bandpass filter-bank: The example uses g(t) = δ(t) with K = 2 diracs per period T = 1 and displays the outputs of the first three sampling channels.Dashed lines indicate the sampling instants.
  • Complex bandpass filter-bank: Sampling kernels smooth short pulses, allowing low-rate samples to retain information about the signal.Without the filters, direct low-rate sampling would often yield only zero samples.

2) Delayed channels:

A delayed-channel implementation uses filters formed by delaying an ideal low-pass filter. Uniformly spaced delays reduce the scheme to ideal low-pass filtering followed by uniform sampling.

  • Delayed channels: Each sampling filter is an ideal low-pass filter preceded by a delay Δℓ ∈ [0, T).The resulting matrix includes a Vandermonde structure, and invertibility holds when the channel delays Δℓ are distinct.
  • Delayed channels: Uniformly spaced delays Δℓ = (ℓ−1)T/p permit implementation with an ideal low-pass filter followed by uniform sampling at rate p/T.The corresponding low-pass cutoff is πp/T.

IV. RECOVERY OF THE UNKNOWN DELAYS

The delay-recovery problem is recast in a form analogous to direction-of-arrival estimation, enabling subspace-based uniqueness analysis. Under suitable sampling-channel conditions, the scheme achieves the minimal rate 2K/T, independent of pulse bandwidth.

  • DOA analogy: The modified measurements have the same structural form as a direction-of-arrival model, with each column depending only on one unknown delay.This correspondence permits DOA estimation methods to be adapted to delay recovery.
  • DOA analogy: ESPRIT is selected because the measurement matrix satisfies the rotational-invariance property required by the algorithm.MUSIC and ESPRIT are subspace methods; ESPRIT exploits rotational invariance for efficient parameter estimation.
  • Uniqueness conditions: Unique recovery follows by extending finite-measurement DOA conditions to the infinite measurement set and applying the resulting finite-equation characterization.The solution to the finite equations is also unique for the corresponding infinite system.
  • Sampling-rate guarantee: 2K/T is the minimal sampling rate that guarantees perfect recovery for every signal in the model.The rate follows from requiring more than 2K−1 sampling channels and matches the theoretical minimum for the associated union of shift-invariant subspaces.
  • Sampling-rate guarantee: 128MHz versus 2GHz is obtained for a 1GHz pulse transmitted at 2MHz with 32 significant multipath components.The example satisfies 2K/T < W, so the proposed rate is below the pulse’s Nyquist rate.
  • Practical implications: Lower sampling rates can support more precise ADCs, lower ADC power consumption, and more efficient real-time digital processing.These implementation benefits arise because fewer samples must be acquired and processed.

C. Recovering the unknown delays

The recovery algorithm is based on the rank and span of correlation matrices formed from the measurement vectors. The channel is separated into uncorrelated and correlated cases, with direct ESPRIT applicable only in the former.

  • Recovery conditions: The ESPRIT procedure requires the correlation matrix Rbb to be positive definite.This condition is equivalent to the measurement-coefficient span having dimension K.
  • Recovery conditions: The uncorrelated case is defined by dim(span(b[Λ])) = K, whereas smaller dimension defines the correlated case.In the correlated case, ESPRIT cannot be applied directly to the measurement vectors.
  • Recovery conditions: The uncorrelated-versus-correlated decision can be made from the measurements by forming Rdd because Rdd and Rbb have equal rank.The equality follows from the full column rank of N(τ).
  • Signal-subspace construction: For positive-definite Rbb, Rdd has rank K and its column span equals the signal subspace spanned by N(τ).An SVD of Rdd provides K left singular vectors spanning this subspace.

1) Uncorrelated Case:

In the uncorrelated case, delays are recovered from a signal-subspace basis using the Vandermonde matrix’s rotational invariance. Correlated measurements require spatial smoothing before ESPRIT.

  • Uncorrelated Case: The signal-subspace basis Es is constructed from the K left singular vectors associated with Rdd’s nonzero singular values.These vectors span the same subspace as the columns of N(τ).
  • Uncorrelated Case: The Vandermonde matrix provides rotational invariance through a diagonal matrix whose entries encode the unknown delays.Deleting its first and last rows yields the shifted submatrices used by ESPRIT.
  • Uncorrelated Case: The matrix Φ = E_s↑†E_s↓ is formed from shifted subspace bases, and its eigenvalues recover the diagonal delay-encoding matrix.The delays are then retrieved from the diagonal elements of that matrix.
  • Uncorrelated Case: The recovery algorithm constructs Rdd, performs SVD, forms Φ, computes its eigenvalues, and retrieves the delays.These steps implement ESPRIT on the measurement set.
  • Uncorrelated Case: When Rbb is not positive definite, spatial smoothing is applied before ESPRIT because the direct signal-subspace span is incomplete.This addresses the correlated case, where rank(Rdd) is smaller than K.

2) Correlated Case:

The paper places its sampling problem within unions of shift-invariant subspaces and contrasts its continuous-delay setting with finite-union compressed-sensing approaches. It provides an ESPRIT-based reconstruction method that reaches the minimal rate without discretizing delays.

  • Infinite union of subspaces: The signal model forms an infinite union of shift-invariant subspaces indexed by continuously varying multipath delays.For fixed delays, each signal lies in an SI subspace spanned by K generators.
  • Sampling-rate limit: Sampling theory establishes 2K as the minimal number of channels for perfect recovery over a union of SI subspaces.With one sample per channel every T seconds, this corresponds to a minimal sampling rate of 2K/T.
  • Finite versus infinite unions: Finite-union compressed-sensing methods assume delays lie on a discrete grid, whereas this paper accommodates any continuous set of delays.The discrete-grid formulation uses N possible delays and can achieve rate 2K/T through a finite-union method.
  • Reconstruction: The proposed reconstruction uses ESPRIT and achieves the minimal rate 2K/T with polynomial complexity rather than combinatorial optimization.The method is presented as a systematic sampling and reconstruction framework for an infinite union of SI spaces.
  • Sampling filters: Compared with finite-union compressed sensing, the approach can use simpler sampling filters instead of filters requiring careful parameter design.Examples include low-pass filters and bandpass filter banks.

C. Signals with finite rate of innovation

The paper relates its multipath model to finite-rate-of-innovation signals and applies the resulting sampling scheme to time-varying wireless channels. Its shift-invariant structure enables low-rate recovery of path delays and, when symbols are known, path gains.

  • Finite rate of innovation: Finite-rate-of-innovation signals contain finitely many degrees of freedom per unit time, with recovery reducing to estimating unknown shifts and weights.Examples include streams of Diracs, nonuniform splines, and piecewise polynomials.
  • Relation to FRI: The paper's model is a special FRI case with shift-invariant structure that keeps delays constant relative to each symbol period.The method uses this additional structure to reduce the sampling rate while guaranteeing perfect recovery.
  • Prior FRI methods: Prior infinite-length FRI methods use specific finite-support kernels and local reconstruction under restricted pulse assumptions.The cited approach is limited to Diracs, differentiated Diracs, or short compactly supported pulses without a DC component.
  • Sampling-rate comparison: The cited FRI approach requires at most K Diracs in each interval of size 2KLT_s, leading to a higher sampling-rate requirement.Here L denotes the support of the sampling kernel.
  • Wireless application: If the pulse satisfies condition (32) with p = 2K, the scheme recovers path delays; known transmitted symbols additionally permit recovery of time-varying path gains.The channel model assumes gains are constant over each symbol period and delays lie within one symbol period.
  • Wireless application: For wireless channel estimation, the proposed scheme recovers channel parameters at a rate proportional to the number of paths rather than the transmitted pulse bandwidth.The application targets time-varying multipath channels carrying known-shape pulses or PAM communication signals.
  • Implementation motivation: UWB communication illustrates the implementation motivation: reducing sampling rates can make higher-resolution, lower-power ADCs feasible than gigahertz-rate sampling.The paper notes that current high-rate ADCs may operate at low resolution and high power consumption.

VII. NUMERICAL EXPERIMENTS

The experiments evaluate channel estimation, noise robustness, and the effects of sampling-channel count under time-varying multipath conditions. The method estimates channel parameters from noisy low-rate samples and reaches the CRB above 15 dB SNR.

  • VII. NUMERICAL EXPERIMENTS: The experiments cover channel estimation, noise performance, finite measurement-vector effects, and imperfect digital correction filtering.Simulations generally use ideal band-pass sampling filters, TLS-ESPRIT, and averages over 1000 experiments.
  • A. Channel estimation: K = 4 channel paths are simulated with time-varying gain coefficients generated using Jakes’ model.The channel is modeled as slowly varying relative to the symbol rate, and p = 5 sampling channels are used.
  • A. Channel estimation: p = 5 sampling channels yield good estimates of channel parameters even when samples are noisy.Figures 4 and 5 compare the original and estimated channel energy and the first path’s time-varying gain magnitude.
  • B. Performance in the presence of noise: The delay-estimation MSE reaches the CRB for SNR> 15dB with K = 2 and p = 4.The comparison is made in the range where delay estimation is considered sufficiently unbiased.
  • B. Performance in the presence of noise: Increasing the number of sampling channels improves delay-estimation error at SNR=10dB, indicating improved noise robustness through oversampling.This experiment uses K = 2 paths.

C. Effects of imperfect approximation of Rdd

The experiments examine how finite measurement-vector counts and finite digital correction filters affect delay-estimation accuracy. Faster-varying gain sequences require fewer measurement vectors for comparable error, while filter approximation limits high-SNR performance.

  • C. Effects of imperfect approximation of Rdd: Faster-varying gain sequences provide reasonable delay estimates with 50 measurement vectors, compared with 80 for slowly varying sequences.The comparison uses fd = 0.1/T versus fd = 0.05/T, with SNR=20dB and p = 4.
  • C. Effects of imperfect approximation of Rdd: The MSE depends on gain-sequence variation rate because faster variation makes each new measurement vector more informative for estimating Rdd.Increasing SNR or the number of sampling channels can further improve the estimation error.
  • D. Effects of imperfect digital filtering correction: At low SNRs noise dominates delay-estimation error, whereas at high SNRs correction-filter approximation becomes the main source of error.The experiment uses finite-length filters for a non-ideal band-pass sampling scheme.
  • D. Effects of imperfect digital filtering correction: 49-tap filters provide a good correction-filter approximation with a delay of 24 samples, while 11-tap filters are reasonable below 40dB SNR.These results quantify the trade-off between filter length and approximation error.
  • VIII. CONCLUSION: The overall method targets perfect recovery at rate 2K/T under appropriate sampling-filter conditions and recovers time-varying coefficients after identifying delays.The paper frames the problem as sampling an analog signal in an infinite union of subspaces.
Loading 0905.2429v3…