PaperlayerView exact revision on arXiv

Source-linked AI summary

Compressed Sensing of Analog Signals in Shift-Invariant Spaces

Yonina C. Eldar

arXiv:0806.3332v2cs.IT

TL;DR

The paper addresses low-rate sampling of continuous-time signals in shift-invariant spaces when only an unknown subset of generators is active. It combines analog sampling with a continuous-to-finite reformulation and compressed sensing, showing that stable recovery can use 2k ≤ p < m uniform sequences at rate 1/T.

  • Problem

    The paper studies how to sample signals generated by k of m shift-invariant generators when the active generators are unknown, unlike standard compressed sensing's finite-vector setting.

  • Method

    The approach combines analog sampling results with a continuous-to-finite block that converts the infinite sparse problem into a finite counterpart for compressed-sensing algorithms.

  • Results

    2k ≤ p < m uniform sequences sampled at rate 1/T suffice for signals with k active generators.

  • Takeaways & Limitations

    The framework extends compressed-sensing methods to analog SI signals without requiring an underlying finite-dimensional model.

Abstract

from arXiv · show

A traditional assumption underlying most data converters is that the signal should be sampled at a rate exceeding twice the highest frequency. This statement is based on a worst-case scenario in which the signal occupies the entire available bandwidth. In practice, many signals are sparse so that only part of the bandwidth is used. In this paper, we develop methods for low-rate sampling of continuous-time sparse signals in shift-invariant (SI) spaces, generated by m kernels with period T. We model sparsity by treating the case in which only k out of the m generators are active, however, we do not know which k are chosen. We show how to sample such signals at a rate much lower than m/T, which is the minimal sampling rate without exploiting sparsity. Our approach combines ideas from analog sampling in a subspace with a recently developed block diagram that converts an infinite set of sparse equations to a finite counterpart. Using these two components we formulate our problem within the framework of finite compressed sensing (CS) and then rely on algorithms developed in that context. The distinguishing feature of our results is that in contrast to standard CS, which treats finite-length vectors, we consider sampling of analog signals for which no underlying finite-dimensional model exists. The proposed framework allows to extend much of the recent literature on CS to the analog domain.

I. INTRODUCTION

The paper develops direct low-rate sampling methods for continuous-time sparse signals in shift-invariant spaces, where only an unknown subset of generators is active. It connects analog sampling with compressed sensing to obtain stable recovery below the conventional m/T rate.

  • Shift-invariant spaces represent broad signal classes as combinations of shifted generators, including bandlimited functions, splines, pulse amplitude modulation, and multiband signals.
  • m filter outputs sampled every T recover general signals in an SI space at total rate m/T, while known active generators reduce the required rate to k/T.The k/T rate assumes the active subset is known in advance.
  • The central problem is sampling signals generated by only k of m generators when the active subset is unknown, potentially requiring rates below m/T.This setting is a union of subspaces because each possible generator subset defines a different subspace.
  • Unlike standard compressed sensing, the paper targets continuous signals with infinitely many parameters and avoids first acquiring Nyquist-rate samples for finite-dimensional processing.Standard CS algorithms cannot be directly applied to infinite-dimensional sequences without discretization or heuristics.
  • The approach combines analog sampling theory, the continuous-to-finite block, and standard CS to reformulate the analog problem as a finite counterpart solvable with tractable algorithms.The continuous-to-finite operation transforms the continuous reconstruction problem without discretization or heuristics.
  • 2k ≤ p < m uniform sequences sampled at rate 1/T suffice when k of m generators are active, with p selected according to standard CS requirements.The resulting rate is much lower than m/T while supporting stable recovery in the stated SI model.

II. BACKGROUND: SAMPLING IN SI SPACES

Signals in finitely generated shift-invariant spaces can be represented through generator coefficients and recovered from uniformly sampled filter outputs under stable invertibility conditions. With m generators, the standard scheme uses m sampling sequences at rate 1/T, matching the signal’s m degrees of freedom per interval T.

  • A finitely generated shift-invariant space represents signals using m generator functions shifted with period T.
  • Signals in these spaces are sampled by filtering with m filters and uniformly sampling each output at times nT.
  • The sample sequences and expansion-coefficient sequences are related in the Fourier domain through a matrix-valued cross-correlation system.
  • Perfect recovery follows when the sampling matrix MSA(ejω) is invertible almost everywhere, with stable recovery requiring αI ⪯ MSA(ejω) ⪯ βI.
  • m sampling sequences at rate 1/T produce an average sampling rate of m/T, matching m new signal parameters over every interval of length T.

III. UNION OF SHIFT-INVARIANT SUBSPACES

The paper considers signals formed from only k of m possible shift-invariant generators when the active subspaces are unknown. This uncertainty raises the sampling requirement relative to the known-subspace case, motivating recovery from 2k ≤ p < m sampling sequences.

  • Unknown active generators place the signal in a union of subspaces formed by choosing k of m possible generator subspaces.
  • When the active generators are known, filtering with k corresponding filters yields an average sampling rate of k/T.
  • Without knowledge of the active subspaces, sampling all m filter outputs gives rate m/T but increases the sampling burden.
  • Uniqueness requires a minimal rate of at least 2k/T, so unknown subspace selection increases the minimal rate by at least a factor of two.
  • The paper’s goal is to recover the analog signal from 2k ≤ p < m sampling sequences obtained by sampling p filter outputs at rate 1/T.

A. Compressed Sensing

Finite compressed sensing recovers sparse vectors from underdetermined measurements by exploiting a union-of-subspaces prior, but the analog problem must handle infinitely many coefficient parameters. The paper connects these settings through matrix conditions and sparse-recovery algorithms.

  • Finite compressed sensing seeks to recover a length-m vector from p < m linear measurements using a sparse representation.
  • A k-sparse prior models the unknown vector as x = Φα, where α has at most k nonzero entries and each support defines a subspace.
  • A Kruskal-rank of at least 2k for A = MΦ is sufficient for uniqueness of the sparse solution.
  • Although 2k measurements can yield exact recovery without stability or computational-complexity requirements, the corresponding optimization is NP-hard.
  • For random Fourier measurements, ℓ1 recovery succeeds with overwhelming probability when p ≥ ck log m, while related MMV models recover matrices with at most k nonzero rows.

B. Compressed Sensing of Analog Signals

The paper frames analog compressed sensing as recovery of sparse continuous-time signals without discretization, while direct operator extensions of finite-dimensional CS create infinite-dimensional obstacles. It addresses these obstacles by combining Fourier-domain sample analysis with sampling functions that produce an IMV model.

  • Problem: Analog CS seeks to sense sparse continuous-time signals with fewer measurements, but the underlying problem remains infinite-dimensional.The signal is represented using an infinite sequence and operator rather than a finite vector and matrix.
  • Problem: Directly replacing finite CS matrices with operators creates infinite sparsity, unclear operator dimensions, and recovery problems.The resulting convex formulation can involve infinitely many variables and constraints, beyond standard finite-dimensional optimization tools.
  • Problem: The paper identifies three design questions: choosing an analog sampling operator, preserving stability under structure, and solving infinite-dimensional recovery.These questions organize the adaptation of CS results to analog sampling.
  • Approach: Two elements enable the proposed analog CS framework: Fourier-domain analysis of sample sequences and sampling functions that yield an IMV model.The approach extends these elements from blind multiband sampling to the general SI setting.
  • Approach: The resulting design uses p < m sampling filters and finite-dimensional CS ideas to address analog sampling without discretization or heuristics.The sampling filters are chosen so the resulting samples can be described by an IMV system.

IV. INFINITE MEASUREMENT MODEL

The IMV model represents infinitely many measurement equations whose unknown vectors share a joint support. A continuous-to-finite reduction identifies that support through one finite MMV problem, after which the signals can be recovered exactly under the stated rank condition.

  • IMV model: The IMV model recovers infinitely many unknown vectors that share a fixed joint sparsity pattern.The support contains at most k active locations across the vector family.
  • IMV model: If σ(A) ≥2k, the IMV solution is the unique k-sparse solution of the measurement equations.The condition makes the active columns sufficiently independent for uniqueness.
  • Recovery: Recovery proceeds in two steps: identify the joint support S, then reconstruct the vectors using the measurements and known support.Once S is known, the restricted matrix A_S and its pseudoinverse provide exact recovery.
  • Recovery: The continuous-to-finite block replaces the infinite IMV structure with a finite MMV system while preserving the support-recovery task.A finite collection spanning span(y(Λ)) contains sufficient information to recover S.
  • Recovery: A matrix V constructed from the measurement span supports the finite reduction when the required integral exists.Every V satisfying Q = VV^H has column span equal to span(y(Λ)).

V. COMPRESSED SENSING OF SI SIGNALS

The SI sampling strategy combines a finite CS matrix with an analog filter bank to compressively measure the active generator sequences. The resulting IMV system permits perfect or high-probability recovery according to the chosen matrix A.

  • Sampling design: The proposed SI strategy filters x(t) with p < m functions and uniformly samples the outputs at rate 1/T.The filter design combines a discrete CS matrix with functions that sample and reconstruct the generators.
  • Sampling design: The matrix A is selected from a finite CS problem recovering a k-sparse length-m vector from p measurements.Exact combinatorial recovery can use p ≥2k, while efficient recovery may require p > 2k.
  • Recovery: The construction compressively measures the sequence d[n], whose at most k nonzero component sequences share a joint support.IMV recovery theory is used to recover d[n] from measurements generated by A.
  • Recovery: An analog filter bank first obtains d[n] from x(t), and the two stages are merged into p < m direct analog filters.The merged filters directly compressively sample the continuous-time signal.
  • Recovery: Because A determines the IMV recovery properties, d[n] can be perfectly recovered or recovered with high probability for each n when the corresponding CS conditions hold.The recovery algorithm reduces the infinite sequence problem through an equivalent MMV formulation.
  • Implementation: An invertible frequency-dependent matrix W(e^jω) provides additional freedom in choosing implementable sampling functions.The paper gives an example where selecting W(e^jω) produces analog sampling functions that are easy to implement.

B. Biorthogonal Expansion

The section constructs biorthogonal sampling functions that recover coefficient sequences from analog signals, then connects those sequences to compressed measurements.

  • Sampling x(t) with m filters and uniformly sampling their outputs produces the coefficient sequences needed for recovery.
  • Filtering x(t) with the biorthogonal filters and sampling at times nT obtains the inner products required by the coefficient expansion.
  • The identity MV A(e^jω) = I verifies that the constructed filters recover the desired sequences.
  • A set of filters hℓ(t) with stably invertible MHA(e^jω) yields biorthogonal functions vℓ(t) through the inverse filter-bank construction.The resulting functions satisfy the biorthogonality relation with the generator shifts.
  • Different analog filters spanning the same space produce the same sampling functions, although their hardware implementations differ.The distinction arises because hℓ(t) is an analog filter while MHA(e^jω) is a discrete-time filter bank.

C. CS of Analog Signals

The paper combines an analog front end with discrete compressed sensing so that compressed measurements can be acquired directly from x(t) at rate p/T.

  • The initial compressed measurements remain costly because they are produced by an analog front end operating at the high rate m/T.
  • Filtering x(t) with p filters sℓ(t) and sampling at times nT produces measurement sequences at rate p/T.
  • Theorem 2 constructs p sampling functions from a CS matrix A, filters h_i(t), and an invertible filter bank, enabling direct analog compression.
  • The compressed measurements are processed by the CTF block to recover the coefficient sequences d_i[n], after which the original signal is reconstructed with the generators a_i(t).
  • The framework combines biorthogonal sampling, a conventional CS mixing matrix, and CTF recovery in either time or frequency.

VI. EXAMPLES

The examples show how periodic sparsity in shift-invariant signals can be exploited to reduce the analog sampling rate below the rate required by direct coefficient acquisition.

  • The model represents periodic sparsity by grouping coefficients into length-m blocks whose vectors are jointly k-sparse.
  • Standard compressed sensing of coefficient sequences reduces only the discrete-time rate, while the analog sampling rate remains at the Nyquist rate.
  • Theorem 2 enables p < m sampling functions that mix coefficient values before integration, avoiding acquisition of zero coefficients.
  • The resulting analog sampling rate is p/T = p/(mT′) < 1/T′ when the CS matrix satisfies the required conditions.
  • For a piecewise-constant generator, the construction integrates weighted groups of m intervals and recovers d[n] through the CTF block.

B. Multiband Sampling

The multiband example embeds occupied frequency intervals into the shift-invariant model and uses the framework to generate stable low-rate sampling strategies.

  • A multiband signal with at most N occupied bands can be represented by at most 2N nonzero generator sequences.
  • When band locations are known, the framework yields recovery rates below Nyquist, including the stated average rate NB/(2π).
  • Choosing h_i(t) = a_i(t) gives MHA(e^jω) = I because the generators are orthonormal.
  • A particular choice of A and W(e^jω) reproduces the sampling strategy of, while other choices yield alternative sampling functions.
  • The framework extends the specific multiband strategy by identifying more general sampling methods with stable recovery.

VII. CONCLUSION

The paper develops a framework for sampling sparse analog signals in shift-invariant spaces by converting an infinite-dimensional problem into a finite compressed-sensing formulation. It connects compressed sensing of finite-dimensional vectors with traditional sampling of continuous-time signals and identifies hardware architectures as future work.

  • The framework targets sparse signals in shift-invariant spaces generated by m kernels, with only k active generators whose identities are unknown.
  • The approach combines analog sampling ideas with biorthogonal sampling sets and the CTF block to convert the infinite-dimensional problem into a finite MMV compressed-sensing problem.
  • The resulting formulation enables the use of compressed-sensing methods previously developed for finite-dimensional problems.
  • The paper focuses on sampling with a bank of analog filters, while extending the approach to other hardware-friendly sampling architectures remains future work.
  • The work aims to bridge compressed sensing of finite-dimensional vectors and traditional sampling of infinite-dimensional continuous-time signals.
Loading 0806.3332v2…