A least-squares method for sparse low rank approximation of multivariate functions. (English) Zbl 1327.65029
Summary: In this paper, we propose a low rank approximation method based on discrete least-squares for the approximation of a multivariate function from random, noise-free observations. Sparsity inducing regularization techniques are used within classical algorithms for low rank approximation in order to exploit the possible sparsity of low rank approximations. Sparse low rank approximations are constructed with a robust updated greedy algorithm, which includes an optimal selection of regularization parameters and approximation ranks using cross validation techniques. Numerical examples demonstrate the capability of approximating functions of many variables even when very few function evaluations are available, thus proving the interest of the proposed algorithm for the propagation of uncertainties through complex computational models.
MSC:
| 65D15 | Algorithms for approximation of functions |
| 62J02 | General nonlinear regression |
| 15A69 | Multilinear algebra, tensor calculus |
Keywords:
uncertainty propagation; high dimension; tensor; low rank approximation; sparsity; least-squaresSoftware:
PDCOReferences:
| [1] | F. Bach, R. Jenatton, J. Mairal, and G. Obozinski, {\it Optimization with sparsity-inducing penalties}, Found. Trends Mach. Learn., 4 (2012), pp. 1-106. · Zbl 06064248 |
| [2] | G. Beylkin, J. Garcke, and M. J. Mohlenkamp, {\it Multivariate regression and machine learning with sums of separable functions}, SIAM J. Sci. Comput., 31 (2009), pp. 1840-1857. · Zbl 1190.62135 |
| [3] | G. Blatman and B. Sudret, {\it Adaptive sparse polynomial chaos expansion based on least angle regression}, J. Comput. Phys., 230 (2011), pp. 2345-2367. · Zbl 1210.65019 |
| [4] | E. J. Candes, J. Romberg, and T. Tao, {\it Near optimal signal recovery from random projections: Universal encoding strategies?}, IEEE Trans. Inform. Theory, 52 (2006), pp. 5406-5425. · Zbl 1309.94033 |
| [5] | G. C. Cawley and N. L. C. Talbot, {\it Fast exact leave-one-out cross-validation of sparse least-squares support vector machines}, Neural Networks, 17 (2004), pp. 1467-1475. · Zbl 1073.68072 |
| [6] | S. S. Chen, D. L. Donoho, and M. A. Saunders, {\it Atomic decomposition by basis pursuit}, SIAM J. Sci. Comput., 20 (1998), pp. 33-61. · Zbl 0919.94002 |
| [7] | D. L. Donoho, {\it Compressed sensing}, IEEE Trans. Inform. Theory, 52 (2006), pp. 1289-1306. · Zbl 1288.94016 |
| [8] | A. Doostan and G. Iaccarino, {\it A least-squares approximation of partial differential equations with high-dimensional random inputs}, J. Comput. Phys., 228 (2009), pp. 4332-4345. · Zbl 1167.65322 |
| [9] | A. Doostan and H. Owhadi, {\it A non-adapted sparse approximation of PDEs with stochastic inputs}, J. Comput. Phys., 230 (2011), pp. 3015-3034. · Zbl 1218.65008 |
| [10] | A. Doostan, A. Validi, and G. Iaccarino, {\it Non-intrusive low-rank separated approximation of high-dimensional stochastic models}, Comput. Methods Appl. Mech. Engrg., 263 (2013), pp. 42-55. · Zbl 1286.65014 |
| [11] | B. Efron, T. Hastie, I. Johnstone, and R. Tibshirani, {\it Least angle regression}, Ann. Statist., 32 (2004), pp. 407-499. · Zbl 1091.62054 |
| [12] | A. Falcó and A. Nouy, {\it Proper generalized decomposition for nonlinear convex problems in tensor Banach spaces}, Numer. Math., 121 (2012), pp. 503-530. · Zbl 1264.65095 |
| [13] | R. Ghanem and P. Spanos, {\it Stochastic Finite Elements: A Spectral Approach}, Springer, Berlin, 1991. · Zbl 0722.73080 |
| [14] | L. Grasedyck, D. Kressner, and C. Tobler, {\it A literature survey of low-rank tensor approximation techniques}, GAMM-Mitt., 36 (2013), pp. 53-78. · Zbl 1279.65045 |
| [15] | W. Hackbusch, {\it Tensor Spaces and Numerical Tensor Calculus}, Comput. Math. 42, Springer, Berlin, 2012. · Zbl 1244.65061 |
| [16] | B. N. Khoromskij, {\it Tensor structured numerical methods in scientific computing: Survey on recent advances}, Chemometrics and Intelligent Laboratory Systems, 110 (2012), pp. 1-19. |
| [17] | B. N. Khoromskij and C. Schwab, {\it Tensor-structured Galerkin approximation of parametric and stochastic elliptic PDEs}, SIAM J. Sci. Comput., 33 (2011), pp. 364-385. · Zbl 1243.65009 |
| [18] | T. G. Kolda and B. W. Bader, {\it Tensor decompositions and applications}, SIAM Rev., 51 (2009), pp. 455-500. · Zbl 1173.65029 |
| [19] | O. P. Le Maître, O. M. Knio, H. N. Najm, and R. G. Ghanem, {\it Uncertainty propagation using Wiener-Haar expansions}, J. Comput. Phys., 197 (2004), pp. 28-57. · Zbl 1052.65114 |
| [20] | O. P. Le Maître and O. M. Knio, {\it Spectral Methods for Uncertainty Quantification with Applications to Computational Fluid Dynamics}, Sci. Comput., Springer, The Netherlands, 2010. · Zbl 1193.76003 |
| [21] | J. Mairal, F. Bach, J. Ponce, and G. Sapiro, {\it Online learning for matrix factorization and sparse coding}, J. Mach. Learn. Res., 11 (2010), pp. 19-60. · Zbl 1242.62087 |
| [22] | H. G. Matthies, {\it Stochastic finite elements: Computational approaches to stochastic partial differential equations}, Zamm Z. Angew. Math. Mech., 88 (2008), pp. 849-873. · Zbl 1158.65009 |
| [23] | H. G. Matthies and E Zander, {\it Solving stochastic systems with low-rank tensor compression}, Linear Algebra Appl., 436 (2012), pp. 3819-3838. · Zbl 1241.65016 |
| [24] | G. Migliorati, F. Nobile, E. von Schwerin, and R. Tempone, {\it Analysis of the discrete \(L^2\) projection on polynomial spaces with random evaluations}, Found. Comput. Math., 14 (2014), pp. 419-456. · Zbl 1301.41005 |
| [25] | A. Nouy, {\it A generalized spectral decomposition technique to solve a class of linear stochastic partial differential equations}, Comput. Methods Appl. Mech. Engrg., 196 (2007), pp. 4521-4537. · Zbl 1173.80311 |
| [26] | A. Nouy, {\it Recent developments in spectral stochastic methods for the numerical solution of stochastic partial differential equations}, Arch. Comput. Methods Engrg., 16 (2009), pp. 251-285. · Zbl 1360.65036 |
| [27] | A. Nouy, {\it Proper generalized decompositions and separated representations for the numerical solution of high dimensional stochastic problems}, Arch. Comput. Methods Engrg., 17 (2010), pp. 403-434. · Zbl 1269.76079 |
| [28] | P. Rai, M. Chevreuil, A. Nouy, and J. Sen Gupta, {\it A regression based non-intrusive method using separated representation for uncertainty quantification}, in Proceedings of ASME 2012, 11th Biennial Conference on Engineering Systems Design and Analysis, Nantes, France, 2012, pp. 167-164. |
| [29] | R. Tibshirani, {\it Regression shrinkage and selection via the lasso}, J. Roy. Statist. Soc. Ser. B, 58 (1996), pp. 267-288. · Zbl 0850.62538 |
| [30] | D. Xiu and G. E. Karniadakis, {\it The Wiener-Askey polynomial chaos for stochastic differential equations}, SIAM J. Sci. Comput., 24 (2002), pp. 619-644. · Zbl 1014.65004 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
