A DEIM Induced CUR Factorization

DOI10.1137/140978430zbMath1382.65121arXiv1407.5516OpenAlexW2272541835MaRDI QIDQ2810324

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

low-rank approximationdiscrete empirical interpolation methodpseudoskeleton decompositionCUR factorizationone-pass QR decomposition

Mathematics Subject Classification ID

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

Related Items

Feasibility of DEIM for retrieving the initial field via dimensionality reduction, Efficient algorithms for CUR and interpolative matrix decompositions, Randomized numerical linear algebra: Foundations and algorithms, Three matrix factorizations from the steps of elimination, A Generalized CUR Decomposition for Matrix Pairs, Perturbations of the \textsc{Tcur} decomposition for tensor valued data in the Tucker format, Tensor CUR Decomposition under T-Product and Its Perturbation, Randomized matrix-free trace and log-determinant estimators, Improved Variants of the Hutch++ Algorithm for Trace Estimation, 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, Adaptive sparse interpolation for accelerating nonlinear stochastic reduced-order modeling with time-dependent bases, CUR and Generalized CUR Decompositions of Quaternion Matrices and their Applications, The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection, Randomized Discrete Empirical Interpolation Method for Nonlinear Model Reduction, System Identification via CUR-Factored Hankel Approximation, Randomized Subspace Iteration: Analysis of Canonical Angles and Unitarily Invariant Norms, Randomized algorithms for the low multilinear rank approximations of tensors, Model Order Reduction Algorithms in the Design of Electric Machines, Low-Rank Approximation in the Frobenius Norm by Column and Row Subset Selection, Interpolation-Based Model Order Reduction for Polynomial Systems, A parametric and non-intrusive reduced order model of car crash simulation, A New Selection Operator for the Discrete Empirical Interpolation Method---Improved A Priori Error Bound and Extensions, Perspectives on CUR decompositions, An extended DEIM algorithm for subset selection and class identification, Flip-flop spectrum-revealing QR factorization and its applications to singular value decomposition, 6 The Loewner framework for system identification and reduction, HOID: Higher Order Interpolatory Decomposition for Tensors Based on Tucker Representation, A Randomized Blocked Algorithm for Efficiently Computing Rank-revealing Factorizations of Matrices, Unnamed Item, Perturbations of CUR Decompositions, Robust CUR Decomposition: Theory and Imaging Applications, Hybrid CUR-type decomposition of tensors in the Tucker format

Uses Software

• PROPACK
• ARPACK

Cites Work

• Unnamed Item
• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• CUR matrix decompositions for improved data analysis
• Low-rank incremental methods for computing dominant singular subspaces
• The many proofs of an identity on the norm of oblique projections
• A theory of pseudoskeleton approximations
• An `empirical interpolation' method: Application to efficient reduced-basis discretization of partial differential equations
• Four algorithms for the the efficient computation of truncated pivoted QR approximations to a sparse matrix
• An implicitly restarted block Lanczos bidiagonalization method using Leja shifts
• Rounding error analysis of the classical Gram-Schmidt orthogonalization process
• A Jacobi--Davidson Type SVD Method
• A New Selection Operator for the Discrete Empirical Interpolation Method---Improved A Priori Error Bound and Extensions
• Optimal CUR Matrix Decompositions
• Nonlinear Model Reduction via Discrete Empirical Interpolation
• Average-Case Stability of Gaussian Elimination
• Relative-Error $CUR$ Matrix Decompositions
• Reorthogonalization and Stable Algorithms for Updating the Gram-Schmidt QR Factorization
• Numerical Linear Algebra for High-Performance Computers
• ARPACK Users' Guide
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• On the Compression of Low Rank Matrices