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

This dissertation consists of two topics: compressed sensing and the Kaczmarz algorithm. Compressed sensing addresses the problem of recovering an unknown signal z0 ∈ Rd from a small number of linear measurements based on an underlying structure of sparsity or compressibility. There are generally two approaches for solving this problem. This dissertation will focus on the ℓ q minimization approach. The classical result is that ℓ q minimization can stably recover an almost sparse signal from its noisy measurements when the measurement matrix satisfies a so called restricted isometry property. Other conditions on measurement matrices are explored for stable recovery. We show that the null space property is a necessary and sufficient condition on the measurement matrix for stable recovery.;When the signal is sparse in an overcomplete dictionary, we have the compressed sensing problem 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 ℓ 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 x ∈ Rd from an overcomplete collection of linear measurements y n = ⟨x, ϕn⟩, n ≥ 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 &cubl0;4n&cubr0;infinityn=1 ⊂Rd . Refined convergence results are given for the special case when each ϕ n has i.i.d. Gaussian entries and, more generally, when each ϕ n/||ϕn|| is uniformly distributed on Sd-1 .