A DEIM induced CUR factorization

DOI10.1137/140978430MaRDI QIDQ2810324zbMATH OpenOpenAlexFDO

Authors Mark Embree, Danny C. Sorensen

Publication date 1 June 2016

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.5516

zbMATH Keywords

CUR factorizationdiscrete empirical interpolation methodlow-rank approximationone-pass QR decompositionpseudoskeleton decomposition

Mathematics Subject Classification ID

Factorization of matrices (15A23) Linear operator approximation theory (47A58) Numerical computation of matrix norms, conditioning, scaling (65F35) Approximation algorithms (68W25)

Abstract: We derive a CUR matrix factorization based on the Discrete Empirical Interpolation Method (DEIM). For a given matrix $A$, such a factorization provides a low rank approximate decomposition of the form $AapproxCUR$, where $C$ and $R$ are subsets of the columns and rows of $A$, and $U$ is constructed to make $CUR$ a good approximation. Given a low-rank singular value decomposition $AapproxVS{W}^T$, the DEIM procedure uses $V$ and $W$ to select the columns and rows of $A$ that form $C$ and $R$. Through an error analysis applicable to a general class of CUR factorizations, we show that the accuracy tracks the optimal approximation error within a factor that depends on the conditioning of submatrices of $V$ and $W$. For large-scale problems, $V$ and $W$ can be approximated using an incremental QR algorithm that makes one pass through $A$. Numerical examples illustrate the favorable performance of the DEIM-CUR method, compared to CUR approximations based on leverage scores.

Recommendations

• Asymptotic expansions for a model with distinguished “fast” and “slow” variables, described by a system of singularly perturbed stochastic differential equations
• Factorization in noncommutative curves
• DEFORMATION OF ALGEBRA FACTORISATIONS
• Factorization of zero curvature representations
• Direct decompositions with finite dimensional factors
• De Rham \(\mathcal E\)-factors
• Perturbations of CUR Decompositions
• scientific article; zbMATH DE number 2037765
• A decomposition theorem in \(\mathrm{II}_{1}\)-factors
• Irreducible decomposition of curves

Cites work

• A Jacobi--Davidson type SVD method
• A new selection operator for the discrete empirical interpolation method -- improved a priori error bound and extensions
• A theory of pseudoskeleton approximations
• An `empirical interpolation' method: Application to efficient reduced-basis discretization of partial differential equations
• An implicitly restarted block Lanczos bidiagonalization method using Leja shifts
• ARPACK Users' Guide
• Average-Case Stability of Gaussian Elimination
• CUR matrix decompositions for improved data analysis
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Four algorithms for the the efficient computation of truncated pivoted QR approximations to a sparse matrix
• scientific article; zbMATH DE number 1012640 (Why is no real title available?)
• Improving CUR matrix decomposition and the Nyström approximation via adaptive sampling
• Low-rank incremental methods for computing dominant singular subspaces
• Nonlinear model reduction via discrete empirical interpolation
• Numerical Linear Algebra for High-Performance Computers
• On the Compression of Low Rank Matrices
• Relative-Error CUR Matrix Decompositions
• Reorthogonalization and Stable Algorithms for Updating the Gram-Schmidt QR Factorization
• Rounding error analysis of the classical Gram-Schmidt orthogonalization process
• The many proofs of an identity on the norm of oblique projections

Cited in

(74)

• A parametric and non-intrusive reduced order model of car crash simulation
• An extended DEIM algorithm for subset selection and class identification
• Hybrid CUR-type decomposition of tensors in the Tucker format
• Feasibility of DEIM for retrieving the initial field via dimensionality reduction
• Perturbations of the \textsc{Tcur} decomposition for tensor valued data in the Tucker format
• Randomized algorithms for the low multilinear rank approximations of tensors
• Linear-time CUR approximation of BEM matrices
• Perspectives on CUR decompositions
• Efficient algorithms for CUR and interpolative matrix decompositions
• Randomized matrix-free trace and log-determinant estimators
• Adaptive sparse interpolation for accelerating nonlinear stochastic reduced-order modeling with time-dependent bases
• A new selection operator for the discrete empirical interpolation method -- improved a priori error bound and extensions
• HOID: higher order interpolatory decomposition for tensors based on Tucker representation
• A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices
• Model Order Reduction Algorithms in the Design of Electric Machines
• 6 The Loewner framework for system identification and reduction
• System identification via CUR-factored Hankel approximation
• Randomized subspace iteration: analysis of canonical angles and unitarily invariant norms
• Three matrix factorizations from the steps of elimination
• A generalized CUR decomposition for matrix pairs
• Tensor CUR decomposition under T-product and its perturbation
• Improved Variants of the Hutch++ Algorithm for Trace Estimation
• The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection
• Randomized Discrete Empirical Interpolation Method for Nonlinear Model Reduction
• Low-Rank Approximation in the Frobenius Norm by Column and Row Subset Selection
• Interpolation-based model order reduction for polynomial systems
• Mode-wise tensor decompositions: multi-dimensional generalizations of CUR decompositions
• Flip-flop spectrum-revealing QR factorization and its applications to singular value decomposition
• Perturbations of CUR Decompositions
• Robust CUR Decomposition: Theory and Imaging Applications
• Randomized numerical linear algebra: Foundations and algorithms
• Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
• A literature survey of matrix methods for data science
• Interpolatory input and output projections for flow control
• A Hybrid DEIM and Leverage Scores Based Method for CUR Index Selection
• CUR and Generalized CUR Decompositions of Quaternion Matrices and their Applications
• A Restricted SVD type CUR Decomposition for Matrix Triplets
• Randomized low-rank approximation methods for projection-based model order reduction of large nonlinear dynamical problems
• Approximation in the extended functional tensor train format
• An L-DEIM induced high order tensor interpolatory decomposition
• Block discrete empirical interpolation methods
• Randomized greedy magic point selection schemes for nonlinear model reduction
• Randomized GCUR decompositions
• Korean topic modeling using matrix decomposition
• Maximal volume matrix cross approximation for image compression and least squares solution
• A multilinear HJB-POD method for the optimal control of PDEs on a tree structure
• Efficient bounds and estimates for canonical angles in randomized subspace approximations
• The discrete empirical interpolation method in class identification and data summarization
• Cross interpolation for solving high-dimensional dynamical systems on low-rank Tucker and tensor train manifolds
• Collocation methods for nonlinear differential equations on low-rank manifolds
• Randomized approach to matrix completion: applications in recommendation systems and image inpainting
• Interpolatory dynamical low-rank approximation for the 3+3d Boltzmann-BGK equation
• Practical challenges in data-driven interpolation: dealing with noise, enforcing stability, and computing realizations
• Adaptive randomized pivoting for column subset selection, DEIM, and low-rank approximation
• Estimating a matrix's singular values with interpolative decompositions
• Empirical sparse regression on quadratic manifolds
• A novel greedy block Gauss-Seidel method for solving large linear least-squares problems
• Robust blockwise random pivoting: fast and accurate adaptive interpolative decomposition
• Low-rank approximation of parameter-dependent matrices via CUR decomposition
• A semi-Lagrangian adaptive-rank (SLAR) method for linear advection and nonlinear Vlasov-Poisson system
• Structure-aware analyses and algorithms for interpolative decompositions
• A new analysis of empirical interpolation methods and Chebyshev greedy algorithms
• Accuracy and stability of CUR decompositions with oversampling
• Efficient quaternion CUR decomposition based on discrete empirical interpolation method
• Accelerating high-fidelity simulations of chemically reacting flows using reduced-order modeling with time-dependent bases
• On the optimality of Voronoi-based column selection
• A sublinear-time randomized algorithm for column and row subset selection based on strong rank-revealing QR factorizations
• Bayesian D-optimal experimental designs via column subset selection
• Leverage score-based quaternion CUR decomposition: gap error analysis and applications
• Quasi-optimal hierarchically semi-separable matrix approximation
• Computing Strong Rank-Revealing Factorizations for Matrices with Orthonormal Rows
• librla: Randomized Linear Algebra Library
• Collect, commit, expand: efficient CPQR-based column selection for extremely wide matrices
• A Geometric View of Adaptive Cross Approximation via Exterior Algebra

Describes a project that uses

Uses Software

• PROPACK
• ARPACK

This page was built for publication: A DEIM induced CUR factorization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2810324)