Dissertation/Thesis Abstract

Topics in Sparse Recovery via Constrained Optimization: Least Sparsity, Solution Uniqueness, and Constrained Exact Recovery
by Mousavi, Seyedahmad, Ph.D., University of Maryland, Baltimore County, 2019, 206; 22623638
Abstract (Summary)

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.

Indexing (document details)
Advisor: Shen, Jinglai
Commitee: Draganescu, Andrei, Gowda, Muddappa Seetharama, Kim, Seung-Jun, Potra, Florian
School: University of Maryland, Baltimore County
Department: Mathematics, Applied
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
Publication Number: 22623638
ISBN: 9781392548356
Copyright © 2020 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy