Performing statistical inference in high-dimension is an outstanding challenge. A major source of difficulty is the absence of precise information on the distribution of high-dimensional estimators. Here, we consider linear regression in the high-dimensional regime @math . In this context, we would like to perform inference on a high-dimensional parameters vector @math . Important progress has been achieved in computing confidence intervals for single coordinates @math . A key role in these new methods is played by a certain debiased estimator @math that is constructed from the Lasso. Earlier work establishes that, under suitable assumptions on the design matrix, the coordinates of @math are asymptotically Gaussian provided @math is @math -sparse with @math . The condition @math is stronger than the one for consistent estimation, namely @math . We study Gaussian designs with known or unknown population covariance. When the covariance is known, we prove that the debiased estimator is asymptotically Gaussian under the nearly optimal condition @math . Note that earlier work was limited to @math even for perfectly known covariance. The same conclusion holds if the population covariance is unknown but can be estimated sufficiently well, e.g. under the same sparsity conditions on the inverse covariance as assumed by earlier work. For intermediate regimes, we describe the trade-off between sparsity in the coefficients and in the inverse covariance of the design. We further discuss several applications of our results to high-dimensional inference. In particular, we propose a new estimator that is minimax optimal up to a factor @math for i.i.d. Gaussian designs.
A non-asymptotic result under weaker sparsity conditions, and for designs with dependent columns, was proved in @cite_22 . However, this only establishes gaussianity of @math for most of the coordinates @math . Here we prove a significantly stronger result holding uniformly over @math .
@cite_22
2764111657 2536849891 2034070643 2953076353
In this paper we consider memoryless one-bit compressed sensing with randomly subsampled Gaussian circulant matrices. We show that in a small sparsity regime and for small enough accuracy @math , @math measurements suffice to reconstruct the direction of any @math -sparse vector up to accuracy @math via an efficient program. We derive this result by proving that partial Gaussian circulant matrices satisfy an @math RIP-property. Under a slightly worse dependence on @math , we establish stability with respect to approximate sparsity, as well as full vector recovery results. We study the recovery of sparse vectors from subsampled random convolutions via @math -minimization. We consider the setup in which both the subsampling locations as well as the generating vector are chosen at random. For a subgaussian generator with independent entries, we improve previously known estimates: if the sparsity @math is small enough, i.e., @math , we show that @math measurements are sufficient to recover @math -sparse vectors in dimension @math with high probability, matching the well-known condition for recovery from standard Gaussian measurements. If @math is larger, then essentially @math measurements are sufficient, again improving over previous estimates. Our results are shown via the so-called robust null space property which is weaker than the standard restricted isometry property. Our method of proof involves a novel combination of small ball estimates with chaining techniques which should be of independent interest. We give an elementary proof of a generalization of Bourgain and Tzafriri’s Restricted Invertibility Theorem, which says roughly that any matrix with columns of unit length and bounded operator norm has a large coordinate subspace on which it is well-invertible. Our proof gives the tightest known form of this result, is constructive, and provides a deterministic polynomial time algorithm for finding the desired subspace. This paper provides novel results for the recovery of signals from undersampled measurements based on analysis @math -minimization, when the analysis operator is given by a frame. We both provide so-called uniform and nonuniform recovery guarantees for cosparse (analysis-sparse) signals using Gaussian random measurement matrices. The nonuniform result relies on a recovery condition via tangent cones and the uniform recovery guarantee is based on an analysis version of the null space property. Examining these conditions for Gaussian random matrices leads to precise bounds on the number of measurements required for successful recovery. In the special case of standard sparsity, our result improves a bound due to Rudelson and Vershynin concerning the exact reconstruction of sparse signals from Gaussian measurements with respect to the constant and extends it to stability under passing to approximately sparse signals and to robustness under noise on the measurements.