On selecting a maximum volume sub-matrix of a matrix and related problems
From MaRDI portal
Publication:1034598
DOI10.1016/J.TCS.2009.06.018zbMATH Open1181.15002OpenAlexW2076410399MaRDI QIDQ1034598FDOQ1034598
Authors: Ali Çivril, Malik Magdon-Ismail 
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
Recommendations
- Exponential inapproximability of selecting a maximum volume sub-matrix
- Rectangular maximum-volume submatrices and their applications
- Submatrix maximum queries in Monge matrices and partial Monge matrices, and their applications
- Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications
- On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices
- Subspace Selection for Projection Maximization With Matroid Constraints
- A note on subset selection for matrices
- The maximal-volume concept in approximation by low-rank matrices
- Improved submatrix maximum queries in Monge matrices
- On a variant of the problem of choosing a vector subset
complexitycondition numberNP-hardnesslow-rank approximationssubset selectionQR factorizationsmaximum volume sub-matrix
Cites Work
- Rang revealing QR factorizations
- Title not available (Why is that?)
- The maximal-volume concept in approximation by low-rank matrices
- Title not available (Why is that?)
- Fast monte-carlo algorithms for finding low-rank approximations
- Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition
- Title not available (Why is that?)
- Handbook series linear algebra. Linear least squares solutions by Householder transformations
- Factoring polynomials with rational coefficients
- Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
- On the existence and computation of rank-revealing LU factorizations
- On Rank-Revealing Factorisations
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Numerical Linear Algebra
- Rank-Revealing QR Factorizations and the Singular Value Decomposition
- Subset selection for matrices
- Matrix approximation and projective clustering via volume sampling
- Adaptive Sampling and Fast Low-Rank Matrix Approximation
- Bounds on singular values revealed by QR factorizations
Cited In (43)
- Low-Rank Approximation in the Frobenius Norm by Column and Row Subset Selection
- An efficient frequency-independent numerical method for computing the far-field pattern induced by polygonal obstacles
- Column subset selection problem is UG-hard
- Some algorithms for maximum volume and cross approximation of symmetric semidefinite matrices
- Near-optimal discrete optimization for experimental design: a regret minimization approach
- Near-optimal polynomial interpolation on spherical triangles
- Polynomial fitting and interpolation on circular sections
- Fixed-size determinantal point processes sampling for species phylogeny
- Compression of Multivariate Discrete Measures and Applications
- Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
- Efficient preconditioning for noisy separable nonnegative matrix factorization problems by successive projection based low-rank approximations
- Proportional volume sampling and approximation algorithms for \(A\)-optimal design
- Revisiting the (block) Jacobi subspace rotation method for the symmetric eigenvalue problem
- On the Use of Compressed Polyhedral Quadrature Formulas in Embedded Interface Methods
- Linear equalities in blackbox optimization
- Column subset selection is NP-complete
- CUR LRA at Sublinear Cost Based on Volume Maximization
- Diversity sampling is an implicit regularization for kernel methods
- Gaussian process landmarking on manifolds
- Mode-wise tensor decompositions: multi-dimensional generalizations of CUR decompositions
- Spectral tensor-train decomposition
- Title not available (Why is that?)
- Maximal volume matrix cross approximation for image compression and least squares solution
- Beyond symmetry: best submatrix selection for the sparse truncated SVD
- Tensor-train numerical integration of multivariate functions with singularities
- Subdeterminant maximization via nonconvex relaxations and anti-concentration
- A hybrid stochastic interpolation and compression method for kernel matrices
- Subset selection for matrices with fixed blocks
- SAGA: sparse and geometry-aware non-negative matrix factorization through non-linear local embedding
- Polynomial interpolation and cubature over polygons
- Literature survey on low rank approximation of matrices
- A Spectral Approach to Network Design
- On the complexity of approximating extremal determinants in matrices
- Convergence of sparse variational inference in Gaussian processes regression
- Polynomial time \(\rho\)-locally maximum volume search
- Geometric weakly admissible meshes, discrete least squares approximations and approximate Fekete points
- Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes
- On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices
- On the parameterized intractability of determinant maximization
- Matrices with hierarchical low-rank structures
- A robust and scalable implementation of the Parks-McClellan algorithm for designing FIR filters
- A Local Search Framework for Experimental Design
- Exponential inapproximability of selecting a maximum volume sub-matrix
This page was built for publication: On selecting a maximum volume sub-matrix of a matrix and related problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1034598)
