On selecting a maximum volume sub-matrix of a matrix and related problems. (English) Zbl 1181.15002

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.


15A03 Vector spaces, linear dependence, rank, lineability
15A12 Conditioning of matrices
Full Text: DOI


[1] Businger, P.A.; Golub, G.H., Linear least squares solutions by Householder transformations, Numerische Mathematik, 7, 269-276, (1965) · Zbl 0142.11503
[2] Chandrasekaran, S.; Ipsen, I.C.F., On rank-revealing factorizations, SIAM journal of matrix analysis and its applications, 15, 592-622, (1994) · Zbl 0796.65030
[3] Chan, T.F., Rank revealing QR factorizations, Linear algebra appl., 88/89, 67-82, (1987) · Zbl 0624.65025
[4] Deshpande, A.; Rademacher, L.; Vempala, S.; Wang, G., Matrix approximation and projective clustering via volume sampling, (), 1117-1126 · Zbl 1192.68889
[5] Deshpande, A.; Vempala, S., Adaptive sampling and fast low-rank matrix approximation, (), 292-303 · Zbl 1155.68575
[6] de Hoog, F.R.; Mattheijb, R.M.M., Subset selection for matrices, Linear algebra and its applications, 422, 349-359, (2007) · Zbl 1158.15017
[7] Drineas, P.; Kannan, R.; Mahoney, M.W., Fast Monte Carlo algorithms for matrices III: computing a compressed approximate matrix decomposition, SIAM journal on computing, 36, 1, 184-206, (2006) · Zbl 1111.68149
[8] Drineas, P.; Kannan, R.; Mahoney, M.W., Fast Monte Carlo algorithms for matrices II: computing a low-rank approximation to a matrix, SIAM journal on computing, 36, 1, 158-183, (2006) · Zbl 1111.68148
[9] Frieze, A.; Kannan, R.; Vempala, S., Fast Monte-Carlo algorithms for finding low-rank approximations, Journal of the association for computing machinery, 51, 6, 1025-1041, (2004) · Zbl 1125.65005
[10] Garey, M.R.; Johnson, D.S., Computers and intractability, (1979), W. H. Freeman · Zbl 0411.68039
[11] G.H. Golub, V. Klema, G.W. Stewart, Rank degeneracy and least squares problems, Dept. of Computer Science, Univ. of Maryland, 1976
[12] Golub, G.H.; Loan, C.V., Matrix computations, (1996), Johns Hopkins U. Press
[13] Goreinov, S.A.; Tyrtyshnikov, E.E., (), 47-51
[14] Gu, M.; Eisenstat, S.C., Efficient algorithms for computing a strong rank-revealing QR factorization, SIAM journal on scientific computing, 17, 4, 848-869, (1996) · Zbl 0858.65044
[15] Hong, Y.P.; Pan, C.T., Rank-revealing QR factorizations and the singular value decomposition, Mathematics of computation, 58, 213-232, (1992) · Zbl 0743.65037
[16] Kahan, W., Numerical linear algebra, vol. 9, (1966), pp. 757-801 · Zbl 0236.65025
[17] Karp, R.M., Reducibility among combinatorial problems, (), 85-103 · Zbl 0366.68041
[18] Lenstra, A.K.; Lenstra, H.W.; Lovasz, L., Factoring polynomials with rational coefficients, Mathematische annalen, 261, 515-534, (1982) · Zbl 0488.12001
[19] Pan, C.T.; Tang, P.T.P., Bounds on singular values revealed by QR factorizations, BIT numerical mathematics, 39, 740-756, (1999) · Zbl 0944.65042
[20] Pan, C.T., On the existence and computation of rank-revealing \(L U\) factorizations, Linear algebra and its applications, 316, 1-3, 199-222, (2000) · Zbl 0962.65023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.