Subset selection in sparse matrices
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Sparse Weighted Canonical Correlation Analysis
Given two data matrices $X$ and $Y$, sparse canonical correlation analysis (SCCA) is to seek two sparse canonical vectors $u$ and $v$ to maximize the correlation between $Xu$ and $Yv$. However, classical and sparse CCA m…
Grouped Variable Selection for Generalized Eigenvalue Problems
Many problems require the selection of a subset of variables from a full set of optimization variables. The computational complexity of an exhaustive search over all possible subsets of variables is, however, prohibitive…
Variable SelectionEfficient Distributed Estimation of Inverse Covariance Matrices
In distributed systems, communication is a major concern due to issues such as its vulnerability or efficiency. In this paper, we are interested in estimating sparse inverse covariance matrices when samples are distribut…
Model SelectionA Maximum Matching Algorithm for Basis Selection in Spectral Learning
We present a solution to scale spectral algorithms for learning sequence functions. We are interested in the case where these functions are sparse (that is, for most sequences they return 0). Spectral algorithms reduce t…
Conditional Uncorrelation and Efficient Non-approximate Subset Selection in Sparse Regression
Given $m$ $d$-dimensional responsors and $n$ $d$-dimensional predictors, sparse regression finds at most $k$ predictors for each responsor for linear approximation, $1\leq k \leq d-1$. The key problem in sparse regressio…
regression