Column subset selection is NP-complete

DOI10.1016/J.LAA.2020.09.015zbMATH Open1456.68056arXiv1701.02764OpenAlexW3088364660MaRDI QIDQ2228097FDOQ2228097

Ya. N. Shitov

Publication date: 16 February 2021

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: Let $M$ be a real $rimesc$ matrix and let $k$ be a positive integer. In the column subset selection problem (CSSP), we need to minimize the quantity $|M-SA|$, where $A$ can be an arbitrary $kimesc$ matrix, and $S$ runs over all $rimesk$ submatrices of $M$. This problem and its applications in numerical linear algebra are being discussed for several decades, but its algorithmic complexity remained an open issue. We show that CSSP is NP-complete.

Full work available at URL: https://arxiv.org/abs/1701.02764

Recommendations

• Column subset selection problem is UG-hard
• On selecting a maximum volume sub-matrix of a matrix and related problems
• Subset selection in sparse matrices
• NP-completeness of some problems of a vectors subset choice
• Exponential inapproximability of selecting a maximum volume sub-matrix

zbMATH Keywords

NP-completenesscolumn subset selection

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Numerical linear algebra (65F99) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Literature survey on low rank approximation of matrices
• Reducibility among Combinatorial Problems
• Sensor Selection via Convex Optimization
• A Recurring Theorem on Determinants
• On the power of unique 2-prover 1-round games
• On selecting a maximum volume sub-matrix of a matrix and related problems
• Some Applications of the Rank Revealing QR Factorization
• Column subset selection problem is UG-hard
• Subset selection for matrices
• Title not available (Why is that?)
• Rank-Deficient Nonlinear Least Squares Problems and Subset Selection
• Bounds on singular values revealed by QR factorizations
• Optimal column subset selection for image classification by genetic algorithms
• Algorithm 853
• Near Optimal Column-Based Matrix Reconstruction

Cited In (10)

• On the thinness of trees
• Estimating Leverage Scores via Rank Revealing Methods and Randomization
• A non-intrusive multifidelity method for the reduced order modeling of nonlinear problems
• Allocation Strategies for High Fidelity Models in the Multifidelity Regime
• Robust CUR Decomposition: Theory and Imaging Applications
• \texttt{pylspack}: parallel algorithms and data structures for sketching, column subset selection, regression, and leverage scores
• Clustering, multicollinearity, and singular vectors
• Smoothed separable nonnegative matrix factorization
• A literature survey of matrix methods for data science
• Adaptive symplectic model order reduction of parametric particle-based Vlasov–Poisson equation

Uses Software

• Algorithm 853

This page was built for publication: Column subset selection is NP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2228097)