Column subset selection is NP-complete
From MaRDI portal
Publication:2228097
DOI10.1016/j.laa.2020.09.015zbMath1456.68056arXiv1701.02764OpenAlexW3088364660MaRDI QIDQ2228097
Publication date: 16 February 2021
Published in: Linear Algebra and its Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1701.02764
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Numerical linear algebra (65F99)
Related Items (9)
Clustering, multicollinearity, and singular vectors ⋮ A non-intrusive multifidelity method for the reduced order modeling of nonlinear problems ⋮ A literature survey of matrix methods for data science ⋮ On the thinness of trees ⋮ Smoothed separable nonnegative matrix factorization ⋮ Adaptive symplectic model order reduction of parametric particle-based Vlasov–Poisson equation ⋮ Allocation Strategies for High Fidelity Models in the Multifidelity Regime ⋮ Estimating Leverage Scores via Rank Revealing Methods and Randomization ⋮ Robust CUR Decomposition: Theory and Imaging Applications
Uses Software
Cites Work
- Unnamed Item
- Subset selection for matrices
- On selecting a maximum volume sub-matrix of a matrix and related problems
- Optimal column subset selection for image classification by genetic algorithms
- Bounds on singular values revealed by QR factorizations
- Column subset selection problem is UG-hard
- Rank-Deficient Nonlinear Least Squares Problems and Subset Selection
- Algorithm 853
- On the power of unique 2-prover 1-round games
- Some Applications of the Rank Revealing QR Factorization
- Sensor Selection via Convex Optimization
- Literature survey on low rank approximation of matrices
- Reducibility among Combinatorial Problems
- Near Optimal Column-Based Matrix Reconstruction
- A Recurring Theorem on Determinants
This page was built for publication: Column subset selection is NP-complete
