Files and links (1)
Free to read and download, Open Access
Dissertation
Convex and non-convex optimizations for recovering structured data: algorithms and analysis
University of Iowa
Doctor of Philosophy (PhD), University of Iowa
Autumn 2017
DOI: 10.17077/etd.0yedhxay
Abstract
<p>Optimization theories and algorithms are used to efficiently find optimal solutions under constraints. In the era of “Big Data”, the amount of data is skyrocketing,and this overwhelms conventional techniques used to solve large scale and distributed optimization problems. By taking advantage of structural information in data representations, this thesis offers convex and non-convex optimization solutions to various large scale optimization problems such as super-resolution, sparse signal processing,hypothesis testing, machine learning, and treatment planning for brachytherapy.</p>
<p>Super-resolution: Super-resolution aims to recover a signal expressed as a sum of a few Dirac delta functions in the time domain from measurements in the frequency domain. The challenge is that the possible locations of the delta functions are in the continuous domain [0,1). To enhance recovery performance, we considered deterministic and probabilistic prior information for the locations of the delta functions and provided novel semidefinite programming formulations under the information. We also proposed block iterative reweighted methods to improve recovery performance without prior information. We further considered phaseless measurements, motivated by applications in optic microscopy and x-ray crystallography. By using the lifting method and introducing the squared atomic norm minimization, we can achieve super-resolution using only low frequency magnitude information. Finally, we proposed non-convex algorithms using structured matrix completion.</p>
<p>Sparse signal processing: L1 minimization is well known for promoting sparse structures in recovered signals. The Null Space Condition (NSC) for L1 minimization is a necessary and sufficient condition on sensing matrices such that a sparse signal can be uniquely recovered via L1 minimization. However, verifying NSC is a non-convex problem and known to be NP-hard. We proposed enumeration-based polynomial-time algorithms to provide performance bounds on NSC, and efficient algorithms to verify NSC precisely by using the branch and bound method.</p>
<p>Hypothesis testing: Recovering statistical structures of random variables is important in some applications such as cognitive radio. Our goal is distinguishing two different types of random variables among n>>1 random variables. Distinguishing them via experiments for each random variable one by one takes lots of time and efforts. Hence, we proposed hypothesis testing using mixed measurements to reduce sample complexity. We also designed efficient algorithms to solve large scale problems.</p>
<p>Machine learning: When feature data are stored in a tree structured network having time delay in communication, quickly finding an optimal solution to the regularized loss minimization is challenging. In this scenario, we studied a communication-efficient stochastic dual coordinate ascent and its convergence analysis.</p>
<p>Treatment planning: In the Rotating-Shield Brachytherapy (RSBT) for cancer treatment, there is a compelling need to quickly obtain optimal treatment plans to enable clinical usage. However, due to the degree of freedom in RSBT, finding optimal treatment planning is difficult. For this, we designed a first order dose optimization method based on the alternating direction method of multipliers, and reduced the execution time around 18 times compared to the previous research.</p>
Details
- Title: Subtitle
- Convex and non-convex optimizations for recovering structured data: algorithms and analysis
- Creators
- Myung Cho - University of Iowa
- Contributors
- Weiyu Xu (Advisor)Soura Dasgupta (Committee Member)Xiaodong Wu (Committee Member)Mathews Jacob (Committee Member)Qihang Lin (Committee Member)
- Resource Type
- Dissertation
- Degree Awarded
- Doctor of Philosophy (PhD), University of Iowa
- Degree in
- Electrical and Computer Engineering
- Date degree season
- Autumn 2017
- Publisher
- University of Iowa
- DOI
- 10.17077/etd.0yedhxay
- Number of pages
- xvi, 251 pages
- Copyright
- Copyright © 2017 Myung Cho
- Comment
This thesis has been optimized for improved web viewing. If you require the original version, contact the University Archives at the University of Iowa: https://www.lib.uiowa.edu/sc/contact/.
- Language
- English
- Description illustrations
- illustrations (some color)
- Description bibliographic
- Includes bibliographical references (pages 236-251).
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9983776721602771
Metrics
776 File views/ downloads
211 Record Views