Stability of compressed sensing for dictionaries and almost sure convergence rate for the Kaczmarz algorithm

Abstract

This dissertation consists of two topics: compressed sensing and the Kaczmarz algorithm.

Compressed sensing addresses the problem of recovering an unknown signal $z_0in mathbb{R}^d$ from a small number of linear measurements based on an underlying structure of sparsity or compressibility. This dissertation will focus on the $ell^q$ minimization approach. We show that the null space property is a necessary and sufficient condition on the measurement matrix for stable recovery. Moreover, we consider the compressed sensing problem when signals are sparse in a dictionary. Some basic conditions are given for this problem to be meaningful. It is known that under an appropriate restricted isometry property for a dictionary, reconstruction methods based on $ell^q$ minimization can provide an effective signal recovery tool even when the dictionary is coherent. We propose that a modified null space property for the dictionary is also sufficient to stably recover the signal. Perturbations on the measurement matrices and the dictionary are also considered.

The second part of this dissertation is concerned with the almost sure convergence rate of the Kaczmarz algorithm. The Kaczmarz algorithm is an iterative method for reconstructing a signal $xinmathbb{R}^d$ from an overcomplete collection of linear measurements $y_n = langle x, varphi_n angle$, $n geq 1$. This algorithm is widely used in image processing and computer tomography. We prove quantitative bounds on the rate of almost sure exponential convergence in the Kaczmarz algorithm for suitable classes of random measurement vectors ${varphi_n}_{n=1}^{infty} subset mathbb{R}^d$. Refined convergence results are given for the special case when each $varphi_n$ has i.i.d. Gaussian entries and, more generally, when each $varphi_n/|varphi_n|$ is uniformly distributed on $mathbb{S}^{d-1}$.