Doctoral Dissertation Defense: Seyedahmad Mousavi

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 non-convex) 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.