Finite Length Analysis of Verifcation-Based Message Passing Algorithms in Compressed Sensing

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.


Farhangdoust, Seyed Mohammad Ebrahim




Compressed sensing (CS) is a newly developed area in signal processing which generally aims at compressing sparse signals. The most challenging part of a CS problem can be the recovery process in which a signal will be reconstructed from its measurements. In this thesis, we address the finite length analysis of verification-based message-passing algorithms (VB MPAs), analytically. In contrary to asymptotic regime analysis, the finite length analysis is fairly an untouched problem. We begin the analysis by characterizing the problematic combinatorial structures, defined over the measurement graph of the CS system in which VB algorithms are trapped. Then, based on this characterization, we derive exact expressions for the average probability of error of a given ensemble of graphs, and also for a given individual graph. The analysis for the individual graph is also shown to be useful for the introduction and estimation of error floors in VB MPAs in CS.


Engineering - Electronics and Electrical




Carleton University

Thesis Degree Name: 

Master of Applied Science: 

Thesis Degree Level: 


Thesis Degree Discipline: 

Engineering, Electrical and Computer

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).