Convergence of a greedy algorithm for high-dimensional convex nonlinear problems

By É. Cancès, Virginie Ehrlacher, Tony Lelièvre. 2010

77 citations recorded by the source corpus.

In this article, we present a greedy algorithm based on a tensor product decomposition, whose aim is to compute the global minimum of a strongly convex energy functional. We prove the convergence of our method provided that the gradient of the energy is Lipschitz on bounded sets. The main interest of this method is that it can be used for high-dimensional nonlinear convex problems. We illustrate this method on a prototypical example for uncertainty propagation on the obstacle problem.

Subfields: Computational Mechanics, Statistical and Nonlinear Physics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Statistical and Nonlinear Physics

In Statistics and Probability

Citations in the corpus

A literature survey of low‐rank tensor approximation techniques (2013, neutral): “Convergence results in this direction can be found in [3, 40, 41, 85–87, 180].”
Low-rank methods for high-dimensional approximation and model order reduction (2015, unknown): “u,w) = ku−wk, conditions for the convergence of greedy algorithms in a general setting can be found in [81]. In the case of the minimization of convex functionals, convergence results can be found in [11, 13, 39, 82]. Note that this greedy construction is not speciﬁc to the particular setting of ten”
F ¨ Ur Mathematik in Den Naturwissenschaften Leipzig on Minimal Subspaces in Tensor Representations on Minimal Subspaces in Tensor Representations (unknown): “…in numerical analysis for the solution of problems defined in high-dimensional tensor spaces, such as PDEs arising in stochastic calculus [1] [4] [9] (e.g., Fokker-Planck equation), stochastic parametric PDEs arising in uncertainty quantification with spectral approaches [18] [8] [19], and…”
Fast Solution of Parabolic Problems in the Tensor Train/Quantized Tensor Train Format with Initial Application to the Fokker-Planck Equation (2012, methodology): “Various solution methods, based on the Monte Carlo approach [43], direct treatment via the spectral methods for lowdimensional examples [32, 7]; greedy algorithms to compute sums of separable tensor products [11, 1, 31, 5] (the so-called canonical tensor format or PARAFAC [18, 17, 6]) were developed”
Proper generalized decomposition for nonlinear convex problems in tensor Banach spaces (2011, unknown): “In particular, the progressive PGD de ned in [7] coincides with a PGD where αk = c for all k ≥ 1.”
Tensor-product approach to global time-space-parametric discretization of chemical master equation (2012, methodology): “As such reduced grid-based methods, we would like to mention the sparse grids technique [13], as well as the initial tensor-structured approaches: the greedy algorithm in the canonical tensor format [14, 15, 16, 17, 18], and the solver in the Tucker format, based on the manifold dynamics via the pro”
Greedy Approximation of High-Dimensional Ornstein–Uhlenbeck Operators (2011, unknown): “…that manipulates minimizers of Dirichlet energies instead of stationary points to the associated Euler–Lagrange equations (in the follow-up paper [CEL11] by Canc`es, Ehrlacher and Leli`evre it was further shown that one can also work with local—yet still energy-decreasing— minimizers provided…”
Tensor-based methods for numerical homogenization from high-resolution images (2013, background): “Theoretical convergence properties have been recently obtained for a class of PGD algorithms [7, 15, 16].”