Applications of Coding Theory to Sub-Linear Time Sparse Recovery Problems

Abstract

This dissertation leverages the connection between coding theory and classical sparse recovery problems like sparse Fourier and Hadamard transform computations to understand properties of existing recovery algorithms under various signal models, propose improvements, and adopt them to interesting applications in theoretical computer science like pattern matching.

In the first part of the dissertation, we begin by demonstrating the relationship between an extended Fast Fourier Aliasing-based Sparse Transform (FFAST) algorithm and the iterative hard decision decoding of product codes. We show that the FFAST algorithm is analogous to an iterative decoder for a carefully defined product code whose thresholds can be computed by an extension of Justensen's analysis to d-dimensional product codes. Interpreting the FFAST algorithm as decoding of a product code also provides insight into the performance of the FFAST algorithm when non-zero coefficients are not randomly chosen but are bursty such as what may be encountered in many practical applications like spectrum sensing. Recoverability results are guaranteed for the finite length case and we provided thresholds for the 1 and 2 burst cases asymptotically. It is further observed that the FFAST algorithm performs better for bursty signals in comparison to those for randomly chosen non-zero coefficients.

We then consider the problem of computing the Walsh-Hadamard Transform (WHT) of an N = 2^n dimensional signal whose WHT is K-sparse, when the sparsity parameter K scales sub-linearly in N. We propose improvements to the algorithm by Scheibler et al. by introducing a two error correcting code at each check node. Further, through density evolution analysis and simulations we show that the proposed modification substantially improves the space and time complexity of the algorithm, sometimes achieving as much as a 70% reduction.

We conclude by considering the substring/pattern matching problem of querying a string (or a database) of length N bits to determine all the locations where a substring (query) of length M appears either exactly or is within a Hamming distance of K from the query. We analyze the exact pattern matching problem where M consecutive symbols from x and is presented as a query, and the approximate pattern matching problem where we assume a noisy version of a substring. Our proposed algorithm is evaluated based on the sketching complexity, and the computational complexity in answering the query. Using a sparse Fourier transform computation based approach we show that all such matches can be determined with high probability in sub-linear time and space. Further, we present several extensions including optimization for longer query lengths, algorithmic improvements for correlated data sources, and a secured matching algorithm in an outsourced pattern matching setting.