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.
Citation
Gao, Jiahui (2020). Applications of Sparse Signal Recovery: 2D-Pattern Matching and Sparse Walsh-Hadamard Transform Computation. Master's thesis, Texas A&M University. Available electronically from https : / /hdl .handle .net /1969 .1 /192751.