Column subset selection problem is UG-hard

DOI10.1016/J.JCSS.2014.01.004MaRDI QIDQ2637653zbMATH OpenOpenAlexFDO

Authors Ali Çivril

Publication date 13 February 2014

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2014.01.004

zbMATH Keywords

hardnessmatricessubset selectionunique games conjecture

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Column subset selection is NP-complete
• On selecting a maximum volume sub-matrix of a matrix and related problems
• An improved approximation algorithm for the column subset selection problem
• Column subset selection, matrix factorization, and eigenvalue optimization
• Faster subset selection for matrices and applications

Cites work

• A theory of pseudoskeleton approximations
• Adaptive Sampling and Fast Low-Rank Matrix Approximation
• Algorithm 853
• An improved approximation algorithm for the column subset selection problem
• Approximating unique games
• Approximation algorithms for unique games
• Bounds on singular values revealed by QR factorizations
• Column subset selection via sparse approximation of SVD
• Computing Truncated Singular Value Decomposition Least Squares Solutions by Rank Revealing QR-Factorizations
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• Exponential inapproximability of selecting a maximum volume sub-matrix
• Fast computation of low-rank matrix approximations
• Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
• Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition
• Fast monte-carlo algorithms for finding low-rank approximations
• Four algorithms for the the efficient computation of truncated pivoted QR approximations to a sparse matrix
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• scientific article; zbMATH DE number 1305418 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• scientific article; zbMATH DE number 7053310 (Why is no real title available?)
• Low‐rank revealing QR factorizations
• Near Optimal Column-Based Matrix Reconstruction
• Near-optimal algorithms for unique games
• On Rank-Revealing Factorisations
• On selecting a maximum volume sub-matrix of a matrix and related problems
• On the hardness of approximating Multicut and Sparsest-Cut
• On the Nyström method for approximating a gram matrix for improved kernel-based learning
• On the power of unique 2-prover 1-round games
• Optimal column-based low-rank matrix reconstruction
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Parameterized complexity and improved inapproximability for computing the largest \(j\)-simplex in a \(V\)-polytope
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Pseudo-skeleton approximations by matrices of maximal volume
• Random vectors in the isotropic position
• Rang revealing QR factorizations
• Rank-deficient nonlinear least squares problems and subset selection
• Rank-Revealing QR Factorizations and the Singular Value Decomposition
• Relative-Error CUR Matrix Decompositions
• Sampling from large matrices
• Sensor Selection via Convex Optimization
• Some Applications of the Rank Revealing QR Factorization
• Some optimal inapproximability results
• Subset selection for matrices
• Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods
• The maximal-volume concept in approximation by low-rank matrices

Cited in

(10)

• Optimal column subset selection for image classification by genetic algorithms
• Exponential inapproximability of selecting a maximum volume sub-matrix
• Clustering, multicollinearity, and singular vectors
• Regularized greedy column subset selection
• Column subset selection is NP-complete
• Perspectives on CUR decompositions
• Sparse approximation is provably hard under coherent dictionaries
• Estimating Leverage Scores via Rank Revealing Methods and Randomization
• Robust CUR Decomposition: Theory and Imaging Applications
• \texttt{pylspack}: parallel algorithms and data structures for sketching, column subset selection, regression, and leverage scores

Describes a project that uses

Uses Software

• Algorithm 853

This page was built for publication: Column subset selection problem is UG-hard

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