Structured Compressed Sensing: From Theory to Applications

Marco F. Duarte; Yonina C. Eldar

Source-linked AI summary

Structured Compressed Sensing: From Theory to Applications

Marco F. Duarte, Yonina C. Eldar

arXiv:1106.6224v2Jun 30, 2011cs.IT

TL;DR

Structured compressed sensing addresses the limits of conventional random-measurement and standard-sparsity models for practical acquisition. This review synthesizes structured sensing architectures, richer signal models, and applications to connect CS theory with hardware, concluding that exploiting signal structure can increase resolution.

Problem
Prior CS reviews largely focus on randomized discrete-to-discrete measurements and standard sparsity, while practical systems require structured architectures and broader signal models.
Method
The review surveys extensions of CS that incorporate measurement and signal structure, including elaborate sensing schemes, joint-sparse models, and application-oriented formulations.
Results
The review summarizes representative theory and applications showing that exploiting signal structure can increase resolution and support practical sensing beyond the random-measurement paradigm.
Takeaways & Limitations
Structured CS provides a framework for relating feasible hardware constraints and richer signal models to practical signal acquisition and processing.

Abstract

from arXiv · show

Compressed sensing (CS) is an emerging field that has attracted considerable research interest over the past few years. Previous review articles in CS limit their scope to standard discrete-to-discrete measurement architectures using matrices of randomized nature and signal models based on standard sparsity. In recent years, CS has worked its way into several new application areas. This, in turn, necessitates a fresh look on many of the basics of CS. The random matrix measurement operator must be replaced by more structured sensing architectures that correspond to the characteristics of feasible acquisition hardware. The standard sparsity prior has to be extended to include a much richer class of signals and to encode broader data models, including continuous-time signals. In our overview, the theme is exploiting signal and measurement structure in compressive sensing. The prime focus is bridging theory and practice; that is, to pinpoint the potential of structured CS strategies to emerge from the math to the hardware. Our summary highlights new directions as well as relations to more traditional CS, with the hope of serving both as a review to practitioners wanting to join this emerging field, and as a reference for researchers that attempts to put some of the existing ideas in perspective of practical applications.

I. INTRODUCTION AND MOTIVATION … A. Sparsity

The review motivates structured compressed sensing by linking sub-Nyquist acquisition to signal and measurement structure, then develops CS from linear dimensionality reduction and sparsity toward broader signal models and practical hardware. It positions structured CS as a bridge between mathematical recovery theory, feasible acquisition architectures, and applications.

I. INTRODUCTION AND MOTIVATION: Structured CS replaces fully random measurement matrices with application-dependent architectures that reflect wireless channels, analog hardware, sensor networks, and optical imaging.This shift responds to CS expanding beyond its original simplified discrete-to-discrete setting.
A. Shannon-Nyquist Theorem: Shannon-Nyquist reconstruction requires equispaced sampling at least 2B for bandlimited signals, but increasingly wideband applications make such conversion speeds difficult for available ADC hardware.Structured analog signals can potentially be processed more efficiently because the Shannon-Nyquist framework does not account for their internal structure.
I. INTRODUCTION AND MOTIVATION: The review targets acquisition devices that exploit signal structure so sampling, storage, and DSP depend on information content rather than ambient signal dimension.Its central goal is to move structured CS strategies from mathematical theory toward real-world hardware and applications.
B. Compressed Sensing and Beyond: CS recovers an N-dimensional signal from M ≪ N linear measurements, performing compression during acquisition through carefully chosen projection vectors.The review extends this framework beyond standard sparsity through union-of-subspaces models and related structured signal representations.
III. COMPRESSED SENSING BASICS: The CS measurement model acquires y = Φx with M < N, while designing Φ to make signals in a chosen class uniquely identifiable from substantially fewer measurements.The recoverable signal class is therefore a central design choice in compressed sensing.
A. Sparsity: Sparsity represents a signal as x = Ψθ with only K ≪ N nonzero coefficients, enabling compression by retaining coefficient values and locations using O(K log2 N) bits.Sparsity is the most prevalent CS structure and has supported transform-coding applications including imaging denoising, deconvolution, restoration, and inpainting.
A. Sparsity: Approximately sparse signals with power-law coefficient decay are s-compressible because their best K-term approximation error decreases as K grows.CS exploits this structure by recovering x from measurements while aiming to push M as close as possible to K; the review often uses the identity basis so x itself is sparse.

B. Design of CS Matrices

CS matrix design seeks unique and stable recovery of sparse signals, progressing from spark-based uniqueness to computable coherence and RIP guarantees. The section also contrasts deterministic constructions with randomized matrices and practical structured alternatives.

B. Design of CS Matrices: If spark(Φ) > 2K, every measurement vector corresponds to at most one K-sparse signal, implying the necessary measurement condition M ≥ 2K.Spark measures the smallest number of linearly dependent columns, but computing it has combinatorial complexity.
B. Design of CS Matrices: Coherence provides an easier-to-compute uniqueness criterion, obtained by relating pairwise column correlations to spark through the Gershgorin circle theorem and the Welch bound.The resulting coherence-based sparsity guarantee is weaker in scaling, with K = O(√M) as reported in the section.
B. Design of CS Matrices: The (K, δ)-RIP makes every M × K submatrix approximately distance-preserving, supports stability under additive noise, and implies uniqueness when Φ has the (2K, δ)-RIP with δ > 0.When noise is added before measurement, recovery distortion degrades by a factor of N/M.
B. Design of CS Matrices: Deterministic matrices can provide strong spark, coherence, or RIP properties, but Vandermonde matrices become poorly conditioned and some RIP constructions require M = O(K^2 log N) measurements.These limitations make such constructions undesirable for real-world values of N and K.
B. Design of CS Matrices: Random Gaussian, Rademacher, and subgaussian matrices achieve spark, coherence, or RIP guarantees with high probability, while subsampled Fourier and Hadamard transforms also support effective CS recovery.These randomized and structured constructions address limitations of deterministic designs and broaden the practical matrix choices discussed.

C. CS Recovery Algorithms

CS recovery algorithms seek a signal consistent exactly or approximately with measurements, balancing recovery guarantees against computational feasibility. The section contrasts exhaustive ℓ0 search with convex ℓ1 methods, noise-aware extensions, stochastic-prior approaches, and greedy iterative algorithms.

Sparse recovery formulation: ℓ0 minimization searches for the sparsest signal consistent with y, succeeds for all x ∈ΣK under sparse solution uniqueness, but has combinatorial complexity.The search may require checking spans of every set of K columns of Φ, motivating computationally feasible alternatives.
Convex optimization: Basis pursuit replaces ℓ0 with the convex ℓ1 norm, enabling linear-program implementations with polynomial complexity in the signal length.BP is formulated as a convex relaxation of the sparsest-solution problem.
Noise-aware recovery: For noisy measurements y = Φx + n, BP extends to BPIC using a noise-magnitude bound and to BPDN through Lagrangian relaxation, with polynomial-complexity solvers.Efficient solvers are available for BP, BPIC, and BPDN.
Stochastic noise models: When bounded-norm noise is too pessimistic, complexity-based regularization and Bayesian estimation incorporate stochastic noise through complexity-based or probabilistic priors.A common stochastic model is additive white Gaussian noise n ∼N(0, σ2I).
Greedy recovery: Greedy methods such as matching pursuit and orthogonal matching pursuit iteratively select columns of Φ most correlated with the measurement residual until a convergence criterion is met.OMP updates the support, signal estimate, and residual at each iteration.

D. CS Recovery Guarantees

CS recovery guarantees are organized by the matrix metric or signal model used: coherence, RIP, and non-uniform probabilistic conditions. Randomized matrices and sparse-signal models enable recovery at K = O(M), improving on deterministic coherence-based guarantees with K = O(√M).

Coherence-based guarantees: Coherence-based results guarantee recovery for BP and OMP under noiseless or noisy measurements, but noisy error bounds scale with the noise magnitude and require knowledge of that magnitude.OMP additionally requires a lower bound on the minimum nonzero coefficient for its support guarantee, whereas BPIC and BPDN do not.
Coherence-based guarantees: Under AWGN, BPDN achieves an O(σ√K log M) error bound, substantially smaller than the O(σ√M) bound obtained by applying the deterministic noise-magnitude guarantee, and close to the Cramér–Rao bound [61, 62].OMP can also achieve high-probability error and exact-support recovery under AWGN, subject to coherence and minimum-entry conditions.
Non-uniform guarantees: Non-uniform probabilistic guarantees relax matrix requirements and recover most sufficiently sparse signals, including unique BP recovery with high probability when support and entries follow the stated random model.These guarantees apply to a subset of sparse signals rather than uniformly to every signal.
Measurement scaling: K = O(M) for high-probability recovery under RIP or probabilistic sparse-signal models, versus K = O(√M) for deterministic coherence guarantees, creating the square root bottleneck.The improved scaling helps explain the popularity of randomized CS matrices and sparse signal models.

IV. STRUCTURE IN CS MATRICES · A. Subsampled Incoherent Bases

Structured CS replaces infeasible arbitrary random matrices with sensing architectures constrained by measurement physics and hardware, including subsampled bases incoherent with the signal’s sparsity basis. This approach forms measurements by selecting coefficients from a suitable orthonormal basis, retaining limited randomness through coefficient selection.

IV. STRUCTURE IN CS MATRICES: Real-world sensing physics and device capabilities can restrict which CS matrices are implementable.Arbitrary high-dimensional matrix–vector multiplication may be too costly for practical applications.
IV. STRUCTURE IN CS MATRICES: Structured CS matrices address the practical limitations of independently randomized matrix entries.The sensing modality and hardware determine feasible measurement architectures.
A. Subsampled Incoherent Bases: A basis incoherent with the sparsity basis can provide CS measurements by subsampling its coefficients.This extends coherence from a frame to pairs of orthonormal bases.
A. Subsampled Incoherent Bases: The subsampled-incoherent-basis construction retains some randomness through the choice of coefficients used as measurements.Randomness remains in selecting which basis coefficients represent the signal.
A. Subsampled Incoherent Bases: Formally, measurement uses a provided N × N basis Φ whose columns represent distinct basis elements.The basis is specified as Φ = [φ1 φ2 . . . φN].
A. Subsampled Incoherent Bases: A column submatrix preserves basis vectors indexed by Γ before forming the measurement vector y.The supplied formulation defines the retained basis elements through the index set Γ.

1) Formulation: … 2) Theoretical guarantees:

The framework evaluates structured compressed sensing through mutual coherence and extends recovery guarantees from sparse to compressible signals. It also analyzes structurally subsampled matrices, hardware-constrained acquisition, and applications including imaging and compressive ADCs.

1) Formulation:: Mutual coherence measures the largest absolute inner product between elements of two orthonormal bases, with values ranging from N^-1/2 for Fourier and canonical bases to 1 for shared elements.The definition extends to infinite-dimensional representations of continuous-time signals.
1) Formulation:: With random signs and uniformly sampled measurements, Theorem 14 guarantees exact recovery of a K-sparse signal with probability at least 1 −δ when M ≥ CKNµ^2(Φ, Ψ) log(N/δ) and M ≥ C′ log^2(N/δ).The required measurements range from O(K log N) to O(N).
2) Theoretical guarantees:: For compressible signals, adapting Rudelson and Vershynin’s argument links coherence to restricted isometry, yielding δ_2K ≤1/2 with probability at least 1−5e^−t and measurement requirements dictated by µ(Φ, Ψ).The result extends the sparse-signal guarantee to compressible signals.
2) Theoretical guarantees:: Subsampled incoherent bases support hardware-limited measurements in MRI, tomographic imaging, and optical microscopy, where acquisition directly produces 2-D continuous Fourier coefficients.These applications constitute one major category of structured acquisition architectures.
3) Applications:: A second category designs hardware-compatible measurement bases, including single-pixel cameras using binary optical-modulator patterns and random sampling ADCs for periodic multitone signals on a uniform frequency grid.Randomized basis permutations reduce coherence with wavelets, while the single-pixel camera’s optical aggregation improves measurement signal-to-noise ratio.
B. Structurally Subsampled Matrices: Structurally subsampled matrices model observations that linearly combine multiple signal coefficients, with Φ formed by randomly selecting and normalizing rows from Φ = RU.The formulation includes subsampled incoherent bases when P = N and R = I.
2) Theoretical guarantees:: Using an integrator matrix that sums adjacent transform coefficients and Rademacher diagonal modulation, the resulting structurally subsampled matrix satisfies the (K, δ)-RIP with probability at least 1 −20 max{exp(−c2δ^2z), N^−1} [83].The construction uses R = SM, where S aggregates intervals of adjacent coefficients.
2) Theoretical guarantees:: The coherence µ(U, Ψ) determines measurement requirements for structurally subsampled matrices, ranging from O(K log^3 N) to O(N).This parallels the subsampled incoherent-basis setting.

3) Applications: … 1) Formulation:

The paper develops structured sensing architectures that connect feasible acquisition hardware with compressive sensing, spanning analog random demodulation, subsampled circulant matrices, imaging systems, and separable multidimensional measurements. These structures reduce degrees of freedom or computational cost while requiring specialized theoretical guarantees and accommodating richer signal models.

3) Applications:: Structured CS replaces generic random matrices with hardware-compatible operators for periodic multitone analog signals whose uniformly gridded frequencies yield finite-dimensional models.The random demodulator mixes the signal with a pseudorandom chipping sequence, effectively implementing matrix multiplication in the analog domain.
3) Applications:: Random demodulation is practically limited by the representation’s maximal frequency, with reported implementations reaching 1 MHz and therefore requiring one million coefficients.Prototype and related implementations are reported in,.
3) Applications:: Infinite-dimensional signal models can extend compressive sensing toward more efficient analog acquisition and digital processing than finite-parameter random demodulation.The paper defers the details of this adaptation to Section VI.
C. Subsampled Circulant Matrices: Subsampled circulant sensing forms Φ = RU by randomly selecting rows of a circulant matrix, reducing matrix degrees of freedom for communication tasks such as channel estimation and activity detection.These applications use sparse priors on channel responses or multiuser activity patterns.
2) Theoretical guarantees:: Because circulant entries are dependent, standard independent-entry proofs do not apply, so recovery guarantees require alternative probabilistic tools and randomness in the defining sequence.The supplied theoretical passages state that RIP can be achieved with high probability under the stated bounds, including universal constants C and C′.
3) Applications:: Convolution-based sensing supports fast CS computations through FFT multiplications by Φ and ΦT and can be implemented in imaging systems with dense point spread functions.A dense PSF spreads an impulse across the imaging field, enabling compressive imaging with coded apertures.
3) Applications:: A custom microelectronic imager uses an N × N sensor array and an N^2-length feedback shift register to implement a subsampled circulant CS matrix [95].The architecture uses a pseudorandom generator, LFSR-controlled multipliers, and quantization; its schematic appears in Fig. 5.
D. Separable Matrices: Separable and Kronecker-product matrices provide efficient CS representations for multidimensional signals by exploiting structure and sparsity or compressibility along each dimension.For x = Ψθ with Ψ = Ψ1 ⊗ … ⊗ ΨD, component matrices’ RIP properties yield corresponding bounds for the full matrix [96, 97].

2) Theoretical guarantees: … 1) Conditions on measurement matrices:

The paper develops theoretical guarantees for structured sensing and joint-sparse recovery, then connects separable CS matrices to hyperspectral and transform-imaging hardware. It also broadens CS beyond standard sparsity toward structured finite-dimensional and continuous-time signal models.

2) Theoretical guarantees:: For an orthonormal basis Φ_d, the Kronecker-product sensing matrix inherits the CS matrix’s RIP constant because Φ_d has δ_d=0.This preserves the relevant RIP guarantee under the structured measurement construction.
2) Theoretical guarantees:: Kronecker products conserve mutual coherence, yielding measurement requirements no greater than partitioned measurements under the stated recovery theorems.The comparison follows because each section’s sparsity and measurement-basis coherence is at most one.
3) Applications:: Separable CS matrices support multidimensional sensing applications, including hyperspectral datacubes and transform-imaging architectures.The hyperspectral example extends the single-pixel camera, while the transform imager implements a separable matrix through tiled matrix products.
3) Applications:: A spectrometer-based hyperspectral camera applies shared modulation patterns across spectral bands, producing measurements represented by a separable sensing matrix.The spectrometer records intensities by wavelength while the micromirror array reflects all wavelengths of interest.
V. STRUCTURE IN FINITE-DIMENSIONAL MODELS: Beyond measurement structure, the paper generalizes sparsity to reduce sampling for finite-dimensional models and ultimately continuous-time signals.The discussion first structures nonzero values in finite-dimensional vectors before extending to broader analog-signal models in Section VI.
A. Multiple Measurement Vectors: MMV recovery jointly estimates vectors sharing a common support, represented as a matrix with at most K nonzero rows.The model is Y=ΦX with each measurement vector shorter than the signal dimension, enabling joint use of shared support information.
1) Conditions on measurement matrices:: MMV uniqueness depends on rank and support, with higher-rank matrices recoverable from fewer measurements or larger supports under the necessary-and-sufficient condition.When rank(X)=1, joint processing provides no advantage; greater column diversity enables recovery benefits, and noiseless recovery admits a simple algorithm.

2) Recovery Algorithms: · 3) Performance guarantees:

Recovery methods for MMV systems range from mixed-norm optimization and greedy algorithms to rank-aware, ReMBo, and continuous-to-finite strategies, with guarantees tied to sparsity, rank, and measurement conditions. Average-case analysis shows that joint recovery can require fewer measurements and achieve high-probability recovery beyond worst-case limits.

2) Recovery Algorithms:: Mixed-norm recovery replaces the ℓ0 objective with minimizing ∥X∥p,q subject to Y = ΦX, while simultaneous greedy methods extend OMP by selecting rows from residual-matrix q-norms.Advocated choices include p, q = 1, 2, and ∞; the greedy extension replaces residual vectors with residual matrices and ΦT r with row q-norms of ΦT R.
2) Recovery Algorithms:: ReMBo reduces MMV to an SMV while preserving the sparsity pattern, then recovers the support and inverts the measurements; repeated random reductions can boost empirical recovery rates.The reduction merges measurement columns with random coefficients, but noise or insufficient measurements can cause errors.
2) Recovery Algorithms:: Rank-aware recovery exactly recovers X when rank(X) = K and condition (31) holds, exploiting the signal subspace to identify its support.In noise, selecting the K indices minimizing the subspace criterion yields a rank-aware method whose performance improves with increasing rank.
2) Recovery Algorithms:: The continuous-to-finite reduction recovers infinite measurement-vector signals by solving a finite MMV system whose unique sparse solution has the original support under condition (31).The reduction constructs a basis for the span of the measurements, after which each signal vector is recovered by pseudoinversion on the identified support.
2) Recovery Algorithms:: MMV extensions have SMV-equivalent worst-case guarantees, yet multichannel reconstruction performs better in practice than recovering channels independently.Theoretical equivalence for arbitrary X therefore does not predict the observed practical gain from joint sparsity.
3) Performance guarantees:: Average-case analysis needs fewer measurements for exact recovery, and mixed-norm recovery with p = 2 and q = 1 succeeds with high probability when K ≤ min(C1/µ2(Φ), C2N/∥Φ∥2).The model selects K nonzero rows uniformly at random and draws their concatenated nonzero entries from a Gaussian construction.
3) Performance guarantees:: Average-case recovery supports sparsity up to order K = O(M), versus worst-case K = O(√M), while failure probability decays exponentially with the number of channels L [119].The exponential decay holds under a mild condition on sparsity and the sensing matrix Φ.
3) Performance guarantees:: The MMV model also supports EEG/MEG applications, where temporal regularization can further improve estimation for available signal sequences [21, 102].Sparsity-promoting inversion is used to localize electromagnetic source signals.

4) Applications: · B. Unions of Subspaces · 1) Conditions on measurement matrices:

The section generalizes sparsity to unions of finite- and infinite-dimensional subspaces, enabling structured signal models beyond canonical supports. It then develops measurement conditions, recovery guarantees, and block-sparse formulations for these models.

4) Applications:: MMV recovery also applies to certain infinite-dimensional signal models, with further discussion deferred to Section VI-B.The paper illustrates MMV-based EEG inversion using temporal regularization with 306 sensors and simulated activity from three vertices over 120 ms.
B. Unions of Subspaces: Unions of subspaces represent sparse signals as vectors lying in one of several K-dimensional subspaces, extending canonical sparsity to richer finite- and infinite-dimensional models.Canonical sparse supports correspond to subspaces aligned with coordinate axes, while other choices encode broader signal priors.
B. Unions of Subspaces: Union models are not closed under addition, so the sum of two signals in the union generally leaves it, complicating sampling and recovery.This nonlinear behavior is a central distinction from linear signal models.
B. Unions of Subspaces: Finite unions of subspaces include structured sparse supports and sparse sums of subspaces, with only selected support patterns or subspace combinations permitted.These cases can also be combined, while models with infinitely dimensional or infinitely many subspaces extend to analog signals.
1) Conditions on measurement matrices:: For a finite union of L subspaces of dimension D, subgaussian measurement matrices satisfy the (U, δ)-RIP with probability at least 1 −e−t under the proposition’s stated conditions.The dominant asymptotic measurement term quantifies the samples needed to identify the signal’s exact subspace.
1) Conditions on measurement matrices:: Structured support constraints reduce required measurements relative to traditional sparsity because fewer supports are allowed, while each subspace retains dimension D = K.For sparse sums of subspaces, the number of nonzeros remains unchanged, so D = O(K) is not reduced.
1) Conditions on measurement matrices:: Sparse sums of subspaces are equivalent to block-sparse coefficient vectors, yielding measurements y = AΨθ = Φθ with at most K nonzero blocks.When block size d = 1, block sparsity reduces to conventional sparsity; block-coherence extends coherence, and µB(Φ) ≤µ(Φ).

2) Recovery algorithms:

Recovery for structured sparse models extends greedy and optimization-based methods by incorporating structured support approximations, while often retaining guarantees from standard algorithms under modified conditions. These methods include model-based CoSaMP and IHT, block-thresholding approximations, and mixed-norm convex recovery for sums of subspaces.

Model-based greedy recovery: Model-based CoSaMP modifies residual and signal pruning through structured operators, and the same approach yields a model-based IHT variant.For FUS recovery, CoSaMP’s standard RIP requirement of order 4K is replaced by reliance on enlarged unions of subspaces.
Structured sparse approximation: Structured sparse approximation algorithms are feasible and computationally efficient across varied support models, including block sparsity where MU preserves the K blocks with largest energies.Under block sparsity, MU is equivalent to block thresholding based on block energies or ℓ2 norms.
Optimization-based recovery: For sparse sums of subspaces, convex recovery minimizes the summed block energies using a mixed ℓ2/ℓ1 norm.The resulting optimization formulation recovers the coefficient representation θ, with the cited method associated with.
Extensions: The convex constraints can be relaxed for noisy measurements, while greedy recovery has also been generalized to block-sparse settings.These extensions parallel the standard BPIC treatment of noise.
Guarantees: Many FUS recovery methods inherit guarantees from their standard counterparts, subject to model-specific requirements such as enlarged unions of subspaces for CoSaMP.The stated CoSaMP condition follows from its requirement for RIP of order 4K.

3) Recovery guarantees: · 4) Applications: · VI. STRUCTURE IN INFINITE-DIMENSIONAL MODELS

Structured models admit recovery guarantees under model-based RIP, optimization, and block-coherence conditions, while applications demonstrate structured source separation and internally sparse representations. The framework extends reduced-rate analog sampling to unions of finite- or infinite-dimensional subspaces through hardware-aware, continuous-time formulations.

3) Recovery guarantees:: Model-based CoSaMP recovers noisy signals in a finite union of subspaces when the sensing operator satisfies an (S4(U), δ)-RIP with δ ≤ 0.1.Related guarantees also cover model-based IHT, and additional conditions provide stability to signal mismodeling.
3) Recovery guarantees:: Optimization-based recovery for sparse sums of subspaces is guaranteed under an (S2(U), δ)-RIP condition with bounded measurement noise.The estimate is obtained from the relaxed constrained formulation, with the bound depending on the model mismatch quantity MU(x).
3) Recovery guarantees:: Block-coherence conditions guarantee recovery of block-sparse vectors by both greedy and optimization-based methods, including extensions to adversarial and random measurement noise.For orthonormal blocks, ν(Φ)=0, and exploiting block structure can guarantee recovery at a potentially higher sparsity level than conventional sparsity.
3) Recovery guarantees:: Tree-structured wavelet supports provide a structured sparse model for smooth or piecewise-smooth signals, with model-based CoSaMP illustrated on a 512 × 512 Peppers image from 40000 measurements.The figure contrasts standard and model-based CoSaMP recovery for the same image and measurements; only the standard method’s reported SNR is supplied.
4) Applications:: Adding ℓ1 penalties within subspace blocks yields C-HiLaSo, combining group-level and individual-feature sparsity for structured representations.Applied to mixtures of handwritten digits from subsampled information, the FUS model supports source identification and separation; Fig. 10 shows recovered digits and active sets.
VI. STRUCTURE IN INFINITE-DIMENSIONAL MODELS: Infinite-dimensional union models target reduced-rate sampling of analog signals through three cases: finite unions of infinite-dimensional spaces, infinite unions of finite-dimensional spaces, and infinite unions of infinite-dimensional spaces.The review develops general theory and a representative application for each class.
VI. STRUCTURE IN INFINITE-DIMENSIONAL MODELS: The analog-sampling approach represents signals directly as unions of subspaces, unlike discretization-based methods that may ignore hardware or shift reduced-rate analog processing into high-rate DSP.Shift-invariant subspaces provide the introductory sampling framework, which is then extended to incorporate structure and hardware-aware acquisition.

A. Shift-invariant spaces for analog signals … 5) Example application:

The paper develops structured analog compressed-sensing architectures for shift-invariant and union-of-subspaces signal models, enabling recovery from hardware-compatible measurements and sub-Nyquist multiband sampling. The framework combines analog aliasing, digital subspace identification, MMV-based reconstruction, and practical sampling alternatives.

A. Shift-invariant spaces for analog signals: Shift-invariant spaces represent broad analog signal classes, including bandlimited, spline, multiband, and pulse-amplitude-modulation signals, using finitely many generators and coefficient sequences.Each signal can be recovered from samples at rate N/T, despite the signal space having infinite dimension.
B. Finite union of infinite-dimensional subspaces: The framework extends shift-invariant models to unions of subspaces by activating only K generators, or by selecting generators from finite or infinite sets.The common architecture aliases signals before sampling so measurements contain energy from all subspace components, then identifies the active subspace before recovery.
1) Analog signal model:: When the K active generators are known, K appropriately filtered uniform sample streams suffice; when they are unknown, the problem becomes recovery from a union of single-generator subspaces.This establishes the analog signal model underlying compressive acquisition.
2) Compressive signal acquisition scheme:: Compressive acquisition designs p<N sampling filters as linear combinations of Nyquist-rate reconstruction filters, with coefficients determined by a p×N matrix solving a discrete MMV problem with sparsity K.An arbitrary invertible filter-bank matrix provides additional freedom in selecting the sampling filters.
3) Reconstruction algorithm:: The sampled generator coefficients form jointly K-sparse measurement vectors, allowing analog recovery to reduce to an MMV reconstruction problem after any required inverse filter-bank preprocessing.The measurement vectors collect the p sampled outputs, while the unknown vectors contain the N generator coefficients.
4) Recovery guarantees:: p=2K filters guarantee recovery for all input signals, while practical polynomial-time MMV algorithms generally require slightly more than 2K filters.Noise, mismodeling, and suboptimal-recovery results transfer directly from the underlying MMV problem.
5) Example application:: For multiband signals with unknown carriers, the blind sampling density obeys D(R)≥min{Ω, 2fmax}; with Ω=2NB and NB<fmax, sampling below the Nyquist rate is possible.Periodic nonuniform sampling uses a partial DFT sensing matrix and can approach this lower bound, while the modulated wideband converter avoids the high-bandwidth track-and-hold required by PNS.

6) Example hardware: … 2) Compressive signal acquisition:

The paper connects structured compressed sensing to practical hardware through the modulated wideband converter, and to analog signal recovery through finite-rate-of-innovation pulse models. These approaches exploit signal structure to recover wideband or continuous-time signals from substantially fewer samples than Nyquist-rate acquisition.

6) Example hardware:: A modular MWC can reduce channel count or sampling rate when carrier frequencies are known, or scale toward full-band Nyquist sampling by adding channels or rate.Advanced configurations collapse branches by a factor q while increasing each channel’s sampling rate by the same factor.
6) Example hardware:: The modulated wideband converter mixes, filters, and samples wideband inputs in parallel low-rate channels, producing compressed measurements of spectrum slices.Its periodic mixing scrambles spectrum slices, while lowpass filtering retains the required narrowband mixtures.
6) Example hardware:: The MWC prototype sampled 43 inputs with a 2 GHz Nyquist rate and 120 MHz occupied spectrum at a total 280 MHz rate, using q = 3 hardware collapsing.This demonstrates sampling proportional to occupied bandwidth rather than the highest frequency.
C. Infinite union of finite-dimensional subspaces: Signals whose generators have unknown continuous parameters form an infinite union of finite-dimensional subspaces, including streams of pulses with unknown delays and amplitudes.The pulse-stream model has 2L degrees of freedom when the pulse shape is known and was introduced as a finite-rate-of-innovation model.
1) Analog signal model:: Because no general acquisition method exists for the full continuous-parameter model, the discussion focuses on periodic pulse streams and their Fourier-series structure.Periodicity preserves the model’s dimensionality while making acquisition easier to analyze.
2) Compressive signal acquisition:: For a τ-periodic pulse stream, filtered uniform samples uniquely determine the signal when N ≥ |K| ≥ 2L and the selected Fourier samples avoid zeros of the pulse spectrum.The sampling filter is followed by uniform sampling with T = τ/N; the result extends earlier lowpass-filter work to arbitrary filters.
2) Compressive signal acquisition:: Fourier coefficients support recovery of delays and amplitudes through matrix-pencil, subspace, or annihilating-filter methods, each requiring 2L coefficients.The sample vector is converted into the required Fourier-coefficient vector through the sampling scheme.
2) Compressive signal acquisition:: Sum-of-Sincs filters provide finite-time-support acquisition and remain stable for very high pulse-stream orders, such as L = 100, unlike spline-based moments for high L [7, 163].Infinite-time-support lowpass filters cannot directly handle time-limited pulse streams, motivating compact filters such as SoS.

3) Recovery algorithms:

Recovery combines structured sampling with algebraic reconstruction: Fourier coefficients are obtained from samples, then an annihilating filter recovers pulse delays and a Vandermonde inversion computes amplitudes. For five Gaussian pulses, SoS-filter reconstruction is exact to numerical precision using 11 samples, while Fig. 15 compares noisy recovery across several sampling kernels.

SoS sampling recovers the Fourier coefficient vector from samples as x = Q†c, with Q determined by the filter and, for multichannel architectures, modulation coefficients.
The annihilating-filter method identifies delays from the roots of its z-transform, after which the Fourier coefficients are computed from the recovered delays.
Only 2L consecutive values of X[k] are needed to determine the annihilating filter and retrieve the delays.
The pulse amplitudes are obtained by matrix inversion because the associated Vandermonde matrix is left-invertible.
Exact to numerical precision, SoS-filter sampling reconstructs a signal of L = 5 Gaussian pulses from N = 11 samples; Fig. 15 also compares noisy recovery for finite streams of 3 and 5 Dirac pulses using Gaussian [6], B-spline, E-spline [7], and SoS kernels.

4) Applications: … 2) Compressive signal acquisition:

The paper extends structured compressed sensing from finite-dimensional models to applications in superresolution, ultrasound imaging, and continuous-time signal acquisition. It develops sampling and reconstruction schemes that exploit finite-rate-of-innovation structure, periodic delays, parallel channels, and digital filter correction.

4) Applications:: FRI-based methods support image superresolution by registering low-resolution images before fusing them into a higher-resolution output, potentially removing blur and noise.Registration is crucial for obtaining a good-quality superresolved image; Fig. 16 demonstrates an 8× superresolution factor.
4) Applications:: Ultrasound imaging can use FRI sampling to reduce acquisition and processing demands while reconstructing signals from substantially fewer samples than the original recording.Fig. 17 compares the original 4160-sample signal with reconstructions using N = 17 and N = 33 samples.
D. Infinite Union of Infinite-Dimensional Subspaces: For infinite unions of infinite-dimensional spaces, each generator is assigned an unknown parameter, and the discussion specializes to shifted generators hℓ(t) = h(t − τℓ).The paper notes that no general sampling framework is currently available for the full model.
1) Analog signal model:: When no more than L nonoverlapping pulses occur in each interval of length T, parameters can be processed independently using the earlier schemes.The sampling system uses p ≥ 2K channels and obtains one sample from each channel every T seconds.
1) Analog signal model:: For pulses extending beyond T, independent per-period processing fails, but periodic time delays enable efficient sampling and recovery with a single filter even when h(t) is not time limited.The periodic-delay case is treated as a special simplification, while amplitudes remain nonperiodic.
1) Analog signal model:: The infinite-generator setting replaces the finite-model CTF block with a continuity-supporting block, with ESPRIT effectively replacing the CTF.This adapts the structured SI approach from N possible generators to infinitely many possibilities.
2) Compressive signal acquisition:: The compressive acquisition architecture uses p parallel channels, band-limited kernels, uniform sampling at 1/T, and digital filter correction through W^-1(e^jωT).The kernels spread signal energy in time before low-rate sampling, and their filters can be collapsed to one filter sampled at p times the single-channel rate.

3) Recovery algorithms: … VII. CONCLUSIONS

The paper develops structured recovery methods and guarantees for continuous-time, parameterized signals, demonstrating reduced-rate sampling and improved resolution in applications such as radar while connecting analog acquisition to digital array processing.

3) Recovery algorithms:: The proposed ESPRIT-based recovery constructs a correlation matrix, extracts its signal subspace by SVD, computes eigenvalues, and maps them to the unknown delays.After digital correction, the sample vector is related to amplitudes through a delay-dependent Vandermonde matrix, enabling ESPRIT recovery [19, 173].
4) Recovery guarantees:: Any signal of the stated form is guaranteed recoverable when p ≥ 2L − η + 1, provided the filters have the required support and W(e^jωT) is invertible.The guarantee applies to joint outputs whose signal vectors lie in a minimal subspace of dimension η.
4) Recovery guarantees:: The resulting sampling rate is at most 2L/T and can fall to (L+1)/T, independently of the pulse Nyquist rate, enabling substantial wideband reductions.The reduction follows from jointly processing the outputs in an MMV-like manner.
5) Applications:: The radar targets can be exactly identified when W ≥ 4πL/T and N ≥ 2 max Kℓ, yielding a minimum input time-bandwidth product WT ≥ 8πL max Kℓ.Doppler shifts and reflection coefficients are obtained from the recovered sequences using standard spectral estimation tools.
5) Applications:: Nine close radar targets were correctly identified, and the compressive union-of-subspaces method achieved superior low-noise resolution to matched filtering at the same time-bandwidth product.The comparison uses the delay–Doppler plane and the parameters specified for Fig. 19.
E. Discussion: These infinite-union methods use analog filters followed by standard digital array processing, achieve perfect noiseless recovery, and generally degrade gracefully under noise.Their noise behavior has been extensively analyzed in the array-processing literature.
VII. CONCLUSIONS: The review extends compressed sensing beyond random measurements and standard sparsity by incorporating device constraints, structured signals, continuous-time models, analog-to-digital interfaces, and application-specific recovery algorithms.Its selected examples balance theoretical foundations with varied applications and are intended to support practitioners in signal acquisition and processing.
VII. CONCLUSIONS: By exploiting signal structure, compressed sensing can increase resolution and potentially remove Nyquist barriers in radar, microscopy, surveillance, medical imaging, and other ADC-dependent applications.The conclusion frames this as efficient use of the available degrees of freedom in resolution-limited systems.