Column subset selection problem is UG-hard
From MaRDI portal
Publication:2637653
DOI10.1016/j.jcss.2014.01.004zbMath1285.68052OpenAlexW1982716240MaRDI QIDQ2637653
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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (8)
Optimal column subset selection for image classification by genetic algorithms ⋮ Clustering, multicollinearity, and singular vectors ⋮ Sparse approximation is provably hard under coherent dictionaries ⋮ Regularized greedy column subset selection ⋮ Column subset selection is NP-complete ⋮ Perspectives on CUR decompositions ⋮ Estimating Leverage Scores via Rank Revealing Methods and Randomization ⋮ Robust CUR Decomposition: Theory and Imaging Applications
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Rang revealing QR factorizations
- Column subset selection via sparse approximation of SVD
- Parameterized complexity and improved inapproximability for computing the largest \(j\)-simplex in a \(V\)-polytope
- Subset selection for matrices
- On selecting a maximum volume sub-matrix of a matrix and related problems
- Pseudo-skeleton approximations by matrices of maximal volume
- Random vectors in the isotropic position
- A theory of pseudoskeleton approximations
- Four algorithms for the the efficient computation of truncated pivoted QR approximations to a sparse matrix
- Exponential inapproximability of selecting a maximum volume sub-matrix
- Bounds on singular values revealed by QR factorizations
- On the hardness of approximating Multicut and Sparsest-Cut
- Near-optimal algorithms for unique games
- Rank-Deficient Nonlinear Least Squares Problems and Subset Selection
- Proof verification and the hardness of approximation problems
- Computing Truncated Singular Value Decomposition Least Squares Solutions by Rank Revealing QR-Factorizations
- Fast computation of low-rank matrix approximations
- Sampling from large matrices
- Algorithm 853
- On the power of unique 2-prover 1-round games
- Approximating unique games
- Adaptive Sampling and Fast Low-Rank Matrix Approximation
- Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods
- Relative-Error $CUR$ Matrix Decompositions
- Probabilistic checking of proofs
- Rank-Revealing QR Factorizations and the Singular Value Decomposition
- Some Applications of the Rank Revealing QR Factorization
- On Rank-Revealing Factorisations
- Low‐rank revealing QR factorizations
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Sensor Selection via Convex Optimization
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Fast monte-carlo algorithms for finding low-rank approximations
- Some optimal inapproximability results
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- 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
- Near Optimal Column-Based Matrix Reconstruction
- Optimal Column-Based Low-Rank Matrix Reconstruction
This page was built for publication: Column subset selection problem is UG-hard
