Subset selection in sparse matrices
From MaRDI portal
Abstract: In subset selection we search for the best linear predictor that involves a small subset of variables. From a computational complexity viewpoint, subset selection is NP-hard and few classes are known to be solvable in polynomial time. Using mainly tools from discrete geometry, we show that some sparsity conditions on the original data matrix allow us to solve the problem in polynomial time.
Recommendations
Cites work
- scientific article; zbMATH DE number 5485514 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 44282 (Why is no real title available?)
- scientific article; zbMATH DE number 1906319 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
- A polynomial case of the cardinality-constrained quadratic optimization problem
- A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs
- Algorithmic complexity: threeNP- hard problems in computational statistics
- An introduction to network flows over time
- Combinatorics of Compositions and Words
- Compressed sensing
- Constructing Arrangements of Lines and Hyperplanes with Applications
- Constructing maximal dynamic flows from static flows
- Covering a tree with rooted subtrees -- parameterized and approximation algorithms
- Integer Programming with a Fixed Number of Variables
- Least angle regression. (With discussion)
- On the Optimality of the Backward Greedy Algorithm for the Subset Selection Problem
- Regressions by Leaps and Bounds
- Restricted strong convexity implies weak submodularity
- Ridge Regression: Biased Estimation for Nonorthogonal Problems
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Stable signal recovery from incomplete and inaccurate measurements
- The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
- Understanding machine learning. From theory to algorithms
- \(N\)-fold integer programming
- \(n\)-fold integer programming in cubic time
Cited in
(16)- A Bidirectional Greedy Heuristic for the Subspace Selection Problem
- Cardinality minimization, constraints, and regularization: a survey
- scientific article; zbMATH DE number 6982912 (Why is no real title available?)
- Determinant and Exchange Algorithms for Observation Subset Selection
- A graph-based decomposition method for convex quadratic optimization with indicators
- Finding nonoverlapping substructures of a sparse matrix
- Column subset selection is NP-complete
- Selection procedures for sparse data
- Graph structured sparse subset selection
- Subset selection for matrices
- Sparse approximation over the cube
- Connection between the selection problem for a sparse submatrix of a large-size matrix and the Bayesian problem of hypotheses testing
- Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix
- Some recent results in model selection
- Faster subset selection for matrices and applications
- A polynomial algorithm for best-subset selection problem
This page was built for publication: Subset selection in sparse matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4961001)
