Topics in Sparse Recovery via Constrained Optimization: Least Sparsity, Solution Uniqueness, and Constrained Exact Recovery

Tuesday, November 5, 2019 - 1:25pm - 2:25pm
Lind 305
Seyedahmad Mousavi (University of Minnesota, Twin Cities)
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 talk is to present 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. 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 $\ell_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