Rectangular maximum volume and projective volume search algorithms

2018/09/07 by Alexander Osinsky, Osinsky, Alexander · 3 citations
Computer Science · Mathematics · Physics and Astronomy · #65F30 #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Scientific Research and Discoveries

paper · pdf · doi:10.48550/arxiv.1809.02334

openalex publication_date 2018/09/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

New methods for finding submatrices of (locally) maximal volume and large projective volume are proposed and studied. Detailed analysis is also carried out for existing methods. The effectiveness of the new methods is shown in the construction of cross approximations, and estimates are also proved in the case of their application for the search for a strongly nondegenerate submatrix. Much attention is also paid to the choice of the starting submatrix.

Cited by

• Interpolatory Dynamical Low-Rank Approximation: Theoretical Foundations and Algorithms
• Perturbations of CUR Decompositions
• Low Rank Approximation at Sublinear Cost

Related

• Some algorithms for maximum volume and cross approximation of symmetric semidefinite matrices
• On maximum volume submatrices and cross approximation for symmetric\n semidefinite and diagonally dominant matrices
• Exponential Inapproximability of Selecting a Maximum Volume Sub-matrix
• Maximal Volume Matrix Cross Approximation for Image Compression and Least Squares Solution
• On largest volume simplices and sub-determinants