Sparse recovery finds numerous applications in different areas, for example, engineering, computer science, business, applied mathematics, and statistics. Sparse recovery is often formulated as relatively large-scale and challenging constrained (convex or nonconvex) optimization problems. Constraints are ubiquitous and important in many applications of sparse recovery, but they make analysis and computation nontrivial and require novel techniques to handle them. The goal of this thesis is to develop numerical and analytical techniques for constrained sparse recovery using convex analysis and optimization tools. Three topics are investigated in the realm of constrained sparse recovery. First, we analyze quantitative adverse properties of different p-norm based optimization problems with p > 1, such as generalized basis pursuit, basis pursuit denoising, ridge regression, and elastic net. We show that their optimal solutions are least sparse for almost all measurement matrices and measurement vectors, and we compare these results with the case of 0 < p ≤ 1. Second, we study the solution uniqueness of an individual feasible vector of a class of convex optimization problems involving convex piecewise affine functions and subject to general polyhedral constraints. We apply these solution uniqueness results to a broad class of ℓ1-minimization problems in constrained sparse optimization, such as basis pursuit, LASSO, and polyhedral gauge recovery. Third, we propose a constrained matching pursuit algorithm for constrained sparse recovery and develop uniform conditions for exact support and vector recovery on constraint sets. The exact recovery via this algorithm not only depends on a measurement matrix but also critically relies on a constraint set. Hence, we identify an important class of constraint sets, called coordinate projection admissible. We then use the conic hull structure of these sets together with constrained optimization techniques to establish sufficient conditions for uniform exact recovery via this algorithm on coordinate projection admissible sets. These conditions are expressed in terms of the restricted isometry-like and the restricted orthogonality-like constants. We also revisit the classical orthogonal matching pursuit on the Euclidean space and construct a counterexample to a necessary condition for exact support recovery in the literature.
|Commitee:||Draganescu, Andrei, Gowda, Muddappa Seetharama, Kim, Seung-Jun, Potra, Florian|
|School:||University of Maryland, Baltimore County|
|School Location:||United States -- Maryland|
|Source:||DAI-B 81/7(E), Dissertation Abstracts International|
|Subjects:||Applied Mathematics, Electrical engineering|
|Keywords:||Sparse recovery, Constrained optimization, Least sparsity, Solution uniqueness, Constrained exact recovery|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be