About this scholarly article

On Selecting a Maximum Volume Sub-matrix of a Matrix and Related Problems by Ali Çivril; Malik Magdon-Ismail is a scholarly article available to read on EtoBox.

Given a matrix A ∈ R m×n (n vectors in m dimensions), we consider the problem of selecting a subset of its columns such that its elements are as linearly independent as possible. This notion turned out to be important in low-rank approximations to 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 this paper, from a complexity theoretic point of view, we propose four related problems in which we try to find a ) is minimum, and (iv) the volume of the parallelepiped defined by the column vectors of C is maximum. We establish the NP-hardness of these problems and further show that they do not admit PTAS. We then study a natural Greedy heuristic for the maximum volume problem and show that it has approximation ratio 2 -O(k log k) . Our analysis of the Greedy heuristic is tight to within a logarithmic factor in the exponent, which we show by explicitly constructing an instance for which the Greedy heuristic is 2 -Ω(k) from optimal. When A has unit norm columns, a related problem is to select the maximum number of vectors with a given volume. We show that if the optimal solution sele

Author

Ali Çivril; Malik Magdon-Ismail

Publisher

Elsevier Science; Elsevier ; Elsevier BV (ISSN 0304-3975)

Published

2009

Language

EN