Certified a priori error control for the Discrete Empirical Interpolation Method: closing the amplification-constant gap and guaranteeing adaptive tolerances

The discrete empirical interpolation method (DEIM) makes projection-based model reduction of nonlinear PDEs computationally feasible by evaluating nonlinear terms at only $m \ll n$ selected components, with the certified error bound $\|f-\hat f\|_2 \le \mathcal{C}\|(I-UU^T)f\|_2$ where $\mathcal{C}=\|(P^TU)^{-1}\|_2$. The founding 2010 paper of Chaturantabut and Sorensen proved only $\mathcal{C} \le (1+\sqrt{2n})^{m-1}\|u_1\|_\infty^{-1}$, an astronomically pessimistic estimate, and left a priori error control open. Later work largely settled the original agenda: Q-DEIM (pivoted QR selection) proved $\mathcal{C} \le \sqrt{n-m+1}\,\sqrt{4^m+6m-1}/3$, maximum-volume selections are known to exist with $\mathcal{C} \le \sqrt{1+m(n-m)}$, randomized and adaptive selection theory grew up around it, and state-space plus a posteriori error estimates quantified error propagation. This problem states the surviving open core as two separate open targets. Part A: close the amplification-constant gap - the conjectured optimal $\sqrt n$ bound for maximum-volume selection (with a matching universal $\sqrt n$ lower bound) is unproven, no polynomial-time selection is known to achieve $O(\sqrt n)$, a sharp worst-case bound for the practically used DEIM greedy rule remains open, and the constant factors for Q-DEIM are not characterized (refinements appeared as recently as 2025). Part B: construct adaptive snapshot-generation and stopping procedures with a proven guarantee that user-specified tolerances are met uniformly over the parameter or time domain, replacing the heuristic $\sigma_{m+1}$ stopping rule.

Background

Large-scale simulation of nonlinear partial differential equations is routinely accelerated by projection-based model order reduction: the state is approximated in a low-dimensional subspace and the governing equations are projected onto it. The dominant subspace construction is proper orthogonal decomposition (POD), in which a truncated singular value decomposition (SVD) of sampled solution trajectories ('snapshots') supplies an orthonormal basis $V_k$ containing the dominant solution energy. POD-Galerkin reduction shrinks the number of unknowns, but for a general non-affine, non-polynomial nonlinearity $F$ the projected term $V_k^T F(V_k\tilde y)$ still requires evaluating $F$ at all $n$ spatial degrees of freedom, so the per-step cost remains tied to the full dimension $n$.

The discrete empirical interpolation method (DEIM) of Chaturantabut and Sorensen removes this bottleneck, a task known as hyperreduction. From snapshots of the nonlinear term one builds a second POD basis $U=[u_1,\dots,u_m]\in\mathbb{R}^{n\times m}$ with $m \ll n$; DEIM approximates $F$ by the interpolatory projection $\hat f = U(P^TU)^{-1}P^T f$, where the selection matrix $P$ picks $m$ component indices produced by a greedy rule (each new index is the largest-magnitude entry of the residual of the next basis vector against the current interpolant). Only the $m$ selected components of $F$ must be evaluated, so the online cost becomes independent of $n$. DEIM is the discrete counterpart of the empirical interpolation method (EIM) of Barrault, Maday, Nguyen and Patera in the reduced-basis context.

The accuracy certificate of DEIM is $\|f-\hat f\|_2 \le \mathcal{C}\|(I-UU^T)f\|_2$ with $\mathcal{C}=\|(P^TU)^{-1}\|_2$: the interpolant is at most a factor $\mathcal{C}$ worse than the optimal orthogonal projection onto the span of $U$, a Lebesgue-constant-type amplification. The 2010 paper proved only $\mathcal{C} \le (1+\sqrt{2n})^{m-1}\|u_1\|_\infty^{-1} \le \sqrt{n}(1+\sqrt{2n})^{m-1}$, a Wilkinson-style growth-factor bound (an estimate in the spirit of the classical pivot-growth bounds for Gaussian elimination) that is far too pessimistic to be predictive, and it left a priori error control open: sharper bounds on $\mathcal{C}$, index selections with provably small $\mathcal{C}$, tolerance-guaranteed snapshot and stopping rules, quantified propagation of DEIM errors to the computed solution, and cheaper index selection.

Subsequent work transformed this landscape. Q-DEIM (Drmač and Gugercin, 2016) replaces the greedy DEIM rule by a pivoted QR factorization of $U^T$: the selection costs $O(nm^2)$ using BLAS-3 kernels (dense matrix-matrix operations that run at high efficiency on modern hardware), is invariant under changes of orthonormal basis, and satisfies the a priori bound $\mathcal{C} \le \sqrt{n-m+1}\,\sqrt{4^m+6m-1}/3$, where the exponential-in-$m$ factor is attained only on contrived Kahan-type matrices (a classical upper-triangular family with tiny diagonal entries that forces worst-case pivot growth in QR-type factorizations) and behaves like $O(m)$ in practice. Strong rank-revealing QR refinements (QR factorizations with column pivoting strengthened by provable bounds on the conditioning of the selected submatrix) and a weighted-inner-product extension $W$-DEIM, the variant relevant to finite-element mass and energy inner products, followed (Drmač and Saibaba, 2018), as did randomized DEIM (Saibaba, 2020), probabilistic stability analysis of oversampled 'gappy' empirical interpolation, which reads the nonlinear term at more components than the basis size (Peherstorfer, Drmač and Gugercin, 2020), and adaptive randomized pivoting with expected-error guarantees (Cortinovis and Kressner, 2026). On the propagation side, Chaturantabut and Sorensen (2012) derived a priori state-space bounds showing that, for ODE systems from parabolic PDEs with Lipschitz nonlinearities, the POD-DEIM state error is proportional to the neglected POD and DEIM singular values; a posteriori estimators (error bounds computed from the actually obtained reduced solution) followed (Wirtz, Sorensen and Haasdonk, 2014; Eftang, Grepl and Patera, 2010 for EIM; Karatzas, 2026 at the finite-element level).

What remains unsettled is sharpness and certification. For the underlying matrix question - given orthonormal $U\in\mathbb{R}^{n\times m}$, select $m$ rows minimizing $\|(S^TU)^{-1}\|_2$ - the maximum-volume selection (the $m\times m$ submatrix of maximal determinant, the same object governing skeleton and CUR cross approximations (low-rank approximations assembled from selected rows and columns of the original matrix), cf. Sorensen and Embree's DEIM-induced CUR factorization) is known to achieve $\mathcal{C} \le \sqrt{1+m(n-m)}$ and is conjectured (Goreinov, Tyrtyshnikov and Zamarashkin, 1997) to satisfy the optimal bound $\mathcal{C} \le \sqrt n$, while no selection rule can guarantee less than $\sqrt n$ uniformly. Whether any efficiently computable selection achieves $O(\sqrt n)$, and whether the conjecture itself holds, are open; error bounds for masked projections including DEIM were still being tightened in 2025 (Tripathi and Shekhawat). On the methodological side, choosing the nonlinear-term snapshot ensemble and the DEIM dimension $m$ still rests on heuristics, chiefly the magnitude of the first neglected singular value $\sigma_{m+1}$, with no procedure that provably meets a user-specified tolerance uniformly over a parameter or time domain.

Problem Statement

The problem is the surviving open core of the error-control agenda left open by the DEIM paper of Chaturantabut and Sorensen (2010), after Q-DEIM and its successors settled the original pessimistic bound and the scalability of index selection. The two parts serve one objective - turning DEIM's error certificate from a loose worst-case estimate into tight, certified, practically predictive control - and are stated as separate open targets, each of which can be pursued and resolved on its own. The maximum-volume $\sqrt n$ conjecture in Part A(a) originates with Goreinov, Tyrtyshnikov and Zamarashkin (1997).

Part A (the amplification constant). For an orthonormal $U\in\mathbb{R}^{n\times m}$ (or $\mathbb{C}^{n\times m}$) with $m<n$, and a row-selection matrix $S=[e_{i_1},\dots,e_{i_m}]\in\mathbb{R}^{n\times m}$ whose columns are distinct standard basis vectors (so that $S^TU$ is the $m\times m$ submatrix of $U$ formed by rows $i_1,\dots,i_m$, and $\mathcal{C}$ is finite exactly when this submatrix is nonsingular), let $\mathcal{C}(S,U)=\|(S^TU)^{-1}\|_2$. Known today: $\mathcal{C}\le\sqrt{1+m(n-m)}$ is achieved by the maximum-volume selection (an existence result; exact volume maximization is not known to be efficiently computable); $\mathcal{C}\le\sqrt{n-m+1}\,\sqrt{4^m+6m-1}/3$ holds for the polynomial-time Q-DEIM selection; and $\sqrt n$ is a universal lower bound, so no selection rule can guarantee less in general. Determine the optimal worst-case behavior of $\mathcal{C}$ over efficiently computable selections, where 'efficiently computable' means polynomial time in $n$ and $m$, deterministic or with provable probabilistic guarantees. Concretely:

(a) prove or disprove the Goreinov-Zamarashkin-Tyrtyshnikov conjecture that the maximum-volume selection satisfies $\mathcal{C}\le\sqrt n$ for all orthonormal $U$;

(b) construct a polynomial-time computable selection with a proven bound $\mathcal{C}\le c\sqrt n$ for a constant $c$ independent of $n$ and $m$, or prove that every polynomial-time selection admits instances on which $\mathcal{C}$ is asymptotically larger than $\sqrt n$;

(c) sharpen the a priori worst-case bounds for the selections actually used in practice: for the original DEIM greedy rule, whose bound $(1+\sqrt{2n})^{m-1}\|u_1\|_\infty^{-1}$ is acknowledged in the 2010 paper to be very pessimistic and for which no matching lower bound is known; and, for Q-DEIM-type selections, where the exponential-in-$m$ factor is attained only on contrived Kahan-type matrices and is therefore worst-case unavoidable for that rule, so the remaining question concerns the constant and the $\sqrt{n-m+1}$ factor.

Part B (certified adaptive selection and stopping). Construct a snapshot-ensemble generation and DEIM basis/selection procedure with a stopping criterion for the DEIM dimension $m$ that carries a rigorously proven guarantee: for a user-specified tolerance $\varepsilon$, the resulting reduced model's solution error - including the propagated effect of the DEIM nonlinear-term error through the reduced dynamics and, for finite-element discretizations, on the reconstructed continuous solution - is at most $\varepsilon$ uniformly over the user-specified parameter or time domain on which the reduced model is to be certified. This domain is a nondegenerate continuum domain of the kind appearing in the DEIM setting (parameter sets $D\subset\mathbb{R}^d$ or time intervals), not a singleton or a finite set chosen to make the guarantee trivial. The guarantee must be a priori certifiable or follow from a posteriori bounds, thereby replacing the heuristic $\sigma_{m+1}$ stopping rule, and the certificate must be efficiently computable in addition to accurately predicting the error, as requested in the 2010 paper's future-work item.

The two parts are separate open targets of the same error-control agenda; neither presupposes the other. Part A is resolved when its items are settled: the gap between the universal $\sqrt n$ lower bound and the best efficiently computable selection is closed, by proof, construction, or impossibility, and sharp bounds are established for the practical DEIM greedy rule and for the constant factors of Q-DEIM-type selections. Part B is resolved when a concrete adaptive DEIM workflow carries a proven uniform tolerance guarantee over the certified parameter or time domain.

References

1. Saifon Chaturantabut and Danny C. Sorensen, Nonlinear Model Reduction via Discrete Empirical Interpolation, SIAM Journal on Scientific Computing 32(5):2737-2764, 2010. DOI: 10.1137/090766498. https://doi.org/10.1137/090766498
2. Saifon Chaturantabut and Danny C. Sorensen, A State Space Error Estimate for POD-DEIM Nonlinear Model Reduction, SIAM Journal on Numerical Analysis 50(1):46-63, 2012. DOI: 10.1137/110822724. https://doi.org/10.1137/110822724
3. Zlatko Drmač and Serkan Gugercin, A New Selection Operator for the Discrete Empirical Interpolation Method---Improved A Priori Error Bound and Extensions, SIAM Journal on Scientific Computing 38(2):A631-A648, 2016. DOI: 10.1137/15M1019271. https://doi.org/10.1137/15M1019271 (full text also at arXiv:1505.00370, https://arxiv.org/abs/1505.00370)
4. Zlatko Drmač and Arvind Krishna Saibaba, The Discrete Empirical Interpolation Method: Canonical Structure and Formulation in Weighted Inner Product Spaces, SIAM Journal on Matrix Analysis and Applications 39(3):1152-1180, 2018. DOI: 10.1137/17M1129635. https://doi.org/10.1137/17M1129635
5. Benjamin Peherstorfer, Zlatko Drmač, and Serkan Gugercin, Stability of Discrete Empirical Interpolation and Gappy Proper Orthogonal Decomposition with Randomized and Deterministic Sampling Points, SIAM Journal on Scientific Computing 42(5):A2837-A2864, 2020. DOI: 10.1137/19M1307391. https://doi.org/10.1137/19M1307391
6. Arvind K. Saibaba, Randomized Discrete Empirical Interpolation Method for Nonlinear Model Reduction, SIAM Journal on Scientific Computing 42(3):A1582-A1608, 2020. DOI: 10.1137/19M1243270. https://doi.org/10.1137/19M1243270
7. D. Wirtz, D. C. Sorensen, and B. Haasdonk, A Posteriori Error Estimation for DEIM Reduced Nonlinear Dynamical Systems, SIAM Journal on Scientific Computing 36(2):A311-A338, 2014. DOI: 10.1137/120899042. https://doi.org/10.1137/120899042
8. Benjamin Peherstorfer, Daniel Butnaru, Karen Willcox, and Hans-Joachim Bungartz, Localized Discrete Empirical Interpolation Method, SIAM Journal on Scientific Computing 36(1):A168-A192, 2014. DOI: 10.1137/130924408. https://doi.org/10.1137/130924408
9. Jens L. Eftang, Martin A. Grepl, and Anthony T. Patera, A posteriori error bounds for the empirical interpolation method, Comptes Rendus Mathematique 348(9-10):575-579, 2010. DOI: 10.1016/j.crma.2010.03.004. https://doi.org/10.1016/j.crma.2010.03.004
10. S. A. Goreinov, N. L. Zamarashkin, and E. E. Tyrtyshnikov, Pseudo-skeleton approximations by matrices of maximal volume, Mathematical Notes 62(4):515-519, 1997. DOI: 10.1007/BF02358985. https://doi.org/10.1007/BF02358985
11. S. A. Goreinov, E. E. Tyrtyshnikov, and N. L. Zamarashkin, A theory of pseudoskeleton approximations, Linear Algebra and its Applications 261:1-21, 1997. DOI: 10.1016/S0024-3795(96)00301-1. https://doi.org/10.1016/S0024-3795(96)00301-1 (the work from which Q-DEIM quotes the maximum-volume bound $\mathcal{C}\le\sqrt{1+m(n-m)}$, the conjectured $\sqrt n$ bound, and the universal $\sqrt n$ lower bound)
12. Alice Cortinovis and Daniel Kressner, Adaptive Randomized Pivoting for Column Subset Selection, DEIM, and Low-Rank Approximation, SIAM Journal on Matrix Analysis and Applications 47(1):25-47, 2026. DOI: 10.1137/24M1719189. https://doi.org/10.1137/24M1719189 (preprint arXiv:2412.13992, https://arxiv.org/abs/2412.13992)
13. Alexander Osinsky, Polynomial time $\rho$-locally maximum volume search, Calcolo 60(3), article 42, 2023. DOI: 10.1007/s10092-023-00536-2. https://doi.org/10.1007/s10092-023-00536-2
14. R. Stefanescu and A. Sandu, A Goal-Oriented Adaptive Discrete Empirical Interpolation Method, preprint arXiv:1901.05343, 2019. https://arxiv.org/abs/1901.05343
15. Brij Nandan Tripathi and Hanumant Singh Shekhawat, Enhanced Error Bounds For The Masked Projection Techniques via Cosine-Sine Decomposition, preprint arXiv:2501.01651, 2025. https://arxiv.org/abs/2501.01651
16. Efthymios N. Karatzas, A posteriori error analysis, Pod-Deim reduced order geometrically parametrized models and unfitted FEMs, preprint arXiv:2604.20044, 2026. https://arxiv.org/abs/2604.20044
17. D. C. Sorensen and Mark Embree, A DEIM Induced CUR Factorization, SIAM Journal on Scientific Computing 38(3):A1454-A1482, 2016. DOI: 10.1137/140978430. https://doi.org/10.1137/140978430
18. Maxime Barrault, Yvon Maday, Ngoc Cuong Nguyen, and Anthony T. Patera, An 'empirical interpolation' method: application to efficient reduced-basis discretization of partial differential equations, Comptes Rendus Mathematique 339(9):667-672, 2004. DOI: 10.1016/j.crma.2004.08.006. https://doi.org/10.1016/j.crma.2004.08.006
19. Frank de Hoog and Markus Hegland, A Note on Error Bounds for Pseudo Skeleton Approximations of Matrices, Linear Algebra and its Applications 669:102-117, 2023. DOI: 10.1016/j.laa.2023.03.024. https://doi.org/10.1016/j.laa.2023.03.024