Phase transitions in deterministic compressed sensing, with application to magnetic resonance spectroscopy
Abstract/Contents
- Abstract
- Undersampled measurement schemes are ubiquitous throughout science and engineering. Compressed sensing is an undersampling theory that has significantly impacted many engineering applications such as MRI imaging, seismic exploration, NMR logging, and NMR spectroscopy. The theory of compressed sensing posits that a "sufficiently sparse" signal can be undersampled yet acquired exactly. This reduction in the number of required samples is achieved by acquiring measurements in a particular way and then reconstructing the signal by a nonlinear algorithm. A fundamental question in compressed sensing is "for a given reconstruction algorithm, how much information is needed to successfully acquire a compressible signal of a given complexity." To answer this question, researchers have come up with different theories using different mathematical tools such as coherence, restricted isometry property, and phase transition. Amongst these, the phase transition approach pioneered by Donoho and Tanner is the only approach that gives an accurate answer and provides precise predictions that match the experimental observations. The Donoho-Tanner predictions of phase transitions rely on the assumption that the sensing matrix has Gaussian i.i.d. entries -- an assumption that is rarely satisfied in engineering applications. Nonetheless, for an important collection of deterministic matrices used in engineering we have shown that the reconstruction of sparse objects by convex optimization works well -- in fact just as well as for true random matrices. In other words, the theories established for the Gaussian random matrices are equally applicable to many other non-random matrices. Though the Gaussian phase transition curves, also known as the ``Donoho-Tanner" curves, are universal across many deterministic sensing matrices, there is a suite of undersampling matrices that exhibit a rather different behavior; For instance, in multi-dimensional Nuclear Magnetic Resonance (NMR) spectroscopy when free induction decay is measured across multiple time dimensions, one typically acquires anisotropic undersampled measurements by exhaustive sampling in certain time dimensions and partial sampling in others. Moreover, the signal acquired in these experiments belong to the set of hypercomplex numbers, and more recent undersampling techniques such as partial component sampling (PCS) take advantage of this fact by randomly acquiring only certain low-dimensional components of each high-dimensional hypercomplex entry. Little is known about the reconstruction behavior of such undersampling schemes in the relevant mathematical literature. In this thesis, we first provide a classification of various hypercomplex-aware undersampling schemes, and define a hypercomplex-aware measure of coherence that can be used to quantify the size and extent of the corresponding undersampling artifacts. We then show that for NMR undersampling schemes the ability of a convex optimizer to recover the unknown signal from undersampled measurements is significantly worse than the known Gaussian phase transitions. In particular, we show that the compressed sensing phase transitions of anisotropic undersampling schemes in NMR matches those of block diagonal matrices. We establish precise equivalence between NMR undersampling schemes and block diagonal matrices. We then provide finite-N predictions of phase transitions for block diagonal matrices, which are directly applicable to sampling methods in NMR spectroscopy.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2016 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Monajemi, Hatef |
|---|---|
| Associated with | Stanford University, Department of Civil and Environmental Engineering. |
| Primary advisor | Donoho, David Leigh |
| Primary advisor | Rajagopal, Ram |
| Thesis advisor | Donoho, David Leigh |
| Thesis advisor | Rajagopal, Ram |
| Thesis advisor | Hoch, Jeffrey C |
| Thesis advisor | Saunders, Michael |
| Advisor | Hoch, Jeffrey C |
| Advisor | Saunders, Michael |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Hatef Monajemi. |
|---|---|
| Note | Submitted to the Department of Civil and Environmental Engineering. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2016. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2016 by Hatef Monajemi
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...