Mathematics – Statistics Theory
Scientific paper
2010-10-12
Mathematics
Statistics Theory
15 pages, 2 figures (revised version with some additional comments)
Scientific paper
This article investigates deterministic design matrices $X$ for the fundamental problems of error prediction and variable selection given observations $y=X \beta^\star+z$ where $z$ is a stochastic error term. In this paper, deterministic design matrices are derived from unbalanced expander graphs, and we show that it is possible to accurately estimate the prediction $X\beta^\star$ and the target vector $\beta^\star$ using computationally tractable algorithms. Using a result of Berinde, Gilbert, Indyk, Karloff and Strauss, we show that for any adjacency matrix of an unbalanced expander graph and any target vector $\beta^\star$, the lasso ($\ell_1$-penalized least squares) and the Dantzig selector ($\ell_\infty$-penalized basis pursuit) satisfy oracle inequalities in error prediction and variable selection involving the $s$ largest (in magnitude) coefficients of $\beta^\star$, i.e. upper bounds in term of the best sparse approximation. Using recent results on Parvaresh-Vardy codes, we present a construction of deterministic designs. Furthermore, we prove that these designs are almost optimal. Indeed, they provide error prediction and variable selection with an accuracy which is the best, up to an explicit factor, one could expect knowing the support of the target $\beta^\star$.
No associations
LandOfFree
Error Prediction and Variable Selection via Unbalanced Expander Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Error Prediction and Variable Selection via Unbalanced Expander Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Error Prediction and Variable Selection via Unbalanced Expander Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-608895