Source-linked AI summary
Fast and Efficient Compressive Sensing using Structurally Random Matrices
Thong T. Do, Lu Gan, Nam H. Nguyen, Trac D. Tran
TL;DR
Sparse-reconstruction algorithms repeatedly compute sensing-matrix products, making computational complexity depend on the sensing matrix structure. The paper proposes Structurally Random Matrices that combine randomization and fast transforms, with theoretical recovery guarantees and lower sensing complexity than i.i.d. matrices.
Problem
Sparse-reconstruction algorithms repeatedly compute ΦΨ and (ΦΨ)T, so system complexity depends on the structure of sensing matrix Φ and its transpose.
Method
The paper proposes Structurally Random Matrices (SRMs), using local or global randomization with a fast transform and subsampling, with sensing matrices whose entries can be {0, 1, −1}.
Results
With probability at least 1−δ, the proposed framework can exactly recover K-sparse signals under stated measurement conditions, while SRM sensing requires N + N log N operations and 2N + N log N bits of storage.
Takeaways & Limitations
SRM reduces sensing and reconstruction computation relative to random matrices, with per-iteration speedups of at least K-fold under the stated assumptions.
Takeaways & Limitations
The asymptotic normality of SRM entries alone does not establish sensing performance because entries of AΨ are generally dependent rather than i.i.d.
Abstract
from arXiv · showhide
This paper introduces a new framework of fast and efficient sensing matrices for practical compressive sensing, called Structurally Random Matrix (SRM). In the proposed framework, we pre-randomize a sensing signal by scrambling its samples or flipping its sample signs and then fast-transform the randomized samples and finally, subsample the transform coefficients as the final sensing measurements. SRM is highly relevant for large-scale, real-time compressive sensing applications as it has fast computation and supports block-based processing. In addition, we can show that SRM has theoretical sensing performance comparable with that of completely random sensing matrices. Numerical simulation results verify the validity of the theory as well as illustrate the promising potentials of the proposed sensing framework.
I. INTRODUCTION
Compressive sensing seeks recovery of sparse or compressible signals from few measurements, but practical sensing matrices must balance recovery quality, universality, computational efficiency, and implementation constraints. The paper proposes SRM, which pre-randomizes signals, applies a fast transform, and subsamples transform coefficients.
- Motivation: K-sparse signals can be well approximated using K ≪ N coefficients and recovered from M = O(K log N) measurements.The measurements follow a random linear projection model with acquisition noise.
- Limitations of existing sensing matrices: Random Gaussian or Bernoulli matrices are universally incoherent but require substantial storage and computation because they are unstructured.For a 512 × 512 image with 64K measurements, a Bernoulli matrix requires nearly gigabytes of storage and giga-flop operations.
- Limitations of existing sensing matrices: Partial FFT matrices are fast but may lose performance when the sparsifying basis has high mutual coherence with the transform.Noiselets target the Haar wavelet basis, but their incoherence with other bases is unknown.
- SRM framework: The proposed SRM framework targets near-optimal sensing, universality, low complexity, fast computation, block processing, and hardware-friendly entries in {0, 1, −1}.SRM is introduced as a product of three matrices.
- SRM framework: SRM pre-randomizes the signal by sign flipping or sample permutation, applies a fast orthonormal transform, and randomly subsamples M transform coefficients.The three stages correspond to multiplying by R, F, and D, respectively.
- SRM framework: SRM is distinct from prior structured sensing methods because its first step pre-randomizes the signal to promote universally incoherent sensing.The stated purpose is to convert the sensing signal into a white noiselike one.
B. Notations
The paper establishes notation for signals, sensing and sparsifying matrices, then analyzes how randomized fast transforms produce approximately Gaussian entries under local and global randomization.
- Notation: x is the input signal, y is the measurement vector, Φ is the sensing matrix, Ψ is the sparsifying matrix, and α satisfies x = Ψα.
- Asymptotical Distribution Analysis: Under the stated assumptions, entries of AΨ are asymptotically normally distributed for both local and global randomizers.
- Local Randomization: The local analysis uses the Central Limit Theorem because matrix entries become sums of independent random variables.
- Global Randomization: The global analysis uses the Combinatorial Central Limit Theorem because permutation-based terms are identically distributed but correlated.
- Scope: These asymptotic results do not establish full Gaussian i.i.d. sensing behavior because entries of AΨ are generally not stochastically independent.
B. Incoherence Analysis
Before analyzing incoherence theoretically, the paper introduces assumptions for block-based local and global randomization models.
- The incoherence analysis begins by specifying assumptions for block-based local and global randomization models.
- These assumptions precede the paper’s theoretical results for incoherence.
- The models distinguish local and global randomization settings for the subsequent analysis.
1) Assumptions for the Block-based Local Randomization Model:
The local randomization analysis assumes bounded, unit-norm transform structures and derives mutual and cumulative coherence bounds using concentration arguments.
- Assumptions: The local model assumes F has unit-norm rows with bounded entries, while Ψ has unit-norm columns.
- Global Randomization: The global model requires concentration and union-bound arguments, and its coherence can depend on the sparsifying basis’s column-wise heterogeneity.
- Mutual Coherence: Theorem III.3 establishes a mutual-coherence bound for A = FR under the block-based local randomization assumptions.
- Mutual Coherence: The analysis models relevant matrix entries as sums of independent bounded random variables and applies Hoeffding’s inequality.
- Cumulative Coherence: Cumulative coherence measures average incoherence and provides a tighter measurement bound for exact recovery than entry-wise mutual coherence.
- Cumulative Coherence: For dense, uniform transforms, the cumulative-coherence analysis removes the log N factor from the trivial bound.
IV. COMPRESSIVE SAMPLING PERFORMANCE ANALYSIS
The analysis connects high incoherence between A and Ψ with spreading transform-domain energy across measurements, supporting recovery from a small measurement subset.
- Under mild conditions, A and Ψ are highly incoherent, so AΨ is almost dense.
- When AΨ is dense, energy from nonzero transform coefficients αT is distributed across all measurements.
- This distribution supports signal recovery from a small subset of measurements because concentrated energy may be missed during sampling.
A. Assumptions for Performance Analysis
The analysis assumes sparse transform coefficients with random Bernoulli signs and considers block-based local and global randomization models for SRMs.
- The signal model assumes x = Ψα, with α having at most K nonzero entries and random independent Bernoulli signs on its nonzero coefficients.
- The performance analysis covers block-based local and global randomization models for structurally random matrices.
B. Theoretical Results
Theoretical analysis establishes exact-recovery guarantees for SRMs, with measurement requirements depending on the transform structure and randomization model. Dense uniform transforms achieve optimal-order bounds comparable to random projection, while sparse transforms can incur additional factors or basis-dependent behavior.
- With probability at least 1−δ, the proposed framework recovers K-sparse signals exactly when the measurement count satisfies the theorem's stated sufficient bound.
- For dense uniform transforms such as DCT or normalized WHT, the required number of measurements is O(K log^2(N/δ)).
- When the transform F is dense and uniform, exact recovery requires M ≥ O(K log(N/δ)); for sparse block transforms, the bound depends on the block structure and coherence terms.
- Using cumulative coherence eliminates the log N upscale factor relative to random projection and yields an optimal performance guarantee.
- The local-randomizer framework requires K > 16 log(2N/δ), while dense uniform transforms reduce the minimum requirement to M = O(K log(N/δ)).
- The proof verifies the Exact Recovery Principle by bounding coherence-related norms and controlling correlations with the random sign vector.
A. Simulation with Sparse Signals
Sparse-signal simulations compare structurally random matrices with completely Gaussian random matrices across sparsity levels and sparsifying bases. Dense transforms are broadly comparable, whereas sparse transforms trade sensing performance against streaming capacity and depend on the basis.
- The experiments evaluate exact-recovery probability across sparsity levels, transform bases, block sizes, and local or global randomization choices.Signals use N = 256 and M = 128, with 500 repetitions for each tested sparsity level.
- SRMs with dense transform matrices have average performance comparable to completely random matrices.
- Sparse-transform SRMs depend on the sparsifying basis: they remain comparable for dense bases but often perform worse than dense SRMs for sparse bases.
- The results reveal a trade-off between sensing performance and streaming capacity for sparse transforms.
- With sparse sparsifying bases, the global randomizer performs much better than the local randomizer in the reported simulations.
B. Simulation with Compressible Signals
Image experiments compare SRM variants with partial-FFT benchmarks using wavelet-sparse natural images. Dense SRMs approach benchmark quality, while fully streaming-capable and highly sparse variants provide practical alternatives with measured quality trade-offs.
- The experiments use 512 × 512 natural images represented with the Daubechies 9/7 wavelet transform and reconstruct them with GPSR.
- WPFFT serves as a practical benchmark because implementing a completely random matrix at this scale requires substantial system resources.
- The plots compare reconstruction PSNR against sampling rate for Lena, Barbara, and Boat images.Figure 4 shows a Boat reconstruction from 35% of measurements using WPFFT, WHT32-G, and WHT512-L.
- For image signals, PFFT is inefficient because Fourier and wavelet bases are highly coherent, whereas SRM substantially improves sensing efficiency.
- Dense SFFT differs from WPFFT by less than 1 dB, while fully streaming-capable DCT512-L and WHT512-L degrade by about 1.5 dB.
VI. DISCUSSION AND CONCLUSION
SRM reduces sensing storage and computation relative to unstructured random matrices while retaining practical performance. It generalizes scrambled FFT-style sensing to other fast transforms and supports flexible implementations.
- Complexity Discussion: An M × N SRM requires 2N + N log N bits and N + N log N operations, versus MN bits and MN operations for an i.i.d. Bernoulli matrix.SRM complexity and memory requirements are independent of the number of measurements M.
- Complexity Discussion: SRM can reduce per-iteration matrix-vector multiplication cost from O(KN log N) for random sensing to O(N log N), implying at least K-fold reconstruction speedup.This comparison assumes the sparsifying basis Ψ is the identity matrix.
- Relationship with Other Related Works: SRM generalizes scrambled FFT sensing by pre-randomizing in the original domain and allowing fast transforms such as Fourier, DCT, and WHT.The paper presents SRM as an alternative framework for high-performance, low-complexity sensing with practical and flexible features.
APPENDIX I
The appendix collects concentration and central-limit tools used in the paper’s analysis. These results cover independent variables, random permutations, bounded variables, and vector-valued sums.
- Central Limit Theorem: The Central Limit Theorem describes asymptotic normality for sums of mutually independent random variables under variance and approximation conditions.The stated setup assumes zero means and defines the aggregate variance as the sum of individual variances.
- Combinatorial Central Limit Theorem: The Combinatorial Central Limit Theorem treats sums formed from uniformly permuted sequences and establishes asymptotic normality under nonconstant-sequence assumptions.The displayed setup defines permuted variables and the resulting sum’s mean and variance.
- Concentration Inequalities: Hoeffding’s inequality addresses sums of independent random variables bounded between variable-specific lower and upper limits.The theorem introduces bounded variables and an aggregate random sum.
- Concentration Inequalities: Ledoux’s and Talagrand’s inequalities provide concentration tools for norms of sums of bounded independent random variables multiplied by vectors or matrix columns.Talagrand’s statement additionally assumes zero-mean i.i.d. variables and bounds their magnitudes by λ.
- Concentration Inequalities: Sourav’s concentration inequality concerns collections of numbers in [0, 1] indexed through a uniformly random permutation.Its setup defines a random sum from the permuted collection.