Random sketching of operators with application to learning preconditioners

Alexandre Pasco; Anthony Nouy; Oleg Balabanov

arxiv: 2104.12177 · v2 · submitted 2021-04-25 · 🧮 math.NA · cs.NA

Random sketching of operators with application to learning preconditioners

Oleg Balabanov , Anthony Nouy , Alexandre Pasco This is my paper

Pith reviewed 2026-05-24 13:46 UTC · model grok-4.3

classification 🧮 math.NA cs.NA

keywords random sketchingHilbert-Schmidt operatorsoperator embeddingpreconditionersGalerkin projectionquasi-optimalityresidual error estimatorrandom matrices

0 comments

The pith

Structured random maps embed subspaces of Hilbert-Schmidt operators with high probability, giving bounds on preconditioned Galerkin error.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that high-dimensional Hilbert-Schmidt operators can be embedded into low-dimensional subspaces by solving a small least-squares problem on random input-output pairs. A structured random map built from three random matrices makes the embedding computationally efficient while preserving accuracy with high probability under stated conditions. The same embedding is then used to minimize a discrepancy measure that characterizes preconditioner quality for linear systems, with explicit high-probability bounds on the quasi-optimality constant of the resulting Galerkin projection and on the accuracy of a residual-based error estimator once the sketch size exceeds a threshold. A reader would care because the approach turns an intractable high-dimensional operator problem into a tractable small least-squares task that still delivers rigorous guarantees on the quality of the computed preconditioner.

Core claim

Subspaces of operators are accurately embedded with high probability when the structured random map is used, and this embedding yields 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 whenever the sketch dimensions are sufficiently large.

What carries the argument

The structured random map composed of three random matrices that approximates the action of a high-dimensional Hilbert-Schmidt operator via random input-output pairs and reduces the embedding task to a small least-squares problem.

If this is right

Preconditioner quality can be characterized and minimized through the discrepancy to an optimal baseline tailored to a chosen linear approximation space.
For parameter-separable linear equations the minimization of this discrepancy becomes efficient inside the sketched framework.
The quasi-optimality error of the preconditioned Galerkin projection remains bounded with high probability once sketch dimensions are large enough.
A preconditioned residual-based error estimator remains accurate with high probability for sufficiently large sketches.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same sketching construction could be applied to other projection methods besides Galerkin if the discrepancy functional is redefined accordingly.
The three-matrix structure may allow trading off between different random-matrix distributions to match memory or arithmetic constraints of a given computing environment.
If the operator family is only approximately parameter-separable, the framework still supplies a computable surrogate for the discrepancy that can be minimized.

Load-bearing premise

The structured random map composed of three random matrices can be adapted to the operator structure and computational environment to achieve both embedding accuracy and computational efficiency.

What would settle it

Numerical checks on the acoustic wave scattering benchmark showing that the observed embedding error or quasi-optimality constant exceeds the derived high-probability bound for all sketch dimensions above the paper's threshold.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper introduces a three-matrix structured random map for embedding subspaces of Hilbert-Schmidt operators with high-probability guarantees and uses it to minimize a discrepancy measure for preconditioners, yielding quasi-optimality bounds for Galerkin projections.

read the letter

The main takeaway is that the authors give a flexible sketching method for high-dimensional operators based on random input-output pairs, realized through a structured map of three random matrices. This lets them approximate operators in low-dimensional subspaces via least squares and then apply the same sketch to build preconditioners by minimizing a discrepancy to an optimal baseline. They supply explicit conditions for accurate embedding with high probability and derive bounds on the preconditioned Galerkin error and residual estimator once the sketch dimensions are large enough. The acoustic wave scattering experiments are cited as evidence that the approach works on a concrete benchmark, especially for parameter-separable problems.

Referee Report

0 major / 3 minor

Summary. The paper proposes a random sketching framework for embedding subspaces of high-dimensional Hilbert-Schmidt operators via random input-output pairs and a structured random map composed of three random matrices. It derives rigorous high-probability conditions for accurate embedding, applies the approach to learning preconditioners for linear systems (with emphasis on parameter-separable cases), and establishes high-probability bounds on the quasi-optimality error of the preconditioned Galerkin projection as well as on the accuracy of a preconditioned residual-based error estimator. Numerical experiments on an acoustic wave scattering benchmark are presented to illustrate effectiveness.

Significance. If the embedding conditions and subsequent bounds hold under the stated assumptions on the random matrices and sketch dimensions, the work supplies a theoretically grounded and computationally efficient method for operator approximation and preconditioner construction in high-dimensional settings. The explicit characterization of preconditioner quality via discrepancy to an optimal baseline and the flexibility to adapt the random map to operator structure and environment are particular strengths; the parameter-separable case offers clear efficiency gains.

minor comments (3)

The abstract states that the random matrices 'may be adapted to the operator structure,' but the main text does not provide an explicit general procedure or pseudocode for constructing the three matrices for a new operator class; this would improve reproducibility.
In the numerical experiments section, the discretization parameters (mesh size, number of degrees of freedom) for the acoustic scattering benchmark are referenced only qualitatively; adding a short table with these values and the chosen sketch dimensions would strengthen the presentation.
Notation for the structured random map (the three constituent matrices) is introduced without a dedicated display equation summarizing their joint action; a single displayed equation would clarify the subsequent probability statements.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading, positive summary, and recommendation of minor revision. The assessment of the paper's contributions to random sketching of Hilbert-Schmidt operators and preconditioner construction is appreciated.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The derivation chain begins from standard properties of Hilbert-Schmidt operators and random matrix concentration inequalities to establish high-probability embedding conditions for operator subspaces via the structured random map (three random matrices). These embeddings are then used to derive independent quasi-optimality bounds on the preconditioned Galerkin projection and residual-based error estimator, with the preconditioner quality measure defined externally as the discrepancy to an optimal baseline before being minimized inside the sketch. No step reduces by construction to a self-definition, a fitted input renamed as prediction, or a load-bearing self-citation chain; all central claims remain self-contained under the stated assumptions on sketch dimensions and random matrix properties.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard functional-analysis properties of Hilbert-Schmidt operators and random-matrix concentration; no free parameters or new entities are introduced in the abstract.

axioms (1)

domain assumption Hilbert-Schmidt operators admit accurate low-dimensional embeddings via random input-output pairs under suitable conditions
This is the foundational premise of the sketching framework stated in the abstract.

pith-pipeline@v0.9.0 · 5732 in / 1286 out tokens · 25746 ms · 2026-05-24T13:46:39.080698+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages

[1]

Robust model reductio n by L1-norm minimization and approximation via dictionaries: application to nonlinear hyperbolic pro blems

R. Abgrall, D. Amsallem, and R. Crisovan. “Robust model reductio n by L1-norm minimization and approximation via dictionaries: application to nonlinear hyperbolic pro blems”. Advanced Modeling and Simulation in Engineering Sciences 3.1 (2016), pp. 1–16 (cit. on p. 2)

work page 2016
[2]

Randomized model order reduction

A. Alla and J. N. Kutz. “Randomized model order reduction”. Advances in Computational Math- ematics 45.3 (2019), pp. 1251–1271 (cit. on p. 3)

work page 2019
[3]

Randomized linear algebra for model r eduction. Part I: Galerkin methods and error estimation

O. Balabanov and A. Nouy. “Randomized linear algebra for model r eduction. Part I: Galerkin methods and error estimation”. Advances in Computational Mathematics 45.5-6 (2019), pp. 2969– 3019 (cit. on pp. 2, 3, 4, 5, 6, 8, 12, 13, 14, 15, 17, 18, 22, 23, 24, 31, 32)

work page 2019
[4]

Randomized linear algebra for model r eduction. Part II: minimal residual methods and dictionary-based approximation

O. Balabanov and A. Nouy. “Randomized linear algebra for model r eduction. Part II: minimal residual methods and dictionary-based approximation”. Advances in Computational Mathematics 47.26 (2021) (cit. on pp. 3, 24)

work page 2021
[5]

Benner, A

P. Benner, A. Cohen, M. Ohlberger, and K. Willcox, eds. Model Reduction and Approximation: Theory and Algorithms . SIAM, Philadelphia, PA, 2017 (cit. on p. 2)

work page 2017
[6]

A survey of projection- based model reduction methods for parametric dynamical systems

P. Benner, S. Gugercin, and K. Willcox. “A survey of projection- based model reduction methods for parametric dynamical systems”. SIAM review 57.4 (2015), pp. 483–531 (cit. on p. 2)

work page 2015
[7]

Improved matrix algorithms via the s ubsampled randomized Hadamard transform

C. Boutsidis and A. Gittens. “Improved matrix algorithms via the s ubsampled randomized Hadamard transform”. SIAM Journal on Matrix Analysis and Applications 34.3 (2013), pp. 1301–1340 (cit. on p. 23)

work page 2013
[8]

Randomized local model order reduct ion

A. Buhr and K. Smetana. “Randomized local model order reduct ion”. SIAM journal on scientiﬁc computing 40.4 (2018), A2120–A2151 (cit. on p. 3)

work page 2018
[9]

A posteriori error estimation and global error control for ordinary dif- ferential equations by the adjoint method

Y. Cao and L. Petzold. “A posteriori error estimation and global error control for ordinary dif- ferential equations by the adjoint method”. SIAM Journal on Scientiﬁc Computing 26.2 (2004), pp. 359–374 (cit. on pp. 2, 3)

work page 2004
[10]

Accurate and online- eﬃcient evaluation of the a posteri- ori error bound in the reduced basis method

F. Casenave, A. Ern, and T. Leli` evre. “Accurate and online- eﬃcient evaluation of the a posteri- ori error bound in the reduced basis method”. ESAIM: Mathematical Modelling and Numerical Analysis 48.1 (2014), pp. 207–229 (cit. on p. 2)

work page 2014
[11]

Parametric analytical pre conditioning and its applications to the reduced collocation methods

Y. Chen, S. Gottlieb, and Y. Maday. “Parametric analytical pre conditioning and its applications to the reduced collocation methods”. Comptes Rendus Mathematique 352.7-8 (2014), pp. 661–666 (cit. on p. 2)

work page 2014
[12]

Imp roved successive constraint method based a posteriori error estimate for reduced basis approximatio n of 2D Maxwell’s problem

Y. Chen, J. S. Hesthaven, Y. Maday, and J. Rodr ´ ıguez. “Imp roved successive constraint method based a posteriori error estimate for reduced basis approximatio n of 2D Maxwell’s problem”. ESAIM: Mathematical Modelling and Numerical Analysis 43.6 (2009), pp. 1099–1116 (cit. on p. 11)

work page 2009
[13]

Polynomial chaos repr esentation of a stochastic precon- ditioner

C. Desceliers, R. Ghanem, and C. Soize. “Polynomial chaos repr esentation of a stochastic precon- ditioner”. International journal for numerical methods in engineerin g 64.5 (2005), pp. 618–634 (cit. on p. 2). 25

work page 2005
[14]

The ROMES method for statistic al modeling of reduced-order- model error

M. Drohmann and K. Carlberg. “The ROMES method for statistic al modeling of reduced-order- model error”. SIAM/ASA Journal on Uncertainty Quantiﬁcation 3.1 (2015), pp. 116–145 (cit. on p. 3)

work page 2015
[15]

A hierarchical a posteriori error estimator for the Reduced Basis Method

S. Hain, M. Ohlberger, M. Radic, and K. Urban. “A hierarchical a posteriori error estimator for the Reduced Basis Method”. Advances in Computational Mathematics (2019), pp. 1–24 (cit. on pp. 2, 5)

work page 2019
[16]

Finding structur e with randomness: Probabilis- tic algorithms for constructing approximate matrix decompositions

N. Halko, P.-G. Martinsson, and J. A. Tropp. “Finding structur e with randomness: Probabilis- tic algorithms for constructing approximate matrix decompositions ”. SIAM review 53.2 (2011), pp. 217–288 (cit. on pp. 3, 23)

work page 2011
[17]

J. S. Hesthaven, G. Rozza, and B. Stamm. Certiﬁed Reduced Basis Methods for Parametrized Partial Diﬀerential Equations. Springer Briefs in Mathematics. Switzerland: Springer, 2015, p. 1 35. isbn: 978-3-319-22469-5 (cit. on p. 2)

work page 2015
[18]

Error estimation f or reduced-order models of dynam- ical systems

C. Homescu, L. R. Petzold, and R. Serban. “Error estimation f or reduced-order models of dynam- ical systems”. SIAM Journal on Numerical Analysis 43.4 (2005), pp. 1693–1714 (cit. on p. 3)

work page 2005
[19]

A natural-norm successive constraint method for inf-sup lower bounds

D. Huynh, D. Knezevic, Y Chen, J. S. Hesthaven, and A. Pater a. “A natural-norm successive constraint method for inf-sup lower bounds”. Computer Methods in Applied Mechanics and Engi- neering 199.29-32 (2010), pp. 1963–1975 (cit. on p. 11)

work page 2010
[20]

A succes sive constraint linear optimiza- tion method for lower bounds of parametric coercivity and inf–sup s tability constants

D. B. P. Huynh, G. Rozza, S. Sen, and A. T. Patera. “A succes sive constraint linear optimiza- tion method for lower bounds of parametric coercivity and inf–sup s tability constants”. Comptes Rendus Mathematique 345.8 (2007), pp. 473–478 (cit. on p. 11)

work page 2007
[21]

A preconditioned lo w-rank CG method for parameter- dependent Lyapunov matrix equations

D. Kressner, M. Pleˇ singer, and C. Tobler. “A preconditioned lo w-rank CG method for parameter- dependent Lyapunov matrix equations”. Numerical Linear Algebra with Applications 21.5 (2014), pp. 666–684 (cit. on p. 2)

work page 2014
[22]

Recycling Krylov subspaces for sequences of linear systems

M. L. Parks, E. De Sturler, G. Mackey, D. D. Johnson, and S. M aiti. “Recycling Krylov subspaces for sequences of linear systems”. SIAM Journal on Scientiﬁc Computing 28.5 (2006), pp. 1651– 1674 (cit. on p. 2)

work page 2006
[23]

Quarteroni, A

A. Quarteroni, A. Manzoni, and F. Negri. Reduced basis methods for partial diﬀerential equations: an introduction. Vol. 92. Springer, 2015 (cit. on p. 2)

work page 2015
[24]

Multi space reduced basis precondi- tioners for large-scale parametrized PDEs

N. D. Santo, S. Deparis, A. Manzoni, and A. Quarteroni. “Multi space reduced basis precondi- tioners for large-scale parametrized PDEs”. SIAM Journal on Scientiﬁc Computing 40.2 (2018), A954–A983 (cit. on p. 2)

work page 2018
[25]

Randomized residual-based error es timators for the proper generalized decomposition approximation of parametrized problems

K. Smetana and O. Zahm. “Randomized residual-based error es timators for the proper generalized decomposition approximation of parametrized problems”. International Journal for Numerical Methods in Engineering 121.23 (2020), pp. 5153–5177 (cit. on p. 3)

work page 2020
[26]

Randomized residual- based error estimators for parametrized equations

K. Smetana, O. Zahm, and A. T. Patera. “Randomized residual- based error estimators for parametrized equations”. SIAM journal on scientiﬁc computing 41.2 (2019), A900–A926 (cit. on pp. 3, 4, 5). 26

work page 2019
[27]

An oﬄine/online procedure for dual norm calculation s of parameterized functionals: empirical quadrature and empirical test spaces

T. Taddei. “An oﬄine/online procedure for dual norm calculation s of parameterized functionals: empirical quadrature and empirical test spaces”. Advances in Computational Mathematics 45.5-6 (2019), pp. 2429–2462 (cit. on p. 2)

work page 2019
[28]

Stabilized weighted reduced basis methods for parametrized advection dominated problems with random inputs

D. Torlo, F. Ballarin, and G. Rozza. “Stabilized weighted reduced basis methods for parametrized advection dominated problems with random inputs”. SIAM/ASA Journal on Uncertainty Quan- tiﬁcation 6.4 (2018), pp. 1475–1502 (cit. on p. 2)

work page 2018
[29]

Error modelin g for surrogates of dynamical systems using machine learning

S. Trehan, K. T. Carlberg, and L. J. Durlofsky. “Error modelin g for surrogates of dynamical systems using machine learning”. International Journal for Numerical Methods in Engineerin g 112.12 (2017), pp. 1801–1827 (cit. on p. 3)

work page 2017
[30]

Signal recovery from random me asurements via orthogonal match- ing pursuit

J. A. Tropp and A. C. Gilbert. “Signal recovery from random me asurements via orthogonal match- ing pursuit”. IEEE Transactions on information theory 53.12 (2007), pp. 4655–4666 (cit. on p. 3)

work page 2007
[31]

Interpolation of inverse operators for preconditioning parameter-dependent equations

O. Zahm and A. Nouy. “Interpolation of inverse operators for preconditioning parameter-dependent equations”. SIAM Journal on Scientiﬁc Computing 38.2 (2016), A1044–A1074 (cit. on pp. 2, 3, 4). 7 Appendix This section provides the proofs of propositions from the article. Proof of Proposition 3.1. We have, ∥Cv∥U ′ = ∥(R− 1/ 2 U CR− 1/ 2 U )(R1/ 2 U v)∥2 ≤ ∥...

work page 2016
[32]

holds with probability at least 1 − δ for V = Ur + U ∗ m. This implies that ∥u − w∥Θ U ≤ ∥ ΠUr+U ∗mu − w∥Θ U + ∥u − ΠUr+U ∗mu∥Θ U ≤ √ 1 + ε∥ΠUr+U ∗mu − w∥U + ∥u − ΠUr+U ∗mu∥Θ U ≤ √ 1 + ε (∥u − w∥U + dm(M)) + ∥u − ΠUr+U ∗mu∥Θ U , (61) and (similarly) ∥u − w∥Θ U ≥ √ 1 − ε (∥u − w∥U − dm(M)) − ∥ u − ΠUr+U ∗mu∥Θ U , (62) hold simultaneously for all u ∈ M and ...

work page
[33]

Propositions 5.2 to 5.4 will follow from the following proposition

to ( 70). Propositions 5.2 to 5.4 will follow from the following proposition. Proposition 7.1. The random map Υ(·) deﬁned by Υ(X) := Γ vec(ΩXΣH), X ∈ Kq× p, where Γ, Ω and Σ are (εΓ, δ Γ, d ), (εΩ, δ Ω, d ) and (εΣ, δ Σ, d ) oblivious ℓ2 → ℓ2 subspace embeddings, is a (ε, δ, d ) oblivious HS (ℓ2, ℓ 2) → ℓ2 subspace embedding of matrices with ε = (1 + εΓ)(...

work page
[34]

(72) Furthermore, by taking V := {XHΩH : X ∈ V } and replacing Ω by Σ in ( 72), we also deduce that P(∀V ∈ V, |∥VHΩH∥2 F − ∥ ΣVHΩH∥2 F | ≤ εΣ∥VHΩH∥2 F ) ≥ 1 − kΩδΣ

and the following identities ∥V∥2 F = p∑ i=1 ∥Vei∥2 2 and ∥ΩV∥2 F = p∑ i=1 ∥Ω[Vei]∥2 2, we deduce that P(∀V ∈ V, |∥V∥2 F − ∥ ΩV∥2 F | ≤ εΩ∥V∥2 F ) ≥ 1 − qδΩ. (72) Furthermore, by taking V := {XHΩH : X ∈ V } and replacing Ω by Σ in ( 72), we also deduce that P(∀V ∈ V, |∥VHΩH∥2 F − ∥ ΣVHΩH∥2 F | ≤ εΣ∥VHΩH∥2 F ) ≥ 1 − kΩδΣ. (73) Finally, by deﬁnition of Γ an...

work page
[35]

to ( 74) and using a union bound, we obtain that |∥V∥2 F − ∥ Γvec(ΩVΣH)∥2 2| ≤ |∥V∥2 F − ∥ ΩVΣH∥2 F |+ |∥ΩVΣH∥2 F − ∥ Γvec(ΩVΣH)∥2 2| ≤ |∥ V∥2 F − ∥ ΩVΣH∥2 F |+ εΓ∥ΩVΣH∥F ≤ (1 + εΓ)|∥V∥2 F − ∥ ΩVΣH∥2 F |+ εΓ∥V∥2 F ≤ (1 + εΓ) ( |∥V∥2 F − ∥ ΩV∥2 F |+ |∥ΩV∥2 F − ∥ ΩVΣH∥2 F | ) + εΓ∥V∥2 F ≤ (1 + εΓ) ( |∥V∥2 F − ∥ ΩV∥2 F |+ εΣ∥ΩV∥2 F | ) + εΓ∥V∥2 F ≤ (1 + εΓ)(...

work page

[1] [1]

Robust model reductio n by L1-norm minimization and approximation via dictionaries: application to nonlinear hyperbolic pro blems

R. Abgrall, D. Amsallem, and R. Crisovan. “Robust model reductio n by L1-norm minimization and approximation via dictionaries: application to nonlinear hyperbolic pro blems”. Advanced Modeling and Simulation in Engineering Sciences 3.1 (2016), pp. 1–16 (cit. on p. 2)

work page 2016

[2] [2]

Randomized model order reduction

A. Alla and J. N. Kutz. “Randomized model order reduction”. Advances in Computational Math- ematics 45.3 (2019), pp. 1251–1271 (cit. on p. 3)

work page 2019

[3] [3]

Randomized linear algebra for model r eduction. Part I: Galerkin methods and error estimation

O. Balabanov and A. Nouy. “Randomized linear algebra for model r eduction. Part I: Galerkin methods and error estimation”. Advances in Computational Mathematics 45.5-6 (2019), pp. 2969– 3019 (cit. on pp. 2, 3, 4, 5, 6, 8, 12, 13, 14, 15, 17, 18, 22, 23, 24, 31, 32)

work page 2019

[4] [4]

Randomized linear algebra for model r eduction. Part II: minimal residual methods and dictionary-based approximation

O. Balabanov and A. Nouy. “Randomized linear algebra for model r eduction. Part II: minimal residual methods and dictionary-based approximation”. Advances in Computational Mathematics 47.26 (2021) (cit. on pp. 3, 24)

work page 2021

[5] [5]

Benner, A

P. Benner, A. Cohen, M. Ohlberger, and K. Willcox, eds. Model Reduction and Approximation: Theory and Algorithms . SIAM, Philadelphia, PA, 2017 (cit. on p. 2)

work page 2017

[6] [6]

A survey of projection- based model reduction methods for parametric dynamical systems

P. Benner, S. Gugercin, and K. Willcox. “A survey of projection- based model reduction methods for parametric dynamical systems”. SIAM review 57.4 (2015), pp. 483–531 (cit. on p. 2)

work page 2015

[7] [7]

Improved matrix algorithms via the s ubsampled randomized Hadamard transform

C. Boutsidis and A. Gittens. “Improved matrix algorithms via the s ubsampled randomized Hadamard transform”. SIAM Journal on Matrix Analysis and Applications 34.3 (2013), pp. 1301–1340 (cit. on p. 23)

work page 2013

[8] [8]

Randomized local model order reduct ion

A. Buhr and K. Smetana. “Randomized local model order reduct ion”. SIAM journal on scientiﬁc computing 40.4 (2018), A2120–A2151 (cit. on p. 3)

work page 2018

[9] [9]

A posteriori error estimation and global error control for ordinary dif- ferential equations by the adjoint method

Y. Cao and L. Petzold. “A posteriori error estimation and global error control for ordinary dif- ferential equations by the adjoint method”. SIAM Journal on Scientiﬁc Computing 26.2 (2004), pp. 359–374 (cit. on pp. 2, 3)

work page 2004

[10] [10]

Accurate and online- eﬃcient evaluation of the a posteri- ori error bound in the reduced basis method

F. Casenave, A. Ern, and T. Leli` evre. “Accurate and online- eﬃcient evaluation of the a posteri- ori error bound in the reduced basis method”. ESAIM: Mathematical Modelling and Numerical Analysis 48.1 (2014), pp. 207–229 (cit. on p. 2)

work page 2014

[11] [11]

Parametric analytical pre conditioning and its applications to the reduced collocation methods

Y. Chen, S. Gottlieb, and Y. Maday. “Parametric analytical pre conditioning and its applications to the reduced collocation methods”. Comptes Rendus Mathematique 352.7-8 (2014), pp. 661–666 (cit. on p. 2)

work page 2014

[12] [12]

Imp roved successive constraint method based a posteriori error estimate for reduced basis approximatio n of 2D Maxwell’s problem

Y. Chen, J. S. Hesthaven, Y. Maday, and J. Rodr ´ ıguez. “Imp roved successive constraint method based a posteriori error estimate for reduced basis approximatio n of 2D Maxwell’s problem”. ESAIM: Mathematical Modelling and Numerical Analysis 43.6 (2009), pp. 1099–1116 (cit. on p. 11)

work page 2009

[13] [13]

Polynomial chaos repr esentation of a stochastic precon- ditioner

C. Desceliers, R. Ghanem, and C. Soize. “Polynomial chaos repr esentation of a stochastic precon- ditioner”. International journal for numerical methods in engineerin g 64.5 (2005), pp. 618–634 (cit. on p. 2). 25

work page 2005

[14] [14]

The ROMES method for statistic al modeling of reduced-order- model error

M. Drohmann and K. Carlberg. “The ROMES method for statistic al modeling of reduced-order- model error”. SIAM/ASA Journal on Uncertainty Quantiﬁcation 3.1 (2015), pp. 116–145 (cit. on p. 3)

work page 2015

[15] [15]

A hierarchical a posteriori error estimator for the Reduced Basis Method

S. Hain, M. Ohlberger, M. Radic, and K. Urban. “A hierarchical a posteriori error estimator for the Reduced Basis Method”. Advances in Computational Mathematics (2019), pp. 1–24 (cit. on pp. 2, 5)

work page 2019

[16] [16]

Finding structur e with randomness: Probabilis- tic algorithms for constructing approximate matrix decompositions

N. Halko, P.-G. Martinsson, and J. A. Tropp. “Finding structur e with randomness: Probabilis- tic algorithms for constructing approximate matrix decompositions ”. SIAM review 53.2 (2011), pp. 217–288 (cit. on pp. 3, 23)

work page 2011

[17] [17]

J. S. Hesthaven, G. Rozza, and B. Stamm. Certiﬁed Reduced Basis Methods for Parametrized Partial Diﬀerential Equations. Springer Briefs in Mathematics. Switzerland: Springer, 2015, p. 1 35. isbn: 978-3-319-22469-5 (cit. on p. 2)

work page 2015

[18] [18]

Error estimation f or reduced-order models of dynam- ical systems

C. Homescu, L. R. Petzold, and R. Serban. “Error estimation f or reduced-order models of dynam- ical systems”. SIAM Journal on Numerical Analysis 43.4 (2005), pp. 1693–1714 (cit. on p. 3)

work page 2005

[19] [19]

A natural-norm successive constraint method for inf-sup lower bounds

D. Huynh, D. Knezevic, Y Chen, J. S. Hesthaven, and A. Pater a. “A natural-norm successive constraint method for inf-sup lower bounds”. Computer Methods in Applied Mechanics and Engi- neering 199.29-32 (2010), pp. 1963–1975 (cit. on p. 11)

work page 2010

[20] [20]

A succes sive constraint linear optimiza- tion method for lower bounds of parametric coercivity and inf–sup s tability constants

D. B. P. Huynh, G. Rozza, S. Sen, and A. T. Patera. “A succes sive constraint linear optimiza- tion method for lower bounds of parametric coercivity and inf–sup s tability constants”. Comptes Rendus Mathematique 345.8 (2007), pp. 473–478 (cit. on p. 11)

work page 2007

[21] [21]

A preconditioned lo w-rank CG method for parameter- dependent Lyapunov matrix equations

D. Kressner, M. Pleˇ singer, and C. Tobler. “A preconditioned lo w-rank CG method for parameter- dependent Lyapunov matrix equations”. Numerical Linear Algebra with Applications 21.5 (2014), pp. 666–684 (cit. on p. 2)

work page 2014

[22] [22]

Recycling Krylov subspaces for sequences of linear systems

M. L. Parks, E. De Sturler, G. Mackey, D. D. Johnson, and S. M aiti. “Recycling Krylov subspaces for sequences of linear systems”. SIAM Journal on Scientiﬁc Computing 28.5 (2006), pp. 1651– 1674 (cit. on p. 2)

work page 2006

[23] [23]

Quarteroni, A

A. Quarteroni, A. Manzoni, and F. Negri. Reduced basis methods for partial diﬀerential equations: an introduction. Vol. 92. Springer, 2015 (cit. on p. 2)

work page 2015

[24] [24]

Multi space reduced basis precondi- tioners for large-scale parametrized PDEs

N. D. Santo, S. Deparis, A. Manzoni, and A. Quarteroni. “Multi space reduced basis precondi- tioners for large-scale parametrized PDEs”. SIAM Journal on Scientiﬁc Computing 40.2 (2018), A954–A983 (cit. on p. 2)

work page 2018

[25] [25]

Randomized residual-based error es timators for the proper generalized decomposition approximation of parametrized problems

K. Smetana and O. Zahm. “Randomized residual-based error es timators for the proper generalized decomposition approximation of parametrized problems”. International Journal for Numerical Methods in Engineering 121.23 (2020), pp. 5153–5177 (cit. on p. 3)

work page 2020

[26] [26]

Randomized residual- based error estimators for parametrized equations

K. Smetana, O. Zahm, and A. T. Patera. “Randomized residual- based error estimators for parametrized equations”. SIAM journal on scientiﬁc computing 41.2 (2019), A900–A926 (cit. on pp. 3, 4, 5). 26

work page 2019

[27] [27]

An oﬄine/online procedure for dual norm calculation s of parameterized functionals: empirical quadrature and empirical test spaces

T. Taddei. “An oﬄine/online procedure for dual norm calculation s of parameterized functionals: empirical quadrature and empirical test spaces”. Advances in Computational Mathematics 45.5-6 (2019), pp. 2429–2462 (cit. on p. 2)

work page 2019

[28] [28]

Stabilized weighted reduced basis methods for parametrized advection dominated problems with random inputs

D. Torlo, F. Ballarin, and G. Rozza. “Stabilized weighted reduced basis methods for parametrized advection dominated problems with random inputs”. SIAM/ASA Journal on Uncertainty Quan- tiﬁcation 6.4 (2018), pp. 1475–1502 (cit. on p. 2)

work page 2018

[29] [29]

Error modelin g for surrogates of dynamical systems using machine learning

S. Trehan, K. T. Carlberg, and L. J. Durlofsky. “Error modelin g for surrogates of dynamical systems using machine learning”. International Journal for Numerical Methods in Engineerin g 112.12 (2017), pp. 1801–1827 (cit. on p. 3)

work page 2017

[30] [30]

Signal recovery from random me asurements via orthogonal match- ing pursuit

J. A. Tropp and A. C. Gilbert. “Signal recovery from random me asurements via orthogonal match- ing pursuit”. IEEE Transactions on information theory 53.12 (2007), pp. 4655–4666 (cit. on p. 3)

work page 2007

[31] [31]

Interpolation of inverse operators for preconditioning parameter-dependent equations

O. Zahm and A. Nouy. “Interpolation of inverse operators for preconditioning parameter-dependent equations”. SIAM Journal on Scientiﬁc Computing 38.2 (2016), A1044–A1074 (cit. on pp. 2, 3, 4). 7 Appendix This section provides the proofs of propositions from the article. Proof of Proposition 3.1. We have, ∥Cv∥U ′ = ∥(R− 1/ 2 U CR− 1/ 2 U )(R1/ 2 U v)∥2 ≤ ∥...

work page 2016

[32] [32]

holds with probability at least 1 − δ for V = Ur + U ∗ m. This implies that ∥u − w∥Θ U ≤ ∥ ΠUr+U ∗mu − w∥Θ U + ∥u − ΠUr+U ∗mu∥Θ U ≤ √ 1 + ε∥ΠUr+U ∗mu − w∥U + ∥u − ΠUr+U ∗mu∥Θ U ≤ √ 1 + ε (∥u − w∥U + dm(M)) + ∥u − ΠUr+U ∗mu∥Θ U , (61) and (similarly) ∥u − w∥Θ U ≥ √ 1 − ε (∥u − w∥U − dm(M)) − ∥ u − ΠUr+U ∗mu∥Θ U , (62) hold simultaneously for all u ∈ M and ...

work page

[33] [33]

Propositions 5.2 to 5.4 will follow from the following proposition

to ( 70). Propositions 5.2 to 5.4 will follow from the following proposition. Proposition 7.1. The random map Υ(·) deﬁned by Υ(X) := Γ vec(ΩXΣH), X ∈ Kq× p, where Γ, Ω and Σ are (εΓ, δ Γ, d ), (εΩ, δ Ω, d ) and (εΣ, δ Σ, d ) oblivious ℓ2 → ℓ2 subspace embeddings, is a (ε, δ, d ) oblivious HS (ℓ2, ℓ 2) → ℓ2 subspace embedding of matrices with ε = (1 + εΓ)(...

work page

[34] [34]

(72) Furthermore, by taking V := {XHΩH : X ∈ V } and replacing Ω by Σ in ( 72), we also deduce that P(∀V ∈ V, |∥VHΩH∥2 F − ∥ ΣVHΩH∥2 F | ≤ εΣ∥VHΩH∥2 F ) ≥ 1 − kΩδΣ

and the following identities ∥V∥2 F = p∑ i=1 ∥Vei∥2 2 and ∥ΩV∥2 F = p∑ i=1 ∥Ω[Vei]∥2 2, we deduce that P(∀V ∈ V, |∥V∥2 F − ∥ ΩV∥2 F | ≤ εΩ∥V∥2 F ) ≥ 1 − qδΩ. (72) Furthermore, by taking V := {XHΩH : X ∈ V } and replacing Ω by Σ in ( 72), we also deduce that P(∀V ∈ V, |∥VHΩH∥2 F − ∥ ΣVHΩH∥2 F | ≤ εΣ∥VHΩH∥2 F ) ≥ 1 − kΩδΣ. (73) Finally, by deﬁnition of Γ an...

work page

[35] [35]

to ( 74) and using a union bound, we obtain that |∥V∥2 F − ∥ Γvec(ΩVΣH)∥2 2| ≤ |∥V∥2 F − ∥ ΩVΣH∥2 F |+ |∥ΩVΣH∥2 F − ∥ Γvec(ΩVΣH)∥2 2| ≤ |∥ V∥2 F − ∥ ΩVΣH∥2 F |+ εΓ∥ΩVΣH∥F ≤ (1 + εΓ)|∥V∥2 F − ∥ ΩVΣH∥2 F |+ εΓ∥V∥2 F ≤ (1 + εΓ) ( |∥V∥2 F − ∥ ΩV∥2 F |+ |∥ΩV∥2 F − ∥ ΩVΣH∥2 F | ) + εΓ∥V∥2 F ≤ (1 + εΓ) ( |∥V∥2 F − ∥ ΩV∥2 F |+ εΣ∥ΩV∥2 F | ) + εΓ∥V∥2 F ≤ (1 + εΓ)(...

work page