Sparse Approximation and Optimization in High Dimensions

Solutions of certain PDEs and variational problems may be characterized by "a few significant degrees of freedom", and one may want to take advantage of this feature in order to design efficient numerical solutions. Examples of such situations are ubiquitous: adaptive solution of PDEs, degenerate PDEs for image processing, crack modelling and free-discontinuity problems, viscosity solutions of Hamilton-Jacobi equations, digital signal coding/decoding, and compressed sensing. In the first part of the talk we review the role of variational principles, in particular L1-minimization, as a method for sparsifying solutions in several contexts. Then we address particular applications and numerical methods. We present the analysis of a superlinearly-convergent algorithm for L1 minimization based on an iteratively re-weighted least-squares method.

An analogous algorithm is then applied for the efficient solution of a system of degenerate PDEs for image recolorization in a relevant real-life problem of art restoration. We give a short description of a few advances in the use of this sparsity promoting algorithm for certain learning theory problems. This introduces us to other algorithms for performing efficiently L1 minimization, based on projected gradient methods and subspace-correction/domain-decomposition methods, and their modifications for free-discontinuity problems. The second part of the talk addresses the issue of embedding compressibility in numerical simulation, and in particular the use of adaptive strategies for the solution of elliptic partial differential equations discretized by means of redundant frames. We discuss the construction of wavelet frames on bounded domains and the optimal performances of adaptive solvers in this context. We conclude the talk with a vision of the prospectives in this field and several new open questions.