On selecting a maximum volume sub-matrix of a matrix and related problems
type: Item
instance of: scholarly article
title: On selecting a maximum volume sub-matrix of a matrix and related problems
zbMATH Open document ID: 1181.15002
author: Ali Çivril
author: Malik Magdon-Ismail
published in: Theoretical Computer Science
publication date: 2009-11-06T00:00:00Z
review text: Given a real \(m\times n\) matrix, the authors consider the problem of selecting a subset of its columns such that its elements are as linearly independent as possible. The notion is important in low-rank approximations of matrices and rank revealing QR factorizations which have been investigated in the linear algebra community and can be quantified in a few different ways. In the present paper, from a complexity theoretic point of view, the authors propose four related problems. They establish the NP-hardness of these problems and they further show that they do not admit PTAS.
Mathematics Subject Classification ID: 15A03
Mathematics Subject Classification ID: 15A12
zbMATH DE Number: 5626951
zbMATH Keywords: subset selection
zbMATH Keywords: condition number
zbMATH Keywords: maximum volume sub-matrix
zbMATH Keywords: complexity
zbMATH Keywords: low-rank approximations
zbMATH Keywords: QR factorizations
zbMATH Keywords: NP-hardness
reviewed by: Andreas Arvanitoyeorgos
MaRDI profile type: Publication
full work available at URL: j.tcs.2009.06.018
OpenAlex ID: W2076410399
cites work: Handbook series linear algebra. Linear least squares solutions by Householder transformations
cites work: On Rank-Revealing Factorisations
cites work: Rang revealing QR factorizations
cites work: Matrix approximation and projective clustering via volume sampling
cites work: Adaptive Sampling and Fast Low-Rank Matrix Approximation
cites work: Subset selection for matrices
cites work: Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition
cites work: Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
cites work: Fast monte-carlo algorithms for finding low-rank approximations
cites work: Q4198056
cites work: Q5689624
cites work: The maximal-volume concept in approximation by low-rank matrices
cites work: Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
cites work: Rank-Revealing QR Factorizations and the Singular Value Decomposition
cites work: Numerical Linear Algebra
cites work: Q4142699
cites work: Factoring polynomials with rational coefficients
cites work: Bounds on singular values revealed by QR factorizations
cites work: On the existence and computation of rank-revealing LU factorizations
DOI: 10.1016/J.TCS.2009.06.018
Recommended article: Exponential inapproximability of selecting a maximum volume sub-matrix
Recommended article: Rectangular maximum-volume submatrices and their applications
Recommended article: Submatrix Maximum Queries in Monge Matrices and Partial Monge Matrices, and Their Applications
Recommended article: Q5743404
Recommended article: On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices
Recommended article: Subspace Selection for Projection Maximization With Matroid Constraints
Recommended article: A note on subset selection for matrices
Recommended article: The maximal-volume concept in approximation by low-rank matrices
Recommended article: Improved Submatrix Maximum Queries in Monge Matrices
Recommended article: Q3115704
description: scientific article; zbMATH DE number 5626951