Efficient Optimization via Sparsification with Applications to Fast Fourier Optimization, Compressive Sensing, and other Machine-Learning Problems
Abstract
Broadly speaking, this project has three distinct, but related, directions. The rst direction is to continue to look for real-world linear optimization problems that are considered di cult because they are large and the constraint matrix is dense. For such problems, the goal is to see if some reformulation of the problem yields a sparser representation that can then be solved much more quickly than the densely formulated version of the problem. In previous work, the PI used this idea in the context of an important optical design problem for high-contrast imaging. The problem involves two-dimensional Fourier transforms. The sparsi cation idea in this context is based on the observation that the kernel" matrix for the 2D transform is the Kronecker product the 1D kernel with itself. The product is a large dense matrix, but the factors are very sparse. Writing the model using the factors yielded a dramatic perform improvement. Recently, the PI working with some of his colleagues realized that similar Kronecker products come up in the area of compressed sensing. Again dramatic improvements were obtained. There are undoubtedly other unrealized real-world problems where this idea can be employed. The rst goal of this project is to nd such problems. The compressed sensing problem mentioned above led the PI to look at many problems in the world of statistics and big data. It turns out that many problems in this arena have some regularization parameter whose value is not known a priori. This quickly led to the realization that the parametric simplex method could be used to nd the optimal solution for all values of the unknown parametric in essentially the same time some other algorithm would need to nd just one soluton. Testing this idea on the so-called LAD-Lasso problem has shown it to be very e ective. A second goal of this project is to look for other examples, in statistics and elsewhere, for which one needs to solve a linear programming problem with an undetermined parameter. The third direction is to look at algorithms for semide nite programming problems that are based on expressing the semide niteness constraint in a simple algebraic manner and then using standard algorithms for nonlinear programming to solve the problem. One such approach proposed by the PI some years ago uses the fact that a matrix is positive semidef- inite if and only if its so-called LDLT factorization has the property that all elements of the diagonal matrix D are nonnegative. Another way to do this is to use the fact that a matrix is symmetric and positive semide nite if and only if it can be written as the product of a matrix and the transpose of that matrix. The rst method preserves algebraic convexity of the problem but the formulas are rather complicated. The second method violates algebraic convexity but preserves geometric convexity and is very easy to implement. Recent experi- ments, desribed later in this proposal, suggest that the second method works quite well on many real-world SDP problems. The third goal of this proposal is to further pursue this direction of research.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jun 10, 2016
- Source ID
- N000141612162
Entities
People
- Robert Vanderbei
Organizations
- Office of Naval Research
- Trustees of Princeton University
- United States Navy