A joint project of the Graduate School, Peabody College, and the Jean & Alexander Heard Library

Title page for ETD etd-06012012-105002


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
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}$.

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.pdf 523.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.