Sparse Optimization: Algorithms, Theory, and Software
Abstract
PROJECT ABSTRACT Sparse optimization: algorithms, theory, and software Michael P. Friedlander University of British Columbia Many applications in signal processing and machine learning need to solve mathematical optimization problems whose solutions satisfy some notion of low complexity|such as vectors that have few nonzero entries, or matrices that are low rank. This describes the class of sparse optimization problems, in which the aim is often to nd the "best" compact representation of some object. Two de ning characteristics make these problems especially di cult to solve: they are nonsmooth, and practical applications give rise to potentially vast problems that challenge existing notions about the e ectiveness of workhorse algorithms. The proposed approach exploits sparse-recovery guarantees that ensure that the underlying sparse optimization problems will have many fewer constraints than variables. This is accomplished by solving certain dual optimization problems in which the number of variables lie in a space whose dimension is the number of measurements. These dual solutions are then used to recover the required solution of the original problem by solving small subproblems of a size that is on the order of the solution complexity. The approach is based on phrasing sparse optimization problems within the class of gauge optimization, which captures many of the optimization problems needed for sparse recovery. The proposed research includes algorithm development and analysis for semide nite optimization prob- lems with low-rank solutions, and for certain conic optimization problems with product-form structure. Eigenvalue computation is a key subproblem for the proposed approach, so research is planned for optimization-based iterative methods for computing extreme eigenvalues and eigen- vectors for large-scale problems. Algorithmic techniques to be considered include variations of subgradient and bundle methods based on novel function approximations derived from tight spectral lower models, and smoothing based on in mal convolution. The most signi cant portion of the requested budget supports two graduate students and a postdoc who will work on algorithms for large-scale sparse optimization. Intellectual merit The proposed research involves the development of fundamental theoretical and algorithmic tools for convex optimization and analysis. The resulting computational methods will be useful for solving real-world applications. Theoretical breakthroughs in optimization can be used by other researchers as the basis for new algorithmic approaches in optimization. Broader impacts In many contexts, optimization is a vital part of a larger procedure; it is therefore critical that optimization algorithms be fast and reliable. Advances in e ciency and robustness are welcomed by optimization users in industry and academia. The proposed research will have an impact on three groups: researchers in optimization, researchers in speci c application elds, and industry practitioners. Optimization often forms a computational kernel for a range of scienti c and engineering applications, including machine learning, signal processing, and medical-treatment planning. Algorithm advances thus have the potential for immediate impact in engineering and in other areas of natural science.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jan 04, 2017
- Source ID
- N000141712009
Entities
People
- Michael P. Friedlander
Organizations
- Office of Naval Research
- United States Navy
- University of British Columbia