Sparse Optimization: Algorithms, Theory, and Software
Abstract
Statement of Work:The PI will develop methods for solving large-scale optimization problems for problems arising in sensor processing, statistics, and big data.Objective:The objective of this proposal is to develop techniques for sparse optimization, which is a class of Optimizationproblems designed to yield solutions that satisfy some notion of low complexity. Modern application of sparseoptimization abound: in machine learning, computational statistics, and signal processing, sparsity (and moregenerally, low complexity) have proven effective in exposing meaningful structure present in underlying data, or in deriving a simplified description of a process. In machine learning, for example, low-complexity solutions are crucial for obtaining meaningful and simplified inference procedures. Applications include robust classification and recommender systems. Compressed sensing provides another notable example: it specifies conditions under which it is possible torecover a signal by taking far fewer measurements than its ambient dimension. In almost all cases, a crucialcomputational step is to solve a non-smooth optimization problem designed to yield a sparse solution. In practice,sparse-recovery applications give rise to highly structured large-scale optimization problems. New applications and problem formulations continue to make it clear that existing theories often are not adequate. New technologies, such as fast digital-data acquisition in traditional fields such as signal processing, give rise to vast problems that challenge our notions of the effectiveness of current workhorse algorithms. The aim of the research in this proposal is to designprincipled algorithms, supporting theory that establishes guarantees, and software implementations for the solution of sparse optimization problems at unprecedented scale. Because reliablesoftware implementation is essential for effectively transferring optimization to practitioners and researchers in other fields, it is an integral component of this research program.Approach:Several different approaches to the problems outlined above are explored. All are based on exploiting useful structure to avoid the pitfalls that plague current workhorse algorithms, and make them unsuitable for large problems (e.g., because they rely on prohibitively expensive computational kernels such as eigenvalue decompositions), or for problems with difficult data (e.g., ill-conditioning that prevents first-order methods from converging). Several different approaches will be considered. An essential step in developing practical approaches for efficiently optimizing modelswith huge numbers of variables is to identify useful structure that can be exploited by implementable algorithms. Several research directions are planned:-- Exploit sparse-recovery guarantees that ensure that the underlying sparse optimization problems have far fewer constraints than variables. This is accomplished by phrasing sparse optimization problems in the framework of gauge optimization, and solving certainhighly structured and relatively small dual problems.-- The objective-constraint reversal procedure pioneered by the PI and collaborators has been the basis for the very successful SPGL1 software package. Research will be conducted for applying this reversal procedure to matrix-valued problems. Preliminary results show that the correct formulations can be used to completely avoid the cost of the proximal iteration, using Frank-Wolfe-type algorithms.--Develop a software architecture based on fact that an enormous family of sparsity- promoting regularizers and their proximal maps fit into the framework of quadratic support functions. This point of view potentially allows for a single efficient implementation to apply to a wide variety of problems.Overall Merit and ONR Mission/Relevance:The PI has proposed innovative methods for solving large-scale optimization problems arising in signal analysis, statistics, and big data. In particular, h
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 26, 2018
- Source ID
- N000141612242
Entities
People
- Michael Friedlander
Organizations
- Office of Naval Research
- United States Navy
- University of California, Davis