Column subset selection problem is UG-hard (Q2637653): Difference between revisions

@@ Property / cites work @@
+Fast computation of low-rank matrix approximations
+Normal rank
@@ Property / cites work @@
+Proof verification and the hardness of approximation problems
+Normal rank
@@ Property / cites work @@
+Probabilistic checking of proofs
@@ Property / cites work: Probabilistic checking of proofs / rank @@
+Normal rank
@@ Property / cites work @@
+Free Bits, PCPs, and Nonapproximability---Towards Tight Results
+Normal rank
@@ Property / cites work @@
+Near Optimal Column-Based Matrix Reconstruction
@@ Property / cites work: Near Optimal Column-Based Matrix Reconstruction / rank @@
+Normal rank
@@ Property / cites work @@
+Q4633910
@@ Property / cites work: Q4633910 / rank @@
+Normal rank
@@ Property / cites work @@
+Rang revealing QR factorizations
@@ Property / cites work: Rang revealing QR factorizations / rank @@
+Normal rank
@@ Property / cites work @@
+Low‐rank revealing QR factorizations
@@ Property / cites work: Low‐rank revealing QR factorizations / rank @@
+Normal rank
@@ Property / cites work @@
+Computing Truncated Singular Value Decomposition Least Squares Solutions by Rank Revealing QR-Factorizations
+Normal rank
@@ Property / cites work @@
+Some Applications of the Rank Revealing QR Factorization
+Normal rank
@@ Property / cites work @@
+On Rank-Revealing Factorisations
@@ Property / cites work: On Rank-Revealing Factorisations / rank @@
+Normal rank
@@ Property / cites work @@
+Near-optimal algorithms for unique games
@@ Property / cites work: Near-optimal algorithms for unique games / rank @@
+Normal rank
@@ Property / cites work @@
+On the hardness of approximating Multicut and Sparsest-Cut
+Normal rank
@@ Property / cites work @@
+Exponential inapproximability of selecting a maximum volume sub-matrix
+Normal rank
@@ Property / cites work @@
+On selecting a maximum volume sub-matrix of a matrix and related problems
+Normal rank
@@ Property / cites work @@
+Column subset selection via sparse approximation of SVD
+Normal rank
@@ Property / cites work @@
+Subset selection for matrices
@@ Property / cites work: Subset selection for matrices / rank @@
+Normal rank
@@ Property / cites work @@
+Adaptive Sampling and Fast Low-Rank Matrix Approximation
+Normal rank
@@ Property / cites work @@
+Q4252300
@@ Property / cites work: Q4252300 / rank @@
+Normal rank
@@ Property / cites work @@
+Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
+Normal rank
@@ Property / cites work @@
+Q3093333
@@ Property / cites work: Q3093333 / rank @@
+Normal rank
@@ Property / cites work @@
+Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods
+Normal rank
@@ Property / cites work @@
+Relative-Error $CUR$ Matrix Decompositions
@@ Property / cites work: Relative-Error $CUR$ Matrix Decompositions / rank @@
+Normal rank
@@ Property / cites work @@
+Algorithm 853
@@ Property / cites work: Algorithm 853 / rank @@
+Normal rank
@@ Property / cites work @@
+Fast monte-carlo algorithms for finding low-rank approximations
+Normal rank
@@ Property / cites work @@
+Q5689624
@@ Property / cites work: Q5689624 / rank @@
+Normal rank
@@ Property / cites work @@
+A theory of pseudoskeleton approximations
@@ Property / cites work: A theory of pseudoskeleton approximations / rank @@
+Normal rank
@@ Property / cites work @@
+Q2784645
@@ Property / cites work: Q2784645 / rank @@
+Normal rank
@@ Property / cites work @@
+Pseudo-skeleton approximations by matrices of maximal volume
+Normal rank
@@ Property / cites work @@
+Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
+Normal rank
@@ Property / cites work @@
+Approximating unique games
@@ Property / cites work: Approximating unique games / rank @@
+Normal rank
@@ Property / cites work @@
+Q5743431
@@ Property / cites work: Q5743431 / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal Column-Based Low-Rank Matrix Reconstruction
+Normal rank
@@ Property / cites work @@
+Some optimal inapproximability results
@@ Property / cites work: Some optimal inapproximability results / rank @@
+Normal rank
@@ Property / cites work @@
+Rank-Revealing QR Factorizations and the Singular Value Decomposition
+Normal rank
@@ Property / cites work @@
+Rank-Deficient Nonlinear Least Squares Problems and Subset Selection
+Normal rank
@@ Property / cites work @@
+Sensor Selection via Convex Optimization
@@ Property / cites work: Sensor Selection via Convex Optimization / rank @@
+Normal rank
@@ Property / cites work @@
+On the power of unique 2-prover 1-round games
@@ Property / cites work: On the power of unique 2-prover 1-round games / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
+Normal rank
@@ Property / cites work @@
+Parameterized complexity and improved inapproximability for computing the largest \(j\)-simplex in a \(V\)-polytope
+Normal rank
@@ Property / cites work @@
+Bounds on singular values revealed by QR factorizations
+Normal rank
@@ Property / cites work @@
+Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate  Matrix Decomposition
+Normal rank
@@ Property / cites work @@
+Random vectors in the isotropic position
@@ Property / cites work: Random vectors in the isotropic position / rank @@
+Normal rank
@@ Property / cites work @@
+Sampling from large matrices
@@ Property / cites work: Sampling from large matrices / rank @@
+Normal rank
@@ Property / cites work @@
+Four algorithms for the the efficient computation of truncated pivoted QR approximations to a sparse matrix
+Normal rank
@@ Property / cites work @@
+Q3002794
@@ Property / cites work: Q3002794 / rank @@
+Normal rank