Polynomial time -locally maximum volume search

DOI10.1007/S10092-023-00536-2MaRDI QIDQ6073869zbMATH OpenOpenAlexFDO

Authors Alexander Osinsky

Publication date 18 September 2023

Published in Calcolo (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10092-023-00536-2

zbMATH Keywords

cross approximationGaussian eliminationlocally maximum volumerank revealing LU

Mathematics Subject Classification ID

Factorization of matrices (15A23) Numerical methods for low-rank matrix approximation; matrix compression (65F55) Complexity and performance of numerical algorithms (65Y20)

Recommendations

• How to find a good submatrix
• Rank revealing Gaussian elimination by the maximum volume concept
• Pseudo-skeleton approximations by matrices of maximal volume

Cites work

• A theory of pseudoskeleton approximations
• Adaptive low-rank approximation of collocation matrices
• Approximation of boundary element matrices
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• Exponential inapproximability of selecting a maximum volume sub-matrix
• How to find a good submatrix
• On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices
• On selecting a maximum volume sub-matrix of a matrix and related problems
• On the accuracy of cross and column low-rank maxvol approximations in average
• On the existence and computation of rank-revealing LU factorizations
• Pseudo-skeleton approximations with better accuracy estimates
• Quasioptimality of skeleton approximation of a matrix in the Chebyshev norm
• Some algorithms for maximum volume and cross approximation of symmetric semidefinite matrices
• Strong rank revealing Cholesky factorization
• Strong rank revealing LU factorizations
• The maximal-volume concept in approximation by low-rank matrices
• TT-cross approximation for multidimensional arrays

Cited in

(6)

• Rectangular maximum-volume submatrices and their applications
• On the query complexity of finding a local maximum point.
• On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices
• A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume
• Close to optimal column approximation using a single SVD
• Fast numerical method for source function reconstruction in the coagulation-fragmentation equation

This page was built for publication: Polynomial time \(\rho\)-locally maximum volume search

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