Source-linked AI summary
A New Selection Operator for the Discrete Empirical Interpolation Method -- improved a priori error bound and extensions
Zlatko Drmac, Serkan Gugercin
TL;DR
Nonlinear reduced models face a lifting bottleneck, and existing DEIM theory raises questions about sharper, less dimension-dependent bounds and basis dependence. The paper introduces Q-DEIM via pivoted QR, extends it to restricted row information, and reports accurate approximations, including full accuracy recovery from 220 sampled rows instead of 10000.
Problem
Nonlinear reduced models require lifting reduced states to the full dimension for nonlinear evaluations, while DEIM theory motivates sharper bounds with weaker dependence on n.
Method
Q-DEIM selects interpolation indices through QR factorization with column pivoting, equivalently an LQ factorization with row pivoting, using robust high-performance implementations.
Results
220 rows fully recover the accuracy achieved using all 10000 rows of U, while DEIM and Q-DEIM both achieve high reconstruction accuracy in the nonlinear RC example.
Takeaways & Limitations
The framework supports basis-invariant DEIM projections, randomized or restricted-row variants with probabilistic guarantees, and applications including least squares, CUR factorization, and parametric model reduction.
Takeaways & Limitations
The paper notes that standard DEIM selections depend on the chosen orthonormal basis and that partial-pivoting bounds can be pessimistic.
Abstract
from arXiv · showhide
This paper introduces a new framework for constructing the Discrete Empirical Interpolation Method DEIM projection operator. The interpolation node selection procedure is formulated using the QR factorization with column pivoting, and it enjoys a sharper error bound for the DEIM projection error. Furthermore, for a subspace $\mathcal{U}$ given as the range of an orthonormal $U$, the DEIM projection does not change if $U$ is replaced by $U Ω$ with arbitrary unitary matrix $Ω$. In a large-scale setting, the new approach allows modifications that use only randomly sampled rows of $U$, but with the potential of producing good approximations with corresponding probabilistic error bounds. Another salient feature of the new framework is that robust and efficient software implementation is easily developed, based on readily available high performance linear algebra packages.
1. Introduction.
Large-scale nonlinear dynamical systems motivate reduced models, but evaluating reduced nonlinearities can require lifting states to the full dimension. DEIM addresses this bottleneck by interpolating nonlinear functions at selected coordinates, while Q-DEIM seeks sharper, basis-invariant selection with efficient large-scale extensions.
- Large-scale systems can demand overwhelming computational resources, motivating lower-dimensional surrogate models with high fidelity.
- Galerkin model reduction approximates the full state as x(t) ≈ Vx_r(t) in an r-dimensional subspace, with r ≪ n.
- The reduced nonlinear term still requires lifting x_r(t) to the full dimension, creating a lifting bottleneck that degrades nonlinear reduced-model performance.
- DEIM approximates general nonlinear functions using a rank-m basis and a selection operator that chooses coordinate indices for interpolation.
- The original DEIM selection depends on the particular orthonormal basis, even though the subspace spanned by that basis may be well determined.
- Q-DEIM uses QR factorization with column pivoting to obtain basis-invariant indices, improve the error bound, and support robust high-performance implementations.
- Q-DEIMr extends the approach by selecting from only a portion of U's rows and combining the Q-DEIM technique with randomized sampling.
2. A new DEIM framework.
Q-DEIM constructs DEIM selection operators through column-pivoted QR, improving theoretical conditioning guarantees while making selections invariant to orthonormal basis changes. Experiments show comparable or sometimes better reconstruction than DEIM, and the framework supports randomized row sampling.
- Q-DEIM construction: Q-DEIM uses column-pivoted QR to construct the DEIM selection operator with complexity O(nm^2), while supporting high-performance linear algebra implementations.The QR procedure selects columns through pivoting and maps them to selected rows of U.
- Theoretical guarantees: Q-DEIM provides an improved upper bound for the DEIM projection error and a selection operator invariant under arbitrary unitary changes UΩ of the orthonormal basis.The invariant selection depends on the represented subspace rather than a particular orthonormal basis.
- Numerical comparison: For the FitzHugh–Nagumo model with r = m = 5, the relative reconstruction errors were 3.500673 × 10^−2 for DEIM and 3.467286 × 10^−2 for Q-DEIM.Both procedures were reported to perform equally well in entrywise snapshot reconstruction.
- Numerical comparison: For the nonlinear RC model, both methods produced highly accurate reduced quantities, with virtually indistinguishable voltage trajectories and errors decreasing as r = m increased from 10 to 20.For r = m = 10, the reported reconstruction errors were 8.603826 × 10^−3 for DEIM and 6.07172 × 10^−3 for Q-DEIM; for r = m = 20, they were 1.970500 × 10^−4 and 1.931018 × 10^−4.
- Extensions: The framework extends to Q-DEIMr, which applies Q-DEIM to randomly sampled rows of U and introduces randomized sampling into DEIM selection.The extension is intended for large-scale settings and is associated with probabilistic error bounds in the framework.
3. Using restricted/randomized basis information.
Q-DEIMr adapts Q-DEIM to select interpolation indices from restricted, randomly sampled rows of U, reducing the amount of basis information processed while targeting a well-conditioned submatrix. In Example 3.1, processing substantially fewer rows could recover the accuracy of using all 10000 rows, although performance depended on the sampling and conditioning threshold.
- Restricted/randomized selection: Q-DEIMr seeks a well-conditioned submatrix by processing only selected columns of W, equivalent to selected rows of U, rather than factorizing the full matrix.The procedure uses QR with column pivoting and an incremental condition estimator to monitor the triangular factor during selection.
- Restricted/randomized selection: Q-DEIMr is intended to reduce the O(m^2n) cost associated with determining a selection operator when n is large.The approach focuses on finding suitable indices, not computing a full QR factorization of W.
- Restricted/randomized selection: The randomized procedure samples k ≥ m columns into a local m × k work array and updates newly selected columns before pivoting.Accepted pivots are retained, while candidates failing the conditioning threshold are discarded and replaced from the active set.
- Numerical example: In Example 3.1, Q-DEIMr processed 113 rows of U, at most 34 simultaneously, whereas DEIM used all 10000 rows.The example used m = 34 basis columns and evaluated relative reconstruction errors over 200 uniformly spaced parameter values.
- Numerical example: By visiting 220 rows, Q-DEIMr fully recovered the accuracy achieved by using all 10000 rows of U.Changing the prescribed upper bound for c altered execution and performance; without sophisticated sampling, results could vary with n, m, and the bound.
- Interpretation: Q-DEIMr connects DEIM with randomized numerical linear algebra as a guided randomized sampling method for orthonormal matrices.The authors note that detailed analysis of blending the procedures was deferred to subsequent work, while the approach was tested on numerical examples and produced high-fidelity approximations.
4. Conclusions and Future Work.
The authors identify additional applications for Q-DEIM, including randomized least-squares sampling, DEIM-induced CUR factorization, and nonlinear inversion or parametric model reduction. They also describe ongoing testing and incremental basis-updating extensions.
- Future applications: Q-DEIM is being investigated for randomized sampling of rows of orthonormal matrices in large least-squares problems.The stated application targets problems with huge row dimension.
- Future applications: Other planned applications include DEIM-induced CUR factorization and affine decomposition for nonlinear inversion and parametric model reduction.Vectorizing parametric matrix functions can create very large row dimensions depending on sparsity patterns.
- Future extensions: Q-DEIM and Q-DEIMr can use incremental updates when the nonlinear snapshot basis comes from the SVD.Increasing m and enlarging U is described as a way to obtain better approximations, with corresponding updates to the rank-revealing QR decomposition.