A tensor approximation method based on ideal minimal residual formulations for the solution of high-dimensional problems

M. Billaud-Friess; A. Nouy; O. Zahm

ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique (2014)

  • Volume: 48, Issue: 6, page 1777-1806
  • ISSN: 0764-583X

Abstract

top
In this paper, we propose a method for the approximation of the solution of high-dimensional weakly coercive problems formulated in tensor spaces using low-rank approximation formats. The method can be seen as a perturbation of a minimal residual method with a measure of the residual corresponding to the error in a specified solution norm. The residual norm can be designed such that the resulting low-rank approximations are optimal with respect to particular norms of interest, thus allowing to take into account a particular objective in the definition of reduced order approximations of high-dimensional problems. We introduce and analyze an iterative algorithm that is able to provide an approximation of the optimal approximation of the solution in a given low-rank subset, without any a priori information on this solution. We also introduce a weak greedy algorithm which uses this perturbed minimal residual method for the computation of successive greedy corrections in small tensor subsets. We prove its convergence under some conditions on the parameters of the algorithm. The proposed numerical method is applied to the solution of a stochastic partial differential equation which is discretized using standard Galerkin methods in tensor product spaces.

How to cite

top

Billaud-Friess, M., Nouy, A., and Zahm, O.. "A tensor approximation method based on ideal minimal residual formulations for the solution of high-dimensional problems." ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique 48.6 (2014): 1777-1806. <http://eudml.org/doc/273105>.

@article{Billaud2014,
abstract = {In this paper, we propose a method for the approximation of the solution of high-dimensional weakly coercive problems formulated in tensor spaces using low-rank approximation formats. The method can be seen as a perturbation of a minimal residual method with a measure of the residual corresponding to the error in a specified solution norm. The residual norm can be designed such that the resulting low-rank approximations are optimal with respect to particular norms of interest, thus allowing to take into account a particular objective in the definition of reduced order approximations of high-dimensional problems. We introduce and analyze an iterative algorithm that is able to provide an approximation of the optimal approximation of the solution in a given low-rank subset, without any a priori information on this solution. We also introduce a weak greedy algorithm which uses this perturbed minimal residual method for the computation of successive greedy corrections in small tensor subsets. We prove its convergence under some conditions on the parameters of the algorithm. The proposed numerical method is applied to the solution of a stochastic partial differential equation which is discretized using standard Galerkin methods in tensor product spaces.},
author = {Billaud-Friess, M., Nouy, A., Zahm, O.},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique},
keywords = {high-dimensional problems; nonlinear approximation; low-rank approximation; proper generalized decomposition; minimal residual; stochastic partial differential equation; numerical examples; algorithm; convergence; Galerkin method; tensor product space},
language = {eng},
number = {6},
pages = {1777-1806},
publisher = {EDP-Sciences},
title = {A tensor approximation method based on ideal minimal residual formulations for the solution of high-dimensional problems},
url = {http://eudml.org/doc/273105},
volume = {48},
year = {2014},
}

TY - JOUR
AU - Billaud-Friess, M.
AU - Nouy, A.
AU - Zahm, O.
TI - A tensor approximation method based on ideal minimal residual formulations for the solution of high-dimensional problems
JO - ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique
PY - 2014
PB - EDP-Sciences
VL - 48
IS - 6
SP - 1777
EP - 1806
AB - In this paper, we propose a method for the approximation of the solution of high-dimensional weakly coercive problems formulated in tensor spaces using low-rank approximation formats. The method can be seen as a perturbation of a minimal residual method with a measure of the residual corresponding to the error in a specified solution norm. The residual norm can be designed such that the resulting low-rank approximations are optimal with respect to particular norms of interest, thus allowing to take into account a particular objective in the definition of reduced order approximations of high-dimensional problems. We introduce and analyze an iterative algorithm that is able to provide an approximation of the optimal approximation of the solution in a given low-rank subset, without any a priori information on this solution. We also introduce a weak greedy algorithm which uses this perturbed minimal residual method for the computation of successive greedy corrections in small tensor subsets. We prove its convergence under some conditions on the parameters of the algorithm. The proposed numerical method is applied to the solution of a stochastic partial differential equation which is discretized using standard Galerkin methods in tensor product spaces.
LA - eng
KW - high-dimensional problems; nonlinear approximation; low-rank approximation; proper generalized decomposition; minimal residual; stochastic partial differential equation; numerical examples; algorithm; convergence; Galerkin method; tensor product space
UR - http://eudml.org/doc/273105
ER -

References

top
  1. [1] A. Ammar, B. Mokdad, F. Chinesta and R. Keunings, A new family of solvers for some classes of multidimensional partial differential equations encountered in kinetic theory modelling of complex fluids. J. Non-Newtonian Fluid Mech.139 (2006) 153–176. Zbl1195.76337
  2. [2] A. Ammar, F. Chinesta and A. Falco, On the convergence of a greedy rank-one update algorithm for a class of linear systems. Arch. Comput. Methods Engrg.17 (2010) 473–486. Zbl1269.65120MR2739950
  3. [3] M. Bachmayr and W. Dahmen, Adaptive near-optimal rank tensor approximation for high-dimensional operator equations. Found. Comput. Math. (2014) DOI:10.1007/s10208-013-9187-3. Zbl1335.65049
  4. [4] J. Ballani and L. Grasedyck, A projection method to solve linear systems in tensor format. Numer. Linear Algebra Appl.20 (2013) 27-43. Zbl1289.65049MR3007237
  5. [5] G. Beylkin and M.J. Mohlenkamp, Algorithms for numerical analysis in high dimensions. SIAM J. Sci. Comput.26 (2005) 2133–2159. Zbl1085.65045MR2196592
  6. [6] E. Cances, V. Ehrlacher and T. Lelievre, Convergence of a greedy algorithm for high-dimensional convex nonlinear problems. Math. Models Methods Appl. Sci.21 (2011) 2433–2467. Zbl1259.65098MR2864637
  7. [7] E. Cances, V. Ehrlacher and T. Lelievre, Greedy algorithms for high-dimensional non-symmetric linear problems (2012). Preprint: arXiv:1210.6688v1. Zbl1330.65097MR3174958
  8. [8] A. Cohen, W. Dahmen and G. Welper, Adaptivity and variational stabilization for convection-diffusion equations. ESAIM: M2AN 46 (2012) 1247–1273. Zbl1270.65065MR2916380
  9. [9] F. Chinesta, P. Ladeveze and E. Cueto, A short review on model order reduction based on proper generalized decomposition. Arch. Comput. Methods Engrg.18 (2011) 395–404. 
  10. [10] W. Dahmen, C. Huang, C. Schwab and G. Welper, Adaptive petrov–galerkin methods for first order transport equations. SIAM J. Numer. Anal.50 (2012) 2420–2445. Zbl1260.65091MR3022225
  11. [11] L. De Lathauwer, B. De Moor and J. Vandewalle, A multilinear singular value decomposition. SIAM J. Matrix Anal. Appl.21 (2000) 1253–1278. Zbl0962.15005MR1780272
  12. [12] A. Doostan and G. Iaccarino, A least-squares approximation of partial differential equations with high-dimensional random inputs. J. Comput. Phys.228 (2009) 4332–4345. Zbl1167.65322MR2531901
  13. [13] A. Ern and J.-L. Guermond, Theory and practice of finite elements. Vol. 159 of Appl. Math. Sci. (2004). Zbl1059.65103MR2050138
  14. [14] M. Espig and W. Hackbusch, A regularized newton method for the efficient approximation of tensors represented in the canonical tensor format. Numer. Math.122 (2012) 489–525. Zbl1264.65087MR2983089
  15. [15] A. Falcó and A. Nouy, A Proper Generalized Decomposition for the solution of elliptic problems in abstract form by using a functional Eckart-Young approach. J. Math. Anal. Appl.376 (2011) 469–480. Zbl1210.65009MR2747771
  16. [16] A. Falcó and W. Hackbusch, On minimal subspaces in tensor representations. Found. Comput. Math.12 (2012) 765–803. Zbl1260.15040MR2989473
  17. [17] A. Falcó and A. Nouy, Proper generalized decomposition for nonlinear convex problems in tensor banach spaces. Numer. Math.121 (2012) 503–530. Zbl1264.65095MR2929077
  18. [18] A. Falcó, W. Hackbusch and A. Nouy, Geometric structures in tensor representations. Preprint 9/2013, MPI MIS. 
  19. [19] L. Figueroa and E. Suli, Greedy approximation of high-dimensional Ornstein-Uhlenbeck operators. Found. Comput. Math.12 (2012) 573–623. Zbl1269.76084MR2970851
  20. [20] L. Giraldi, Contributions aux Méthodes de Calcul Basées sur l’Approximation de Tenseurs et Applications en Mécanique Numérique. Ph.D. thesis, École Centrale Nantes (2012). 
  21. [21] L. Giraldi, A. Nouy, G. Legrain and P. Cartraud, Tensor-based methods for numerical homogenization from high-resolution images. Comput. Methods Appl. Mech. Engrg.254 (2013) 154–169. Zbl1297.65138MR3002768
  22. [22] L. Grasedyck, Hierarchical singular value decomposition of tensors. SIAM J. Matrix Anal. Appl.31 (2010) 2029–2054. Zbl1210.65090MR2678955
  23. [23] L. Grasedyck, D. Kressner and C. Tobler, A literature survey of low-rank tensor approximation techniques. GAMM-Mitteilungen36 (2013) 53–78. Zbl1279.65045MR3095914
  24. [24] W. Hackbusch, Tensor Spaces and Numerical Tensor Calculus. In vol. 42 of Springer Series in Computational Mathematics (2012). Zbl1244.65061MR3236394
  25. [25] W. Hackbusch and S. Kuhn, A New Scheme for the Tensor Representation. J. Fourier Anal. Appl.15 (2009) 706–722. Zbl1188.15022MR2563780
  26. [26] S. Holtz, T. Rohwedder and R. Schneider, The Alternating Linear Scheme for Tensor Optimisation in the TT format. SIAM J. Sci. Comput.34 (2012) 683–713. Zbl1252.15031MR2914300
  27. [27] S. Holtz, T. Rohwedder and R. Schneider, On manifolds of tensors with fixed TT rank. Numer. Math.120 (2012) 701–731. Zbl1242.15022MR2892949
  28. [28] B.N. Khoromskij and C. Schwab, Tensor-structured Galerkin approximation of parametric and stochastic elliptic PDEs. SIAM J. Sci. Comput.33 (2011) 364–385. Zbl1243.65009MR2783199
  29. [29] B.N. Khoromskij, Tensors-structured numerical methods in scientific computing: Survey on recent advances. Chemometrics and Intelligent Laboratory Systems110 (2012) 1–19. 
  30. [30] T.G. Kolda and B.W. Bader, Tensor decompositions and applications. SIAM Review51 (2009) 455–500. Zbl1173.65029MR2535056
  31. [31] D. Kressner and C. Tobler, Low-rank tensor krylov subspace methods for parametrized linear systems. SIAM J. Matrix Anal. Appl.32 (2011) 1288–1316. Zbl1237.65034MR2854614
  32. [32] P. Ladevèze, Nonlinear Computational Structural Mechanics - New Approaches and Non-Incremental Methods of Calculation. Springer Verlag (1999). Zbl0912.73003
  33. [33] P. Ladevèze, J.C. Passieux and D. Néron, The LATIN multiscale computational method and the Proper Generalized Decomposition. Comput. Methods Appl. Mech. Engrg.199 (2010) 1287–1296. Zbl1227.74111MR2601397
  34. [34] H. G. Matthies and E. Zander, Solving stochastic systems with low-rank tensor compression. Linear Algebra Appl. 436 (2012). Zbl1241.65016MR2914549
  35. [35] A. Nouy, A generalized spectral decomposition technique to solve a class of linear stochastic partial differential equations, Comput. Methods Appl. Mech. Engrg.196 (2007) 4521-4537. Zbl1173.80311MR2354451
  36. [36] A. Nouy, Recent developments in spectral stochastic methods for the numerical solution of stochastic partial differential equations, Arch. Comput. Methods Engrg.16 (2009) 251–285. MR2533492
  37. [37] A. Nouy, Proper Generalized Decompositions and separated representations for the numerical solution of high dimensional stochastic problems. Arch. Comput. Methods Engrg.17 (2010) 403–434. Zbl1269.76079MR2739946
  38. [38] A. Nouy, A priori model reduction through proper generalized decomposition for solving time-dependent partial differential equations. Comput. Methods Appl. Mech. Engrg.199 (2010) 1603–1626. Zbl1231.76219MR2630166
  39. [39] I.V. Oseledets and E.E. Tyrtyshnikov, Breaking the curse of dimensionality, or how to use SVD in many dimensions. SIAM J. Sci. Comput.31 (2009) 3744–3759. Zbl1200.65028MR2556560
  40. [40] I.V. Oseledets, Tensor-train decomposition. SIAM J. Sci. Comput.33 (2011) 2295–2317. Zbl1232.15018MR2837533
  41. [41] T. Rohwedder and A. Uschmajew, On local convergence of alternating schemes for optimization of convex problems in the tensor train format. SIAM J. Numer. Anal.51 (2013) 1134–1162. Zbl1273.65088MR3038114
  42. [42] V. Temlyakov, Greedy Approximation. Camb. Monogr. Appl. Comput. Math. Cambridge University Press (2011). MR2848161
  43. [43] V. Temlyakov, Greedy approximation. Acta Numerica17 (2008) 235–409. Zbl1178.65050MR2436013
  44. [44] A. Uschmajew and B. Vandereycken, The geometry of algorithms using hierarchical tensors. Technical report, ANCHP-MATHICSE, Mathematics Section, EPFL (2012). Zbl1281.65062MR3045227

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.