Search-based methods for the sparse signal recovery problem in compressed

Karahanoğlu, Nazım Burak (2013) Search-based methods for the sparse signal recovery problem in compressed. [Thesis]

[thumbnail of NazımBurakKarahanoglu_461279.pdf] PDF

Download (4MB)


The sparse signal recovery, which appears not only in compressed sensing but also in other related problems such as sparse overcomplete representations, denoising, sparse learning, etc. has drawn a large attraction in the last decade. The literature contains a vast number of recovery methods, which have been analysed in theoretical and empirical aspects. This dissertation presents novel search-based sparse signal recovery methods. First, we discuss theoretical analysis of the orthogonal matching pursuit algorithm with more iterations than the number of nonzero elements of the underlying sparse signal. Second, best-first tree search is incorporated for sparse recovery by a novel method, whose tractability follows from the properly defined cost models and pruning techniques. The proposed method is evaluated by both theoretical and empirical analyses, which clearly emphasize the improvements in the recovery accuracy. Next, we introduce an iterative two stage thresholding algorithm, where the forward step adds a larger number of nonzero elements to the sparse representation than the backward one removes. The presented simulation results reveal not only the recovery abilities of the proposed method, but also illustrate optimal choices for the step sizes. Finally, we propose a new mixed integer linear programming formulation for sparse recovery. Due to the equivalency of this formulation to the original problem, the solution is guaranteed to be correct when it can be solved in reasonable time. The simulation results indicate that the solution can be found easily under some reasonable assumptions, especially for signals with constant amplitude nonzero elements.
Item Type: Thesis
Uncontrolled Keywords: Compressed sensing. -- Sparse signal recovery. -- Best-first tree search. -- Forward-backward search. -- Mixed integer linear programming. -- Sıkılaştırmalı algılama. -- Seyrek işaretlerin geri çatılması. -- İlk en iyiye ağaç araması. -- İleri-geri arama. -- Karışık tam sayılı doğrusal programlama.
Subjects: T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800-8360 Electronics
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Electronics
Faculty of Engineering and Natural Sciences
Depositing User: IC-Cataloging
Date Deposited: 20 Dec 2014 13:44
Last Modified: 26 Apr 2022 10:03

Actions (login required)

View Item
View Item