The Effect of Spatial Coupling on Compressive Sensing

Abstract

Recently, it was observed that spatially-coupled LDPC code ensembles approach the Shannon capacity for a class of binary-input memoryless symmetric (BMS) channels. The fundamental reason for this was attributed to a "threshold saturation" phenomena derived by Kudekar, Richardson and Urbanke. In particular, it was shown that the belief propagation (BP) threshold of the spatially coupled codes is equal to the maximum a posteriori (MAP) decoding threshold of the underlying constituent codes. In this sense, the BP threshold is saturated to its maximum value. Moreover, it has been empirically observed that the same phenomena also occurs when transmitting over more general classes of BMS channels. In this paper, we show that the effect of spatial coupling is not restricted to the realm of channel coding. The effect of coupling also manifests itself in compressed sensing. Specifically, we show that spatially-coupled measurement matrices have an improved sparsity to sampling threshold for reconstruction algorithms based on verification decoding. For BP-based reconstruction algorithms, this phenomenon is also tested empirically via simulation. At the block lengths accessible via simulation, the effect is quite small and it seems that spatial coupling is not providing the gains one might expect. Based on the threshold analysis, however, we believe this warrants further study.

8 Pages, 7 figures. This is a slightly modified version of the paper which appeared in the 48th Annual Allerton Conference on Communication, Control, and Computing September 29 - October 1, 2010

References in corpus (5)

• Message Passing Algorithms for Compressed Sensing
• Terminated LDPC Convolutional Codes with Thresholds Close to Capacity
• Threshold Saturation on BMS Channels via Spatial Coupling
• On the Iterative Decoding of High-Rate LDPC Codes With Applications in Compressed Sensing
• Asymptotically Good LDPC Convolutional Codes Based on Protographs

Cited by in corpus (12)

• Breaking the coherence barrier: A new theory for compressed sensing
• Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes
• Analysis of Regularized LS Reconstruction and Random Matrix Ensembles in Compressed Sensing
• Universal Codes for the Gaussian MAC via Spatial Coupling
• Spatially Coupled Codes over the Multiple Access Channel
• Approaching the Rate-Distortion Limit with Spatial Coupling, Belief propagation and Decimation
• Connecting Spatially Coupled LDPC Code Chains
• SHO-FA: Robust compressive sensing with order-optimal complexity, measurements, and bits
• Windowed Decoding of Spatially Coupled Codes
• Non-Binary LDPC Codes with Large Alphabet Size
• The Velocity of the Propagating Wave for General Coupled Scalar Systems
• Subsampling at Information Theoretically Optimal Rates