Type of Document Dissertation Author Chen, Xuemei Author's Email Address anotherdai@gmail.com URN etd-06012012-105002 Title Stability of compressed sensing for dictionaries and almost sure convergence rate for the Kaczmarz algorithm Degree PhD Department Mathematics Advisory Committee

Advisor Name Title Akram Aldroubi Committee Chair Alexander Powell Committee Co-Chair Douglas Hardin Committee Member Edward Saff Committee Member Xenofon Koutsoukos Committee Member Keywords

- stability
- compressed sensing
- Kaczmarz Algorithm
- randomization
- null space property
- dictionary
Date of Defense 2012-04-24 Availability unrestricted AbstractThis 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}$.

Files

Filename Size Approximate Download Time (Hours:Minutes:Seconds)

28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access CHEN_dissertation.pdf523.18 Kb 00:02:25 00:01:14 00:01:05 00:00:32 00:00:02

Browse All Available ETDs by
( Author |
Department )

If you have more questions or technical problems, please Contact LITS.