PaperlayerView exact revision on arXiv

Source-linked AI summary

Beyond Nyquist: Efficient Sampling of Sparse Bandlimited Signals

Joel A. Tropp, Jason N. Laska, Marco F. Duarte, Justin K. Romberg, Richard G. Baraniuk

arXiv:0902.0026v2cs.IT

TL;DR

Wideband signals can exceed practical Nyquist-rate conversion limits even when only a few frequencies are significant. The paper introduces a random demodulator that mixes, filters, and undersamples such signals, then uses nonlinear recovery. Simulations indicate O(K log(W/K)) samples per second, while theory provides broader recovery guarantees and robustness results.

  • Problem

    Nyquist-rate sampling is inefficient for wideband signals whose significant frequency components are sparse, while practical ADC speed and power constraints limit conventional conversion.

  • Method

    The random demodulator multiplies the signal by a high-rate pseudonoise sequence, applies a lowpass anti-aliasing filter, and samples at a low rate for nonlinear sparse recovery.

  • Results

    O(K log(W/K)) Hz suffices in simulations, while theoretical results establish recovery for arbitrary K-tone signals, approximately sparse spectra, and noise and quantization errors.

  • Takeaways & Limitations

    The random demodulator offers an alternative to Nyquist-rate sampling for sparse signals using lower-rate analog hardware and additional digital processing.

Abstract

from arXiv · show

Wideband analog signals push contemporary analog-to-digital conversion systems to their performance limits. In many applications, however, sampling at the Nyquist rate is inefficient because the signals of interest contain only a small number of significant frequencies relative to the bandlimit, although the locations of the frequencies may not be known a priori. For this type of sparse signal, other sampling strategies are possible. This paper describes a new type of data acquisition system, called a random demodulator, that is constructed from robust, readily available components. Let K denote the total number of frequencies in the signal, and let W denote its bandlimit in Hz. Simulations suggest that the random demodulator requires just O(K log(W/K)) samples per second to stably reconstruct the signal. This sampling rate is exponentially lower than the Nyquist rate of W Hz. In contrast with Nyquist sampling, one must use nonlinear methods, such as convex programming, to recover the signal from the samples taken by the random demodulator. This paper provides a detailed theoretical analysis of the system's performance that supports the empirical observations.

I. INTRODUCTION

The paper addresses the limits of Nyquist-rate conversion for wideband signals by exploiting sparse frequency content with a random demodulator. The system lowers analog sampling demands, but requires nonlinear recovery and is supported by simulations and theoretical analysis.

  • Large bandlimits make Nyquist-rate sampling impractical for emerging applications because current hardware cannot meet the required speed and power constraints.
  • Sparse signals contain far fewer significant tones than the bandlimit permits, providing leverage for sampling below the Nyquist rate.
  • The random demodulator multiplies the signal by a high-rate pseudonoise sequence, lowpass-filters the result, and samples it at a relatively low rate.
  • Each input frequency receives a distinct output signature, helping distinguish tones after demodulation and lowpass filtering.
  • The slower sampling rate shifts burden to nonlinear, computationally intensive signal recovery, while theoretical results support recovery beyond perfectly sparse random signals.
  • O(K log(W/K)) Hz suffices in simulations for high-probability reconstruction, compared with W Hz for conventional sampling.

C. Examples

The paper presents sparse wideband signals as common in communications, acoustics, radar, and other applications, then explains how the random demodulator acquires them through randomized demodulation and low-rate sampling.

  • Examples: Sparse or locally sparse frequency content appears in communications, acoustic, chirp, smooth, and piecewise smooth signals.Examples include frequency hopping, musical harmonics, slowly varying chirps, few Fourier coefficients, and step discontinuities.
  • Examples: Surveillance, cognitive radio, and geophysical imaging are identified as potential applications for sparse wideband acquisition.The paper specifically connects spectrum sensing to unoccupied frequency regions in cognitive radio.
  • System design: The random demodulator multiplies the input by a high-rate random square wave, smearing each tone across the spectrum into a detectable signature.Distinct translated noise spectra allow tones to be disentangled from a small spectral slice.
  • System design: Lowpass filtering prevents aliasing before a low-rate ADC captures coded samples that represent the original sparse signal.The implementation uses integrate-and-dump sampling and does not model final quantization.
  • System design: The sampling rate R is much lower than the Nyquist rate W and depends primarily on the number K of significant frequencies.The hardware combines demodulation, filtering, low-rate sampling, and quantization; the mixer still operates at W.
  • Implementation: Pseudorandom sequences, polarity-reversing mixers, off-the-shelf ADCs, and accurately characterized filtering support a robust hardware implementation.The system remains robust to hardware nonidealities, but end-to-end calibration is required so reconstruction algorithms account for them.

B. Action of the Demodulator

The random demodulator is modeled as a matrix system that applies random sign modulation and accumulate-and-dump sampling, after which sparse recovery reconstructs the signal through nonlinear optimization.

  • Matrix model: The discrete signal is represented as x, and demodulation multiplies each entry by a random sign through the diagonal matrix D.The signs ε_n take values ±1 with equal probability.
  • Matrix model: The accumulate-and-dump sampler is represented by an R × W matrix H whose rows sum consecutive demodulated entries.When R does not divide W, fractional matrix elements approximate shared contributions between samples.
  • Matrix model: The hardware action is M = HD, with each row producing one sample, while Φ = MF maps the amplitude vector s to the acquired samples.The matrix Φ is called the random demodulator matrix.
  • Signal recovery: The output cannot be inverted by a linear reconstruction because recovery must incorporate the signal’s sparsity constraint.The paper therefore formulates recovery as finding a sparse amplitude vector consistent with the measurements.
  • Convex relaxation: Convex relaxation replaces the computationally difficult ℓ0 objective with the ℓ1 norm, whose constrained minimization is solvable in polynomial time.The resulting optimization searches for a measurement-consistent vector with minimum ℓ1 norm, promoting sparsity.
  • Algorithmic trade-offs: The paper focuses on convex relaxation because it is more amenable to theoretical analysis, while additional algorithmic research is needed for practical viability.Greedy pursuit can be attractive for large-scale problems because of its computational profile, whereas convex relaxation is usually more powerful outside ultra-sparse settings.
  • Algorithmic trade-offs: Convex programming methods are reported to achieve strong reconstructions, with first-order methods potentially offering similar performance at lower computational overhead.Second-order methods are described as effective for signals with wide dynamic range.

C. Impact of Noise

The experiments characterize reconstruction thresholds for random demodulation across bandwidth, sparsity, and sampling efficiency. They find logarithmic growth with bandwidth, a close empirical fit, and graceful degradation for a communication signal as SNR decreases.

  • C. Impact of Noise: Modern convex relaxation and greedy pursuit methods are described as robust to compressibility, hardware noise, and quantization.The paper distinguishes compressible signals from exactly sparse signals and notes that practical hardware introduces noisy, quantized measurements.
  • C. Impact of Noise: Noise in compressive sampling inevitably decreases the signal-to-noise ratio when signal information is compressed into fewer samples.The paper identifies this SNR reduction as a central design issue for compressive sampling systems.
  • C. Performance Results: R = 1.71K log(W/K + 1) + 1.00 is the empirical trend when sparsity varies at fixed W = 512 Hz.The fitted line gives a close fit for data spanning K from 1 to 64.
  • C. Performance Results: For fixed sparsity, the sampling rate grows only logarithmically as the Nyquist rate increases.The experiments vary W with K = 5 and fit R = 1.69K log(W/K + 1) + 4.51; variation is attributed probably to arithmetic effects when R does not divide W.
  • C. Performance Results: The success threshold is evaluated over compression factor R/W and sampling efficiency K/R, with a 99% success isocline and a Gaussian-matrix theoretical threshold.Figure 6 encodes success probability by pixel shade; the dashed boundary marks where success drops below 99%.
  • D. Example: Analog Demodulation: Communication-signal reconstruction achieves SNRs of 27.8 dB, 22.3 dB, and 20.9 dB at sampling rates of 16 KHz, 8 KHz, and 3.2 KHz.The reported performance degrades gracefully as SNR decreases, but the system requires a sampling rate above the phase transition.

VII. THEORETICAL RECOVERY RESULTS

Theoretical results support recovery by the random demodulator for random sparse signals and extend the guarantee to arbitrary noisy or nonsparse signals under stronger sampling conditions.

  • A. Recovery of Random Signals: High-probability recovery of random sparse signals follows when the convex program returns the original amplitude vector, except with probability O(W^-1).The theorem assumes a random amplitude vector, a random demodulator matrix, and R dividing W.
  • A. Recovery of Random Signals: The sampling rate scales linearly with sparsity K and logarithmically with bandlimit W, supporting the empirical sampling rule.The analysis does not provide a reasonable estimate for the leading constant.
  • A. Recovery of Random Signals: A small startup cost may require a minimal number of measurements before the demodulator system becomes effective.The experiments were not refined enough to determine whether this startup cost occurs in practice.
  • B. Uniformity and Stability: The random-signal theorem is limited by artificial random tone locations, imperfect spectral sparsity, and hardware nonidealities that contaminate samples with noise.These shortcomings motivate uniform and stable recovery for all signals, including noisy and approximately sparse inputs.
  • B. Uniformity and Stability: For arbitrary amplitude vectors and bounded noise, Theorem 2 provides approximation recovery through convex programming, with quality tied to the best K-sparse approximation.When the signal is K-sparse, the relevant approximation term vanishes and perfect recovery remains possible.
  • B. Uniformity and Stability: The general-signal theorem increases the sampling rate by several logarithmic factors, some of which may be artifacts of the proof techniques.The authors conjecture that practical requirements may be closer to R ≥ C K log^2 W, but this conjecture exceeds current techniques.
  • B. Uniformity and Stability: Compressible signals are effective targets because their recovery error is comparable with the ℓ2 norm of their tail.This supports efficiency when the amplitude vector is well approximated by a sparse vector.

C. Extension to Bounded Orthobases

The paper extends the random demodulator beyond periodic frequency-sparse signals by using windowing to make nonharmonic and multiband signals compressible.

  • C. Extension to Bounded Orthobases: The recovery theory extends to sparsity bases incoherent with the Dirac basis, provided the basis matrix has small-magnitude entries.This identifies incoherence, rather than a specific Fourier representation, as the crucial structural feature.
  • C. Extension to Bounded Orthobases: Windowing replaces a nonharmonic signal f with g = ψ · f, enabling approximation by a periodic multitone signal.The window ψ vanishes outside [0, 1).
  • C. Extension to Bounded Orthobases: A smoother window yields faster approximation decay, requiring about ε^-1/(r-1/2) harmonic terms for tolerance ε.This holds when the Fourier transform of the window decays like ω^-r for r ≥ 1.
  • C. Extension to Bounded Orthobases: For multiple nonharmonic sinusoids, the number of harmonic tones needed scales linearly with the number of sinusoids.The windowed signal is compressible in the sense used by the recovery theory.
  • C. Extension to Bounded Orthobases: A bandlimited signal occupying an interval of length B can be approximated using about B + ε^-1/(r-1/2) multitone terms.For multiband signals, the required number of tones scales linearly with total bandwidth.
  • C. Extension to Bounded Orthobases: Reconstructing a long-duration signal uses overlapping shifted windows whose individual reconstructions are added together.The implementation requires a time-varying-gain amplifier and two parallel random-demodulator channels for overlapping windows.
  • A. SNR Performance: The random demodulator can outperform a standard ADC in ENOB when the input is spectrally sparse, but the improvement depends on sparsity.Figure 8 varies bandlimit W at fixed K and varies sparsity K at fixed W; standard ADC performance does not depend on K.
  • A. SNR Performance: Estimated SNR gains omit upstream hardware degradations such as multiplier nonlinearity and pseudorandom-signal jitter.High-quality components are therefore critical to the design.

B. Power Consumption

The random demodulator trades some ENOB for lower power, storage, and communication demands, while its recovery computation may be substantial but parallelizable.

  • B. Power Consumption: Replacing the ADC sampling rate with the acquisition bandlimit in a power figure of merit shows a potential power advantage for the random demodulator.The system incurs an ENOB penalty for a given signal but may require significantly less power as W grows.
  • C. Computational Resources Needed for Signal Recovery: The random demodulator’s computational cost is dominated by repeated applications of its system matrix and transpose, especially FFT operations.The matrix consists of a Fourier transform, pointwise multiplication, and block sums.
  • C. Computational Resources Needed for Signal Recovery: About 13 million 16K-point FFTs per second would be needed for a back-end producing 2^30 samples per second under the stated assumptions.The estimate assumes blocks of size 2^14 and 200 FFTs per block.
  • C. Computational Resources Needed for Signal Recovery: A nominal 200-second processing cost for 2^16 blocks can be reduced substantially through parallel or multicore architectures.The estimate is substantial but described as not entirely unrealistic.
  • B. Power Consumption: The collected samples automatically compress sparse signals, reducing storage, communication, post-sampling processing, hardware complexity, and power consumption.No additional compression processing is required after sampling.
  • B. Power Consumption: The system may enable high-bandwidth acquisition and more favorable size, weight, and power profiles, although some applications remain years away.The high-bandwidth applications still require high-performance analog and digital signal processing.
  • B. Power Consumption: Compared with nonuniform sampling, the random demodulator uses a uniform clock and an integrator that lowers the ADC input bandwidth, reducing timing-jitter sensitivity.The paper also reports higher measurement SNR than nonuniform sampling for the same number of samples.

APPENDIX I THE RANDOM DEMODULATOR MATRIX

The appendix characterizes the random demodulator matrix and develops probabilistic tools used to establish bounds on its entries and recovery behavior.

  • Notation and Probabilistic Tools: The appendix introduces norms, expectation notation, probability notation, and universal-constant conventions used throughout the matrix analysis.It also defines the spectral, Frobenius, and maximum-entry matrix norms.
  • Probabilistic Tools: Moment bounds for maxima, Rademacher series, symmetrization, and Khintchine’s inequality provide the probabilistic machinery for the proofs.These tools control sums of independent random variables and maxima of random quantities.
  • Matrix Structure: The random demodulator matrix Φ is analyzed under the simplifying assumption that sampling rate R divides bandlimit W.The matrix is represented through Fourier, chipping, and block-summing factors.
  • Matrix Structure: The Fourier factor is unitary with entries of magnitude W^-1/2, while the diagonal chipping matrix is unitary with entries ±1.The chipping sequence is modeled as a Rademacher sequence.
  • Matrix Structure: The block-summing matrix H has 0–1 entries, with each row containing a contiguous block of W/R ones and orthogonal rows.The index relation j ∼ r identifies which entries belong to each block.
  • Entry Bounds: A key lemma bounds the maximum entries of Φ with high probability, a property repeatedly used in subsequent arguments.The proof treats each entry as a Rademacher series and applies moment inequalities.

E. The Gram Matrix

The analysis studies the Gram matrix of the random demodulator through random-chaos bounds, ultimately obtaining a high-probability uniform control of its entries.

  • The Gram matrix Φ∗Φ tabulates inner products among the demodulator columns, linking matrix estimates to column correlations.
  • The analysis rewrites the relevant chaos symmetrically and separates its real and imaginary parts before applying decoupling.
  • Uniform norm bounds hold over all frequency pairs, and the auxiliary matrix B satisfies identical bounds.
  • The chaos is subgaussian for moderate deviations but has subexponential tails for larger deviations.
  • A tail bound is obtained by combining moment estimates with Markov’s inequality.

F. Column Norms and Coherence

The paper shows that random demodulator columns are nearly normalized and have low coherence, two properties used to analyze sparse recovery.

  • Lemma 6 implies that the columns of Φ essentially have unit norm.
  • Theorem 8 establishes a column-norm bound under a sampling-rate condition.
  • Coherence µ measures the maximum inner product between distinct columns of Φ.
  • Theorem 9 provides a probabilistic bound on coherence when R ≥2 log W.
  • Because the columns are essentially normalized, the random demodulator’s coherence is nearly as small as possible.

A. Cumulative Coherence

The analysis develops cumulative-coherence bounds for random coordinate sets, overcoming the inadequate estimate based only on pairwise coherence and establishing conditioning results for random submatrices.

  • Theorem 11 gives a cumulative-coherence bound for a random K-coordinate set under a sampling-rate condition.
  • Pairwise coherence alone gives a completely inadequate bound for cumulative coherence.
  • Cumulative coherence is controlled by the maximum column norm of the hollow Gram matrix G.
  • Randomly selecting coordinates enables an improved estimate of cumulative coherence through a projector bound and decoupling argument.
  • The proof combines column-norm, coherence, projector, moment, and Markov bounds, with an intermediate conditional expectation bounded by 0.3.
  • Theorem 13 establishes conditioning control for a random K-column submatrix of the random demodulator.

C. Recovery of Random Signals

The paper analyzes recovery of random sparse signals through ℓ1 minimization and derives high-probability recovery results from structural properties of the random demodulator matrix.

  • The analysis uses cumulative coherence and conditioning bounds to verify the conditions required for ℓ1 minimization.
  • Theorem 1 follows as a corollary of the preceding recovery result under the stated sampling-rate condition.
  • For random signals with uniformly distributed nonzero phases, the convex program recovers s except with probability 8W −1.
  • The recovery program minimizes ∥v∥1 subject to Φv = Φs to recover the sparse amplitude vector s.
  • The RIP preserves sparse-vector norms up to a small factor and supports recovery from a small number of samples.

B. RIP for Random Demodulator

The paper establishes that the random demodulator matrix satisfies the restricted isometry property under an appropriate sampling rate. The proof combines identity-like Gram-matrix behavior, independent rows, bounded entries, and concentration arguments.

  • The random demodulator matrix has the restricted isometry property when the sampling rate is chosen appropriately.
  • An R × W random demodulator matrix has RIP of order N with constant δ_N ≤ δ except with probability O(W^-1).
  • The RIP proof relies on a Gram matrix that averages to the identity, independent rows, and uniformly bounded entries.
  • The analysis uses concentration inequalities for sums of independent, symmetric, bounded Banach-space-valued random variables.
  • The proof controls matrix deviations through symmetrization, truncation, and tail bounds before completing the RIP argument.

C. Signal Recovery under the RIP

Under the RIP, convex optimization can recover sparse or compressible signals from noisy random-demodulator measurements. Combining the recovery guarantee with the RIP theorem yields the paper’s main signal-recovery result.

  • RIP measurements contain enough information to approximate general signals, and convex optimization can perform the recovery.
  • Every solution to the stated optimization problem approximates the target signal when the measurement noise satisfies ∥ν∥_2 ≤ η.
  • The approximation guarantee is measured relative to s_K, the best K-sparse approximation to s in the ℓ1 norm.
  • CoSaMP provides an equivalent recovery guarantee for computing the approximation.
  • Combining the RIP theorem with the recovery proposition produces the paper’s major result, Theorem 2.
  • An R × W random demodulator matrix satisfies RIP of order 2K with constant δ_2K ≤ c except with probability O(W^-1).
Loading 0902.0026v2…