On selecting a maximum volume sub-matrix of a matrix and related problems
From MaRDI portal
Publication:1034598
DOI10.1016/j.tcs.2009.06.018zbMath1181.15002OpenAlexW2076410399MaRDI QIDQ1034598
Malik Magdon-Ismail, Ali Çivril
Publication date: 6 November 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2009.06.018
complexitycondition numbersubset selectionNP-hardnesslow-rank approximationsQR factorizationsmaximum volume sub-matrix
Related Items (37)
Polynomial fitting and interpolation on circular sections ⋮ Compression of Multivariate Discrete Measures and Applications ⋮ Efficient preconditioning for noisy separable nonnegative matrix factorization problems by successive projection based low-rank approximations ⋮ Column subset selection problem is UG-hard ⋮ Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes ⋮ Unnamed Item ⋮ Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design ⋮ A Local Search Framework for Experimental Design ⋮ A Spectral Approach to Network Design ⋮ Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions ⋮ Polynomial time \(\rho\)-locally maximum volume search ⋮ Revisiting the (block) Jacobi subspace rotation method for the symmetric eigenvalue problem ⋮ A hybrid stochastic interpolation and compression method for kernel matrices ⋮ Exponential inapproximability of selecting a maximum volume sub-matrix ⋮ Literature survey on low rank approximation of matrices ⋮ Polynomial interpolation and cubature over polygons ⋮ Matrices with Hierarchical Low-Rank Structures ⋮ Near-optimal discrete optimization for experimental design: a regret minimization approach ⋮ Column subset selection is NP-complete ⋮ Low-Rank Approximation in the Frobenius Norm by Column and Row Subset Selection ⋮ Geometric weakly admissible meshes, discrete least squares approximations and approximate Fekete points ⋮ Fixed-size determinantal point processes sampling for species phylogeny ⋮ SAGA: sparse and geometry-aware non-negative matrix factorization through non-linear local embedding ⋮ Tensor-train numerical integration of multivariate functions with singularities ⋮ Spectral Tensor-Train Decomposition ⋮ Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration ⋮ On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices ⋮ Subset selection for matrices with fixed blocks ⋮ Diversity Sampling is an Implicit Regularization for Kernel Methods ⋮ Unnamed Item ⋮ Linear equalities in blackbox optimization ⋮ CUR LRA at Sublinear Cost Based on Volume Maximization ⋮ Gaussian Process Landmarking on Manifolds ⋮ Near-optimal polynomial interpolation on spherical triangles ⋮ Some algorithms for maximum volume and cross approximation of symmetric semidefinite matrices ⋮ A Robust and Scalable Implementation of the Parks-McClellan Algorithm for Designing FIR Filters ⋮ On the Use of Compressed Polyhedral Quadrature Formulas in Embedded Interface Methods
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Rang revealing QR factorizations
- Subset selection for matrices
- Factoring polynomials with rational coefficients
- On the existence and computation of rank-revealing LU factorizations
- Bounds on singular values revealed by QR factorizations
- Handbook series linear algebra. Linear least squares solutions by Householder transformations
- Matrix approximation and projective clustering via volume sampling
- Adaptive Sampling and Fast Low-Rank Matrix Approximation
- Rank-Revealing QR Factorizations and the Singular Value Decomposition
- On Rank-Revealing Factorisations
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Fast monte-carlo algorithms for finding low-rank approximations
- Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
- Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition
- Numerical Linear Algebra
This page was built for publication: On selecting a maximum volume sub-matrix of a matrix and related problems
