Fast Graph Algorithms by Sparsification and Approximate Elimination
Abstract
Statement of Work:The PI will develop generalizations of recent algorithms that exploit approximate elimination, sparsification, anditerative refinement. He will apply the new algorithms to the solution of graph-structured inference and optimization problems.Objective:The objective is to develop faster and more accurate solutions to graph-structured inference and optimization problems including: interpolation on networks by the computations of lexicographic minimizers and energy minimizers in directed networks; constraint satisfaction problems such as maximum cut, minimum bisection, graph coloring and unique games; isotonic regression; and, the computation of the leading eigenvectors of and the solution of linear equations in connection Laplacians that arise in signal processing problems.Approach:The PI will build on and generalize the sparsified multigrid and sparsifed Cholesky algorithms that were recently developed by the PI. This will involve new analyses of concentration of random matrices and the application of these analyses to sparsification, along with the extension of these analyses to nonlinear problems. It will also require the generalization of iterative refinement to new families of problems.Overall Merit and ONR Mission/Relevance:The algorithms to be developed will enable rapid inference and decision making from big data sets, as well as improve the quality of inferences made from large, noisy data sets. Much of the data gathered by battlefield sensors will necessarily be both noisy and lossy. The algorithms to be developed will provide new and fast ways of optimizing decisions with large data sets that are highly corrupted. This will enable on-site computation by small computers that using present algorithmic techniques would require lengthy computation by supercomputers. Other applications of the algorithms include means to make inferences about individuals in a social network from information gathered about their contacts in the network, and means to combine multiple noisy images of a (possibly moving) object to obtain a high-fidelity image.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Aug 12, 2016
- Source ID
- N000141612374
Entities
People
- Daniel Spielman
Organizations
- Office of Naval Research
- United States Navy
- Yale University