PaperlayerView exact revision on arXiv

Source-linked AI summary

Blind Multi-Band Signal Reconstruction: Compressed Sensing for Analog Signals

Moshe Mishali, Yonina C. Eldar

arXiv:0709.1563v1nlin.CGnlin.SI

TL;DR

The paper addresses multi-band reconstruction without known band locations. It develops a non-discretized, compressed-sensing formulation based on blind multi-coset sampling and establishes a blind sampling-rate bound. The proposed methods provide perfect or near-minimal-rate reconstruction over a broad class, with a special-case limitation for SBR2.

  • Problem

    Multi-band reconstruction methods require band-location information, leaving the sampling and reconstruction problem without a full blind scheme.

  • Method

    The paper assumes blind multi-coset sampling and uses a continuous-to-finite transformation to formulate reconstruction as a finite-dimensional compressed-sensing problem without discretization.

  • Results

    Twice the Landau rate is the lower bound for blind perfect reconstruction, while SBR2 approaches the minimal rate and SBR4 ensures perfect reconstruction for the class M.

  • Takeaways & Limitations

    The approach enables fully spectrum-blind sampling and reconstruction for a broad class of multi-band signals, including minimal-rate operation through SBR2.

  • Takeaways & Limitations

    SBR2 may fail for some very special signals in M, although the experiments also report a sampling-rate-below-bound case that neither algorithm can recover.

Abstract

from arXiv · show

We address the problem of reconstructing a multi-band signal from its sub-Nyquist point-wise samples. To date, all reconstruction methods proposed for this class of signals assumed knowledge of the band locations. In this paper, we develop a non-linear blind perfect reconstruction scheme for multi-band signals which does not require the band locations. Our approach assumes an existing blind multi-coset sampling method. The sparse structure of multi-band signals in the continuous frequency domain is used to replace the continuous reconstruction with a single finite dimensional problem without the need for discretization. The resulting problem can be formulated within the framework of compressed sensing, and thus can be solved efficiently using known tractable algorithms from this emerging area. We also develop a theoretical lower bound on the average sampling rate required for blind signal reconstruction, which is twice the minimal rate of known-spectrum recovery. Our method ensures perfect reconstruction for a wide class of signals sampled at the minimal rate. Numerical experiments are presented demonstrating blind sampling and reconstruction with minimal sampling rate.

I. INTRODUCTION

The paper develops spectrum-blind reconstruction for multi-band signals, removing the need for known band locations in sampling and reconstruction. It establishes a blind sampling-rate bound, introduces CTF-based compressed-sensing algorithms, and reports exact recovery near minimal rates for a broad signal class.

  • Motivation: Existing multi-band reconstruction methods use band-location information in both sampling and reconstruction, so they lack blindness.Blindness processes signals with different band locations in the same way.
  • Related work: Prior blind multi-coset sampling strategies broaden applicability, but their reconstruction designs still require spectral-support information.Earlier conference work mentioned spectrum-blind reconstruction without developing a full scheme.
  • Contributions: Twice the Landau rate is the lower bound for blind perfect reconstruction, and it is no greater than the Nyquist rate.The bound applies with arbitrary sampling and reconstruction.
  • Method: The CTF block converts continuous reconstruction into a finite-dimensional, non-discretized MMV sparsest-solution problem within compressed sensing.The block supports two spectrum-blind reconstruction algorithms.
  • Algorithms: SBR4 achieves perfect reconstruction at twice the minimal sampling rate, whereas SBR2 reaches the minimal rate using bisection and repeated CTF operations.Both algorithms can be implemented in DSP processors or software.
  • Results and scope: For the characterized class M, SBR4 guarantees perfect reconstruction, while SBR2 works for almost all signals and can indicate unsuccessful recovery.Experiments report satisfactory exact recovery near theoretical minimum rates and runtimes fast enough for practical usage.

II. PRELIMINARIES AND PROBLEM FORMULATION

The paper studies perfect reconstruction of multi-band signals from point-wise samples without using band locations, while seeking a sampling rate below Nyquist. It introduces blind sampling and reconstruction results for signals with bounded numbers and widths of bands.

  • B. Multi-band signals: The signal class M contains complex-valued signals bandlimited to [0, 1/T] with no more than N non-overlapping bands, each of width at most B.The corresponding Nyquist rate is 1/T.
  • B. Multi-band signals: Each band is a disjoint spectral interval represented by its edges [a_i, b_i].
  • C. Problem formulation: The reconstruction problem requires blindness: neither sampling nor reconstruction may use the band locations.The second constraint is achieving the required perfect-reconstruction sampling rate.
  • C. Problem formulation: Known band locations permit perfect reconstruction at Landau’s minimal rate, whereas uniform sampling permits blind reconstruction at the Nyquist rate.
  • C. Problem formulation: The paper develops a blind multi-coset sampling strategy and two reconstruction algorithms, SBR4 and SBR2.The strategy acquires samples at an average rate satisfying the blind minimal requirement.
  • C. Problem formulation: SBR4 guarantees perfect reconstruction for every signal in M at twice the minimal rate, while SBR2 uses the minimal rate for most signals.Some special signals in M cannot be perfectly reconstructed by SBR2.
  • III. MINIMAL SAMPLING RATE: Twice the Landau rate is the minimal rate for blind perfect reconstruction, while the Nyquist rate remains a valid blind upper case.The paper states that this lower bound applies to arbitrary sampling operators and that the multi-band class requires density 2NB.

B. Unknown spectrum support

For unknown spectrum support, the paper establishes a blind sampling lower bound and uses multi-coset sampling to approach it. The bound is twice the Landau rate, with exact recovery at the Nyquist rate in a stated high-occupation case.

  • B. Unknown spectrum support: A blind sampling set is designed without knowledge of supp X(f), and its samples must satisfy a stability condition.
  • B. Unknown spectrum support: Theorem 1 states a lower bound on the sampling density for blind sampling of signals with bandwidth occupation no more than Ω.
  • B. Unknown spectrum support: The paper extends prior union-of-subspaces results to arbitrary point-wise sampling operators, including non-periodic sampling sets.
  • B. Unknown spectrum support: When Ω > 0.5, uniform Nyquist-rate sampling with an ideal low-pass filter satisfies the blind reconstruction requirements for every x(t) ∈ M.
  • B. Unknown spectrum support: The blind lower bound is twice the Landau rate; for M, stable perfect reconstruction requires density 2NB.
  • B. Unknown spectrum support: The lower bounds alone do not construct an achieving method, motivating the paper’s multi-coset reconstruction development.
  • B. Unknown spectrum support: Multi-coset sampling divides the uniform grid into blocks of L samples and retains p positions specified by a fixed pattern C.The system is characterized by L, p, and C, with p sampling sequences shifted by the selected offsets.

B. Known-spectrum reconstruction and universality

Known-spectrum reconstruction uses prior knowledge of active band locations and universal sampling patterns to guarantee uniqueness. The blind setting removes that prior, introduces a factor-of-two sampling condition, and converts the recovery task into a finite-dimensional sparse problem.

  • Known-spectrum reconstruction and universality: For each frequency f, the measurement system is underdetermined, so recovery requires a prior on the unknown vector.
  • Known-spectrum reconstruction and universality: Known-spectrum reconstruction supplies the active band locations and restricts the sensing matrix to the corresponding columns.
  • Known-spectrum reconstruction and universality: A universal pattern makes the relevant matrix fully Kruskal-rank and supports recovery for every admissible signal.Choosing L prime makes every sampling pattern universal.
  • B. Reconstruction paradigm: The paper’s main result transforms the continuous reconstruction system into a finite-dimensional problem without discretization and develops two efficient blind algorithms.
  • B. Unknown spectrum support: Blind reconstruction replaces known band-location information with a prior based on sparsity without assuming the locations of nonzero values.
  • A. Conditions for blind perfect reconstruction: The blind sufficient condition differs from the known-spectrum condition by a factor of two because the nonzero locations are unknown.
  • B. Reconstruction paradigm: Directly finding a sparse solution independently for every continuous frequency is impractical, motivating the finite-dimensional reformulation.
  • A. Conditions for blind perfect reconstruction: Theorem 3 chooses L, p, and a universal pattern C from intrinsic signal parameters so the sparse solution is unique for every x(t) ∈ M.The conditions apply to both known and blind reconstruction, with the blind case differing by the factor of two.

B. Reconstruction paradigm

The reconstruction paradigm first identifies a diversity set describing the active components across frequency, then recovers the signal using sparse linear algebra. Under the paper’s parameter conditions, this recovery is unique and coincides with known-spectrum recovery once the set is found.

  • B. Reconstruction paradigm: The reconstruction goal is to recover x(t) from the p multi-coset sample sequences x_c_i[n].
  • B. Reconstruction paradigm: The method targets the diversity set S, which depends on x(t) and captures the indices of its nonzero components.
  • B. Reconstruction paradigm: The reformulated sparse system has a unique sparsest solution under the stated diversity-set condition.
  • B. Reconstruction paradigm: Once S is known and the matrix condition holds, equations (29)–(30) provide perfect reconstruction.
  • B. Reconstruction paradigm: For signals in M, the parameter selection implies |S| ≤ 2N; with p ≥ 2N and a universal pattern, the required matrix condition holds.
  • B. Reconstruction paradigm: After S is recovered, blind and known-spectrum reconstruction use the same recovery equations, although known support can permit fewer samples.

C. Formulation of a finite dimensional problem

The paper converts the continuous reconstruction problem over a frequency interval into a finite-dimensional sparse recovery problem. The resulting Continuous to Finite block determines the interval’s diversity set and supports the SBR algorithms.

  • The continuous equations form infinitely many linear systems because frequency is continuous.
  • The diversity set S is recovered exactly using a single finite-dimensional problem.
  • Under the stated matrix conditions, the sparse solution is unique, supporting exact recovery of the diversity set.
  • The CTF block determines the diversity set S_T for a given frequency interval T.
  • The CTF block transforms the continuous linear system on interval T into a finite-dimensional problem and then recovers S_T.
  • The finite-dimensional system is an MMV compressed-sensing problem whose sparsest solution matrix can be found with existing algorithms.

VI. SBR ALGORITHMS

The SBR algorithms use the finite-dimensional formulation to reconstruct blind multi-band signals. SBR4 provides a simpler twice-Landau-rate guarantee, while SBR2 targets the minimal rate with greater complexity.

  • SBR4: SBR4 guarantees perfect reconstruction for signals in A_K from samples at twice the Landau rate.
  • SBR4: SBR4 can compute its matrix in the time domain using filters designed independently of the signal.
  • SBR4: For the multi-band class M, SBR4 guarantees perfect reconstruction under L ≤ 1/B_T and p ≥ 4N.
  • SBR4: The corresponding minimal sampling rate is 4NB, twice the Landau rate NB for M.
  • SBR2: SBR2 exploits a larger diversity-set bound to regain the factor of two and achieve the minimal sampling rate.
  • SBR2: SBR2 has higher computational complexity than SBR4 because it uses a more complicated reconstruction method.

B. The SBR2 algorithm

SBR2 seeks the unknown frequency partition by applying the CTF block recursively to subintervals. The method can achieve minimal-rate perfect reconstruction theoretically, but has special-case and algorithmic limitations.

  • Minimal-rate construction: SBR2 targets the minimal sampling rate by reconstructing signals in a class whose Landau rate is K/L_T using p ≥ 2K.
  • Partition search: For multi-band signals with N bands, a partition into M = 2N + 1 intervals yields at most N active diversity elements per interval.
  • Partition search: The algorithm applies CTF to frequency intervals and uses bisection when an interval fails the required diversity-set condition.
  • Recovery guarantee: SBR2 guarantees perfect reconstruction for B_K ∩ A_2K at p = 2K, and the multi-band class M is contained in B_N when p ≥ 2N.
  • Limitations: SBR2 is sub-optimal because its estimated diversity set may differ from S, including when strict inequality holds on an interval.
  • Recovery guarantee: Theoretically, SBR2 guarantees perfect reconstruction for M at the minimal rate except for the discussed special cases.

1 MMV system

The section characterizes the computational role of MMV recovery within SBR2. Its practical behavior depends on both the bisection process and the selected MMV algorithm.

  • SBR2 complexity is determined by the number of bisection iterations and the behavior of the MMV algorithm used.
  • Numerical experiments show that SBR2 converges sufficiently fast for practical usage.
  • SBR2 does not provide a success indication for every signal in M because special signals cannot be identified in advance.

C. Comparison between SBR4 and SBR2

The section compares SBR4 and SBR2 in terms of sampling requirements, reconstruction guarantees, complexity, and empirical recovery. SBR2 generally supports broader signal classes and lower sampling rates, while SBR4 can offer lower complexity in some settings.

  • SBR2 guarantees perfect reconstruction for a wider signal set than SBR4, since AK is a true subset of BK ∩ A2K.Both algorithms can operate at the minimal sampling rate, but their guaranteed signal classes differ.
  • SBR4 requires twice the minimal sampling rate for signals in M, whereas SBR2 can achieve the minimal rate under sufficient conditions.For M, the sufficient conditions are p ≥ 4N for SBR4 and p ≥ 2N for SBR2.
  • For p < 2N, neither algorithm recovers the support set S because the sampling rate falls below the lower bound of Theorem 1.With L = 199 and N = 4, the empirical experiments show failure below this threshold.
  • SBR2 outperforms SBR4 by achieving the same empirical success rate at a lower average sampling rate.At p = 4N, the sampling rate is slightly more than four times the Landau rate, while SBR4 maintains a high recovery rate.
  • With L = 23, p = N = 4 gives a 3.4 GHz sampling rate, while the minimal-rate requirement holds only for p ≥ 2N.The smaller L is presented as a practical choice because realizing multi-coset sampling requires p analog-to-digital devices.
  • Increasing p can reduce computational cost: SBR2 runtime rises near the minimal rate, while SBR4 may be preferred at p = 4N because runtime improves.The complexity trade-off reflects the growing difficulty of finding a suitable partition set D near the minimal sampling rate.

C. Applicability

The proposed SBR methods are evaluated on signals inside and outside their designated model classes, with experiments examining recovery, sampling-rate trade-offs, and sampling-pattern universality. The paper concludes that the approach supports spectrum-blind reconstruction without discretization and can approach the blind lower bound for a broad class of multi-band signals.

  • Experiments: The experiments test SBR4 and SBR2 on signals both within and outside their respective model classes.Signals outside M are constructed to satisfy the test conditions for SBR4 or SBR2 while remaining outside M.
  • Recovery performance: 1608 MHz, twice the Landau rate, serves as a threshold for satisfactory recovery in one experiment.SBR4 performs better than SBR2 because it avoids a sub-optimal partition-set recovery stage; both remain affected by MMV sub-optimality.
  • Recovery performance: For generic signals outside M, the model-set membership and uniqueness guarantees cannot be determined reliably from the samples.The uniqueness guarantee applies only when x(t) belongs to A_K, which is not ensured for a generic multi-band signal.
  • Sampling patterns: A universal sampling pattern is crucial: the tested non-universal pattern failed to recover any of 1000 test cases.Random patterns can be used practically for sufficiently large L and p, and the random selection is performed only once for all tested signals.
  • Conclusions: The numerical experiments demonstrate a trade-off between average sampling rate and empirical reconstruction success rate.The conclusion also states that one proposed algorithm approaches the minimal blind sampling rate for a wide class of multi-band signals.
  • Conclusions: The reconstruction problem is formulated as a finite-dimensional compressed-sensing problem without discretization, enabling sampling and reconstruction without band-location knowledge.The method uses conditions and algorithms based on theoretical results from compressed sensing.

APPENDIX A

The appendix extends the framework to real-valued multi-band signals and details the associated frequency-domain and time-domain constructions. It also describes how the sampling filters are selected independently of the signal.

  • Real-valued signals: The appendix extends the results to real-valued multi-band signals using conjugate-symmetric spectral definitions.For these signals, the Nyquist rate remains 1/T and the Landau rate is NB.
  • Real-valued signals: For real-valued signals, the spectrum contains no more than N bands on both sides, with each band width bounded by B.N is even because the Fourier transform is conjugate symmetric.
  • Frequency-domain construction: The appendix modifies the frequency-domain construction by dividing the frequency interval into L equal intervals and treating odd and even L separately.The distinction accounts for the negative-frequency side of the spectrum.
  • Frequency-domain construction: The proof establishes full column rank through rank-preserving column reordering and properties of matrix concatenation and multiplication.This supports the stated sparse-recovery condition involving the matrix construction.
  • Time-domain implementation: The SBR4 algorithm computes the required matrix directly from time-domain samples using DTFT relationships and zero-padded sample sequences.The appendix also defines the sinc function used in the derivation.
  • Time-domain implementation: The digital filters are designed after choosing L, p, and C and do not depend on the signal.This permits filter design before processing individual signals.
Loading 0709.1563v1…