A hybrid DFT-LDPC framework for fast, efficient and robust compressive sensing

We use a hybrid mix of the Discrete Fourier Transform (DFT), an old workhorse in digital signal processing, and Low Density Parity Check (LDPC) codes, a recent workhorse in coding theory, to generate a linear measurement lens through which to perform compressive sensing (CS) of sparse high-dimensional signals. This novel hybrid DFT-LDPC framework represents a new family of sparse measurement matrices, and induces a fast algorithm (dubbed the Short-and-Wide Iterative Fast Transform based or SWIFT algorithm) for robustly recovering a high-dimensional k-sparse signal x, in Cⁿ, from a near-optimal (upto a small constant multiple of k) number of linear observations, with a decoding complexity of k steps, under high signal-to-noise-ratio (SNR). A key attribute of our sensing framework and the SWIFT recovery algorithm is that both the sensing efficiency (number of measurements) and the recovery efficiency (decoding complexity) are independent of the ambient signal dimension n for the noiseless and high-SNR noisy regimes, which is particularly attractive when k <;<; n. This contrasts existing solutions¹ in the CS literature based on the class of Linear Programming (LP)-based optimization techniques and the class of expander graph based greedy-pursuit (sketching) algorithms; for both these classes, both the number of measurements and the decoding complexity depend explicitly on the ambient signal dimension n, even for the noiseless and high-SNR regimes. We provide both an explicit constructions of the DFT-LDPC based matrix framework and an analytical characterization of the SWIFT recovery algorithm. Although our analytical characterization is for asymptotic values of k, n and for high SNR regime, our simulation results validate the efficiency of the SWIFT algorithm even for the low-to-moderate SNR regimes and modest problem dimensions (e.g., k = 250 and n = 20000), beyond what we can currently prove analytically.