Alexandre Pasco

Oleg Balabanov, Anthony Nouy, Alexandre Pasco

We propose a new random sketching approach for embedding high-dimensional Hilbert-Schmidt operators, using random input-output pairs. Such operator can then be approximated in a low-dimensional subspace of operators by solving a small least-squares problem. To achieve computational efficiency, we introduce a structured random map, composed of three random matrices. We provide rigorous conditions under which subspaces of operators are accurately embedded with high probability. The framework is flexible, as the random matrices may be adapted to the operator structure and the computational environment. As an application, we consider the construction of preconditioners for high-dimensional linear equations. We derive a rigorous characterization of preconditioner quality through the discrepancy between the preconditioned operator and an optimal baseline, which can be tailored to a linear approximation space for the solution. We show that this quantity can be efficiently minimized within the proposed framework, especially for parameter separable linear equations. We then establish rigorous high-probability bounds on the quasi-optimality error of the preconditioned Galerkin projection and on the accuracy of a preconditioned residual-based error estimator when the sketch dimensions are sufficiently large. Numerical experiments on an acoustic wave scattering benchmark demonstrate the effectiveness of the method.

Anthony Nouy, Alexandre Pasco

We aim to approximate a continuously differentiable function $u:\mathbb{R}^d \rightarrow \mathbb{R}$ by a composition of functions $f\circ g$ where $g:\mathbb{R}^d \rightarrow \mathbb{R}^m$, $m\leq d$, and $f : \mathbb{R}^m \rightarrow \mathbb{R}$ are built in a two stage procedure. For a fixed $g$, we build $f$ using classical regression methods, involving evaluations of $u$. Recent works proposed to build a nonlinear $g$ by minimizing a loss function $\mathcal{J}(g)$ derived from Poincaré inequalities on manifolds, involving evaluations of the gradient of $u$. A problem is that minimizing $\mathcal{J}$ may be a challenging task. Hence in this work, we introduce new convex surrogates to $\mathcal{J}$. Leveraging concentration inequalities, we provide sub-optimality results for a class of functions $g$, including polynomials, and a wide class of input probability measures. We investigate performances on different benchmarks for various training sample sizes. We show that our approach outperforms standard iterative methods for minimizing the training Poincaré inequality based loss, often resulting in better approximation errors, especially for rather small training sets and $m=1$.