Using prior support information in compressed sensing

Compressed sensing is a data acquisition technique that entails recovering estimates of sparse and compressible signals from $n$ linear measurements, significantly fewer than the signal ambient dimension $N$. In this thesis we show how we can reduce the required number of measurements even further if we incorporate prior information about the signal into the reconstruction algorithm. Specifically, we study certain weighted nonconvex $\ell_p$ minimization algorithms and a weighted approximate message passing algorithm. In Chapter 1 we describe compressed sensing as a practicable signal acquisition method in application and introduce the generic sparse approximation problem. Then we review some of the algorithms used in compressed sensing literature and briefly introduce the method we used to incorporate prior support information into these problems. In Chapter 2 we derive sufficient conditions for stable and robust recovery using weighted $\ell_p$ minimization and show that these conditions are better than those for recovery by regular $\ell_p$ and weighted $\ell_1$. We present extensive numerical experiments, both on synthetic examples and on audio, and seismic signals. In Chapter 3 we derive weighted AMP algorithm which iteratively solves the weighted $\ell_1$ minimization. We also introduce a reweighting scheme for weighted AMP algorithms which enhances the recovery performance of weighted AMP. We also apply these algorithms on synthetic experiments and on real audio signals.