START Prize 2008 - Sparse Approximation and Optimization in High Dimensions
The dimension scale of problems arising in our modern information society became very large. A new area of science and engineering is now urgently needed in order to extract and interpret significant information from the universe of data collected from a variety of modern sources (Internet, physics experiments, medical diagnostics, etc.). Numerical simulations at the required scale will be one of the great challenges of the 21st century. In short, we need to become capable of organizing and understanding complexity. The most notable recent advances in data analysis and numerical simulation are based on the observation that in several situations, even for very complex phenomena, only a few governing components are required to describe the whole dynamics; a dimensionality reduction can be achieved by demanding that the solution be "sparse" or "compressible". Since the relevant degrees of freedom are not prescribed, and may depend on the particular solution, we need efficient optimization methods for solving the hard combinatorial problem of identifying them. In this project we will first address the problem of designing efficient algorithms which allow us to achieve sparse optimization in high-dimensions. Secondly, the tools which we will develop for achieving adaptive dimensionality reductions will subsequently be use as building blocks for solving large-scale partial differential equations or variational problems arising in various contexts. Finally, we will apply the whole machinery to interesting applications in image processing, free-discontinuity and -boundary problems, such as corrosion detection and crack identification, and we will explore new applications in innovative fields such as automatic learning. To do all of this, we will have to face several profound mathematical problems, such as the determination of well-conditioned column splitting of general matrices (called paving), the difficult estimation of the complexity of the algorithms we propose, and establishing their ability to compute the nearly-sparsest solution of the problem at hand. Tools from several different mathematical branches are needed. The relevant mathematics will include methods from applied harmonic analysis, functional analysis, probability theory, convex optimization, and calculus of variations. The main numerical techniques will include iterative thresholding algorithms, operator compression, random alternating projections, subspace correction, and domain decomposition methods.