Estimating a matrix's singular values with interpolative decompositions
Vector spaces, linear dependence, rank, lineability (15A03) Eigenvalues, singular values, and eigenvectors (15A18) Factorization of matrices (15A23) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical methods for low-rank matrix approximation; matrix compression (65F55)
This paper studies rank-revealing algorithms for estimating a matrix's singular values by selecting informative rows and/or columns, a fundamental task in matrix compression, low-rank approximation, and column subset selection. While column-pivoted QR (CPQR) is widely used in practice, it lacks rigorous guarantees as a rank-revealer, whereas Gaussian elimination (GE) with global maximum-volume (maxvol) pivoting has strong theoretical guarantees but is computationally infeasible. The authors show that near-local maximum-volume pivoting provides the missing bridge between theory and practice: it is both necessary and sufficient for GE- and QR-based methods to reliably estimate singular values with polynomially bounded error factors. They prove that any pivot that is locally (or near-locally) maximal in volume performs nearly as well as the global maxvol pivot, thereby unifying GE and QR within a common theoretical framework. Building on this insight, the paper elevates Gu-Eisenstat rank-revealing QR as an archetypal method and presents efficient implementations whose cost is comparable to CPQR while retaining provable guarantees.
- A DEIM induced CUR factorization
- A fast direct solver for boundary integral equations in two dimensions
- A fast direct solver for structured linear systems by recursive skeletonization
- A generalization of the Eckart-Young-Mirsky matrix approximation theorem
- A literature survey of low-rank tensor approximation techniques
- A new selection operator for the discrete empirical interpolation method -- improved a priori error bound and extensions
- A recursive skeletonization factorization based on strong admissibility
- A theory of pseudoskeleton approximations
- An `empirical interpolation' method: Application to efficient reduced-basis discretization of partial differential equations
- An Extension of Chebfun to Two Dimensions
- An improved approximation algorithm for the column subset selection problem
- Approximation of boundary element matrices
- Bounds on singular values revealed by QR factorizations
- Close to optimal column approximation using a single SVD
- Communication avoiding rank revealing QR factorization with column pivoting
- Computing rank-revealing QR factorizations of dense matrices
- Computing the singular value decomposition with high relative accuracy
- Computing Truncated Singular Value Decomposition Least Squares Solutions by Rank Revealing QR-Factorizations
- CUR matrix decompositions for improved data analysis
- Decay properties of spectral projectors with applications to electronic structure
- Determinantal point processes in randomized numerical linear algebra
- Disentanglement via Entanglement: A Unified Method for Wannier Localization
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Efficient volume sampling for row/column subset selection
- Eigenvalues of rank-one updated matrices with some applications
- Fast algorithms for hierarchically semiseparable matrices
- Fast randomized numerical rank estimation for numerically low-rank matrices
- Fast spatial Gaussian process maximum likelihood estimation via skeletonization factorizations
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Handbook series linear algebra. Linear least squares solutions by Householder transformations
- Hierarchical matrices. A means to efficiently solve elliptic boundary value problems
- How to find a good submatrix
- scientific article; zbMATH DE number 852525 (Why is no real title available?)
- Low-Rank Approximation in the Frobenius Norm by Column and Row Subset Selection
- Low‐rank revealing QR factorizations
- Making the Nystr\"om method highly accurate for low-rank approximations
- Nonlinear model reduction via discrete empirical interpolation
- Numerical Linear Algebra
- Numerical methods for Kohn–Sham density functional theory
- Numerical methods for solving linear least squares problems
- On Rank-Revealing Factorisations
- On selecting a maximum volume sub-matrix of a matrix and related problems
- On the Compression of Low Rank Matrices
- On the existence and computation of rank-revealing LU factorizations
- On the Nyström method for approximating a gram matrix for improved kernel-based learning
- Piecewise polynomial, positive definite and compactly supported radial functions of minimal degree
- Principal submatrices. IX: Interlacing inequalities for singular values of submatrices
- Quasioptimality of skeleton approximation of a matrix in the Chebyshev norm
- Randomized Discrete Empirical Interpolation Method for Nonlinear Model Reduction
- Randomized numerical linear algebra: Foundations and algorithms
- randUTV: a blocked randomized algorithm for computing a rank-revealing UTV factorization
- Rang revealing QR factorizations
- Rank revealing Gaussian elimination by the maximum volume concept
- Rank-Revealing QR Factorizations and the Singular Value Decomposition
- Rectangular maximum-volume submatrices and their applications
- SCDM-k: localized orbitals for solids via selected columns of the density matrix
- Simple, direct and efficient multi-way spectral clustering
- Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
- Solving polynomial systems via truncated normal forms
- Some Applications of the Rank Revealing QR Factorization
- Strong rank revealing LU factorizations
- The approximation of one matrix by another of lower rank.
- The Discrete Empirical Interpolation Method: Canonical Structure and Formulation in Weighted Inner Product Spaces
- The maximal-volume concept in approximation by low-rank matrices
- The Restricted Singular Value Decomposition of Matrix Triplets
This page was built for publication: Estimating a matrix's singular values with interpolative decompositions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6883484)
