This paper develops a general theoretical framework to analyze structured
sparse recovery problems using the notation of dual certificate. Although
certain aspects of the dual certificate idea have already been used in some
previous work, due to the lack of a general and coherent theory, the analysis
has so far only been carried out in limited scopes for specific problems. In
this context the current paper makes two contributions. First, we introduce a
general definition of dual certificate, which we then use to develop a unified
theory of sparse recovery analysis for convex programming.

The purpose of this paper is to propose methodologies for statistical
inference of low-dimensional parameters with high-dimensional data. We focus on
constructing confidence intervals for individual coefficients and linear
combinations of several of them in a linear regression model, although our
ideas are applicable in a much broad context. The theoretical results presented
here provide sufficient conditions for the asymptotic normality of the proposed
estimators along with a consistent estimator for their finite-dimensional
covariance matrices.

Scaled sparse linear regression jointly estimates the regression coefficients
and noise level in a linear model. It chooses an equilibrium with a sparse
regression method by iteratively estimating the noise level via the mean
residual squares and scaling the penalty in proportion to the estimated noise
level.

We propose MC+, a fast, continuous, nearly unbiased and accurate method of
penalized variable selection in high-dimensional linear regression. The LASSO
is fast and continuous, but biased. The bias of the LASSO may prevent
consistent variable selection. Subset selection is unbiased but computationally
costly. The MC+ has two elements: a minimax concave penalty (MCP) and a
penalized linear unbiased selection (PLUS) algorithm. The MCP provides the
convexity of the penalized loss in sparse regions to the greatest extent given
certain thresholds for variable selection and unbiasedness.