On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices
From MaRDI portal
Publication:2310401
Abstract: The problem of finding a submatrix of maximum volume of a matrix is of interest in a variety of applications. For example, it yields a quasi-best low-rank approximation constructed from the rows and columns of . We show that such a submatrix can always be chosen to be a principal submatrix if is symmetric semidefinite or diagonally dominant. Then we analyze the low-rank approximation error returned by a greedy method for volume maximization, cross approximation with complete pivoting. Our bound for general matrices extends an existing result for symmetric semidefinite matrices and yields new error estimates for diagonally dominant matrices. In particular, for doubly diagonally dominant matrices the error is shown to remain within a modest factor of the best approximation error. We also illustrate how the application of our results to cross approximation for functions leads to new and better convergence results.
Recommendations
- Some algorithms for maximum volume and cross approximation of symmetric semidefinite matrices
- Pseudo-skeleton approximations by matrices of maximal volume
- Polynomial time \(\rho\)-locally maximum volume search
- On the accuracy of cross and column low-rank maxvol approximations in average
- How to find a good submatrix
Cites work
- A Survey of Condition Number Estimation for Triangular Matrices
- A theory of pseudoskeleton approximations
- Accuracy and Stability of Numerical Algorithms
- Accurate and efficient LDU decomposition of diagonally dominant M-matrices
- Adaptive cross approximation of multivariate functions
- Approximation of boundary element matrices
- Continuous analogues of matrix factorizations
- Error Analysis of Direct Methods of Matrix Inversion
- Error estimates for two-dimensional cross approximation
- Faster spectral sparsification and numerical algorithms for SDD matrices
- scientific article; zbMATH DE number 3950731 (Why is no real title available?)
- scientific article; zbMATH DE number 194139 (Why is no real title available?)
- scientific article; zbMATH DE number 6125590 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- scientific article; zbMATH DE number 4189084 (Why is no real title available?)
- Largest \(j\)-simplices in \(n\)-polytopes
- LDU decompositions with \(L\) and \(U\) well conditioned
- Low-rank tensor Krylov subspace methods for parametrized linear systems
- Matrix approximation and projective clustering via volume sampling
- Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
- Numerical Linear Algebra
- On largest volume simplices and sub-determinants
- On selecting a maximum volume sub-matrix of a matrix and related problems
- On the existence and computation of rank-revealing LU factorizations
- On the low-rank approximation by the pivoted Cholesky decomposition
- Perturbation theory for the LDU factorization and accurate computations for diagonally dominant matrices
- Preconditioning linear least-squares problems by identifying a basis matrix
- Relative-Error CUR Matrix Decompositions
- Some problems in the approximation of functions of two variables and n- widths of integral operators
- Stable and efficient Gaussian process calculations
- Strong rank revealing LU factorizations
- The maximal-volume concept in approximation by low-rank matrices
Cited in
(15)- On selecting a maximum volume sub-matrix of a matrix and related problems
- Rectangular maximum-volume submatrices and their applications
- Some algorithms for maximum volume and cross approximation of symmetric semidefinite matrices
- A GPU parallel randomized CUR compression method for the method of moments
- How to find a good submatrix
- CUR LRA at Sublinear Cost Based on Volume Maximization
- Low-Rank Approximation in the Frobenius Norm by Column and Row Subset Selection
- Polynomial time \(\rho\)-locally maximum volume search
- Approximation in the extended functional tensor train format
- Maximal volume matrix cross approximation for image compression and least squares solution
- Learning tensor networks with tensor cross interpolation: new algorithms and libraries
- A sublinear-time randomized algorithm for column and row subset selection based on strong rank-revealing QR factorizations
- Algorithm-agnostic low-rank approximation of operator monotone matrix functions
- Convergence rates for pivoted QR and LU
- A Geometric View of Adaptive Cross Approximation via Exterior Algebra
This page was built for publication: On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2310401)
