Combinatorial and geometric structures, convex optimization leading to matrix recovery
Abstract
The proposed research will examine two problems in convex optimization: matrix recovery, and the structure of convex cones. Objective The proposed research will focus on developing theory and efficient algorithms for solving problems in convex optimization. One problem of interest is the matrix-recovery problem. Modern applications such as signal and image processing, computer vision, compressed sensing, data mining in big data bases typically require us to compute a matrix satisfying some convex constraints and of minimal rank. Such problems are typically hard and one useful approach is to express a tractable relaxation of this non-convex problem as a convex optimization problem. The proposed research will develop efficient interior-point algorithms for the matrix-recovery problem. In addition, the research will further develop the theory of convex optimization by examining the geometrical structure of convex cones. Approach The approach will be to focus on the following two problems: 1) Matrix recovery via convex optimization: In some applications, we deal with the phenomenon that a very small dimensional structure is responsible for the main behavior of a system, however, we can only observe the behavior of the system in terms of very high dimensional variables. Then the main task is, given an extremely large number of observations of this high dimensional data, deduce the low-dimensional structure that gave rise to it. Applications are abound in signal and image processing, sparse signal recovery, compressed sensing, system identification and control. In some other systems, we need to operate with extreme caution with respect to how close our solution is to the boundary conditions. In this latter case, we are interested in solutions that are far away from every boundary condition (or constraint) or a least from every element of a specific, critical subset of constraints. Typically, this can be achieved very naturally and efficiently via interior-point methods. If the variable space is embedded in a matrix space, this typically means, we want a matrix of maximum rank. Interestingly, one of the best tools to approach both problems is convex optimization. Low rank matrix recovery will be pursued via strong convex relaxations and the high rank matrix recovery via suitably adapted interior-point methods. We propose to continue our construction of min-max theorems via semidefinite programming and convex optimization relaxations and continue our development of efficient primal-dual interior-point algorithms for convex optimization. 2) Geometry and boundary structure of convex cones: Understanding the boundary structure of convex sets (and equivalently convex cones) is paramount in designing efficient algorithms for the solution of convex optimization problems and proving duality theorems. The goal of this module of the research program is to improve our understanding of the geometry and boundary structure of hyperbolic convex cones and their generalizations. In general convex cone setting, we will look for characterizations of facial exposedness and facial dual completeness as they relate to convex representations and duality theorems for convex optimization. Overall Merits and ONR Mission Relevance Convex optimization plays an important role in many Navy-relevant engineering problems, such as compressive sensing for signal and image processing. The proposed research will develop theory and efficient algorithms for solving convex optimization problems.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Aug 12, 2016
- Source ID
- N000141512171
Entities
People
- Levent Tunçel
Organizations
- Office of Naval Research
- United States Navy
- University of Waterloo