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, financial data, 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 the complexity of large amount of data. 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 the START-project we have been first addressing the problem of designing efficient algorithms which allow us to perform sparse optimization in high-dimension. Secondly, the tools which we developed for achieving adaptive dimensionality reductions were subsequently used as building blocks for solving large-scale partial differential equations or variational problems arising in various contexts. Finally, we were applying the whole machinery to interesting applications in image processing, numerical simulation, and, recently, we also explored new applications in innovative fields such as automatic learning and control of large dynamical systems in high-dimension.As a highlight of the project and among the most relevant achievements, we mention the comprehensive analysis of an algorithm, called iteratively-reweighted least squares. Not only we proved that this algorithm is able to solve very efficiently sparse optimization problems, but, in view of its intuitive and easy-to-do implementation and its possible adaptation to several other problems (sparse vector optimization, low rank matrix optimization, nonlinear PDEs), has become very popular among practitioners in several fields in applied mathematics, mathematical signal processing, computer science, and electrical engineering.Another important conceptual development of the project has been the fusion into the concept of mean-field sparse optimal control of the tools of sparse optimization and the so-called mean-field approximations for the descriptions of large systems of interacting agents. In simple words, we proved that the government of a social dynamics can be realized, in several situations by using exclusively parsimonious interventions, as soon as they are done properly, despite having limited resources at disposal. The message is both positive and negative. On the one side, if a society needs to improve its status, our mathematics is establishing that it is theoretically possible for a government to conduct it to a better good. On the other side, our results can be interpreted as a warning to the community that few relevant players can condition significantly the development of large societies, and, perhaps, this is not just theory.