Timezone: »
Poster
Multi-Stage Dantzig Selector
Ji Liu · Peter Wonka · Jieping Ye
We consider the following sparse signal recovery (or feature selection) problem: given a design matrix $X\in \mathbb{R}^{n\times m}$ $(m\gg n)$ and a noisy observation vector $y\in \mathbb{R}^{n}$ satisfying $y=X\beta^*+\epsilon$ where $\epsilon$ is the noise vector following a Gaussian distribution $N(0,\sigma^2I)$, how to recover the signal (or parameter vector) $\beta^*$ when the signal
is sparse?
The Dantzig selector has been proposed for sparse signal recovery with strong theoretical guarantees. In this paper, we propose a multi-stage Dantzig selector method, which iteratively refines the target signal $\beta^*$. We show that if $X$ obeys a certain condition, then with a large probability the difference between the solution $\hat\beta$ estimated by the proposed method and the true
solution $\beta^*$ measured in terms of the $l_p$ norm ($p\geq 1$) is bounded as \begin{equation*} \|\hat\beta-\beta^*\|_p\leq \left(C(s-N)^{1/p}\sqrt{\log m}+\Delta\right)\sigma, \end{equation*} $C$ is a constant, $s$ is the number of nonzero entries in $\beta^*$, $\Delta$ is independent of $m$ and is much smaller than the first term, and $N$ is the number of entries of $\beta^*$ larger
than a certain value in the order of $\mathcal{O}(\sigma\sqrt{\log m})$. The proposed method improves the estimation bound of the standard Dantzig selector approximately from $Cs^{1/p}\sqrt{\log m}\sigma$ to $C(s-N)^{1/p}\sqrt{\log m}\sigma$ where the value $N$
depends on the number of large entries in $\beta^*$. When $N=s$, the proposed algorithm achieves the oracle solution with a high probability. In addition, with a large probability, the proposed method can select the same number of correct features under a milder condition than the Dantzig selector.
Author Information
Ji Liu (University Wisconsin-Madison)
Peter Wonka (KAUST)
Jieping Ye (Arizona State University)
More from the Same Authors
-
2021 Poster: SketchGen: Generating Constrained CAD Sketches »
Wamiq Para · Shariq Bhat · Paul Guerrero · Tom Kelly · Niloy Mitra · Leonidas Guibas · Peter Wonka -
2014 Poster: Two-Layer Feature Reduction for Sparse-Group Lasso via Decomposition of Convex Sets »
Jie Wang · Jieping Ye -
2014 Spotlight: Two-Layer Feature Reduction for Sparse-Group Lasso via Decomposition of Convex Sets »
Jie Wang · Jieping Ye -
2014 Poster: A Safe Screening Rule for Sparse Logistic Regression »
Jie Wang · Jiayu Zhou · Jun Liu · Peter Wonka · Jieping Ye -
2013 Poster: Lasso Screening Rules via Dual Polytope Projection »
Jie Wang · Jiayu Zhou · Peter Wonka · Jieping Ye -
2013 Spotlight: Lasso Screening Rules via Dual Polytope Projection »
Jie Wang · Jiayu Zhou · Peter Wonka · Jieping Ye -
2012 Poster: Multi-Stage Multi-Task Feature Learning »
Pinghua Gong · Jieping Ye · Changshui Zhang -
2012 Poster: Multi-task Vector Field Learning »
Binbin Lin · Sen Yang · Chiyuan Zhang · Jieping Ye · Xiaofei He -
2012 Poster: Regularized Off-Policy TD-Learning »
Bo Liu · Sridhar Mahadevan · Ji Liu -
2012 Spotlight: Multi-Stage Multi-Task Feature Learning »
Pinghua Gong · Jieping Ye · Changshui Zhang -
2012 Spotlight: Regularized Off-Policy TD-Learning »
Bo Liu · Sridhar Mahadevan · Ji Liu -
2012 Poster: Generalization Bounds for Domain Adaptation »
Chao Zhang · Jieping Ye · Lei Zhang -
2011 Poster: Clustered Multi-Task Learning Via Alternating Structure Optimization »
Jiayu Zhou · Jianhui Chen · Jieping Ye -
2011 Poster: Efficient Methods for Overlapping Group Lasso »
Lei Yuan · Jun Liu · Jieping Ye -
2011 Poster: Projection onto A Nonnegative Max-Heap »
Jun Liu · Liang Sun · Jieping Ye -
2011 Spotlight: Projection onto A Nonnegative Max-Heap »
Jun Liu · Liang Sun · Jieping Ye -
2011 Poster: A Two-Stage Weighting Framework for Multi-Source Domain Adaptation »
Qian Sun · Rita Chattopadhyay · Sethuraman Panchanathan · Jieping Ye -
2011 Poster: Identifying Alzheimer's Disease-Related Brain Regions from Multi-Modality Neuroimaging Data using Sparse Composite Linear Discrimination Analysis »
Shuai Huang · Jing Li · Jieping Ye · Teresa Wu · Kewei Chen · Adam Fleisher · Eric Reiman -
2011 Spotlight: Identifying Alzheimer's Disease-Related Brain Regions from Multi-Modality Neuroimaging Data using Sparse Composite Linear Discrimination Analysis »
Shuai Huang · Jing Li · Jieping Ye · Teresa Wu · Kewei Chen · Adam Fleisher · Eric Reiman -
2010 Poster: Moreau-Yosida Regularization for Grouped Tree Structure Learning »
Jun Liu · Jieping Ye -
2009 Poster: Learning Brain Connectivity of Alzheimer's Disease from Neuroimaging Data »
Shuai Huang · Jing Li · Liang Sun · Jun Liu · Teresa Wu · Kewei Chen · Adam Fleisher · Eric Reiman · Jieping Ye -
2009 Spotlight: Learning Brain Connectivity of Alzheimer's Disease from Neuroimaging Data »
Shuai Huang · Jing Li · Liang Sun · Jun Liu · Teresa Wu · Kewei Chen · Adam Fleisher · Eric Reiman · Jieping Ye -
2009 Poster: Efficient Recovery of Jointly Sparse Vectors »
Liang Sun · Jun Liu · Jianhui Chen · Jieping Ye -
2008 Poster: Multi-label Multiple Kernel Learning »
Shuiwang Ji · Liang Sun · Rong Jin · Jieping Ye -
2008 Spotlight: Multi-label Multiple Kernel Learning »
Shuiwang Ji · Liang Sun · Rong Jin · Jieping Ye -
2007 Poster: Discriminative K-means for Clustering »
Jieping Ye · Zheng Zhao · Mingrui Wu