Applications of Sparse Signal Recovery: 2D-Pattern Matching and Sparse Walsh-Hadamard Transform Computation

Abstract

We study two problems related to sparse signal recovery. The first problem considered is querying a sub-image of size square of M in a large image database of size square of N to determine all the locations where sub-image appears. We use sparse graph based codes Fourier transform computation to compute the peaks in the 2-D correlation to determine the matching positions in a computationally efficient manner. We then design a 2-D pattern that can facilitate vision based positioning by enabling the use of our algorithm for fast pattern matching. The second problem studied is the computation of sparse Walsh-Hadamard transform for binary data. We consider signals that are sparse in Walsh-Hadamard tranform domain where the non-zero coefficients are all ones. A possible application of this algorithm is learning an undirected unweighted graph by using a sub-sample version of its evaluation. We design an adaptive algorithm for sparse WHT computation. Adaptivity provides an opportunity to recover more than one non-zero coefficient aliased together in each iteration so that a faster recovery can be expected given the same amount of sub-samples. It is shown that with the same amount sample, the probability of error of our proposed algorithm is lower compared to the earlier work.