Beyond Sub-Gaussian Measurements: High-Dimensional Structured Estimation with Sub-Exponential Designs
We consider the problem of high-dimensional structured estimation with norm-regularized estimators, such as Lasso, when the design matrix and noise are drawn from sub-exponential distributions.Existing results only consider sub-Gaussian designs and noise, and both the sample complexity and non-asymptotic estimation error have been shown to depend on the Gaussian width of suitable sets. In contrast, for the sub-exponential setting, we show that the sample complexity and the estimation error will depend on the exponential width of the corresponding sets, and the analysis holds for any norm. Further, using generic chaining, we show that the exponential width for any set will be at most $\sqrt{\log p}$ times the Gaussian width of the set, yielding Gaussian width based results even for the sub-exponential case. Further, for certain popular estimators, viz Lasso and Group Lasso, using a VC-dimension based analysis, we show that the sample complexity will in fact be the same order as Gaussian designs. Our general analysis and results are the first in the sub-exponential setting, and are readily applicable to special sub-exponential families such as log-concave and extreme-value distributions.
Code (0)
등록된 구현이 없습니다.
Tasks
Vocal Bursts Intensity PredictionSimilar Papers 제목 키워드 기반
Auto-encoders for compressed sensing
Compressed sensing is about recovering a structured high-dimensional signal ${\bf x}\in R^n$ from its under-determined noisy linear measurements ${\bf y}\in R^m$, where $m\ll n$. While the vast majority of the literatur…
compressed sensingProvable Phase Retrieval with Mirror Descent
In this paper, we consider the problem of phase retrieval, which consists of recovering an $n$-dimensional real vector from the magnitude of its $m$ linear measurements. We propose a mirror descent (or Bregman gradient d…
RetrievalOrthogonal Matching Pursuit with Noisy and Missing Data: Low and High Dimensional Results
Many models for sparse regression typically assume that the covariates are known completely, and without noise. Particularly in high-dimensional applications, this is often not the case. This paper develops efficient OMP…
regressionBeyond Independent Measurements: General Compressed Sensing with GNN Application
We consider the problem of recovering a structured signal $\mathbf{x} \in \mathbb{R}^{n}$ from noisy linear observations $\mathbf{y} =\mathbf{M} \mathbf{x}+\mathbf{w}$. The measurement matrix is modeled as $\mathbf{M} = …
compressed sensingBeyond trans-dimensional RJMCMC with a case study in impulsive data modeling
Reversible jump Markov chain Monte Carlo (RJMCMC) is a Bayesian model estimation method which has been used for trans-dimensional sampling. In this study, we propose utilization of RJMCMC beyond trans-dimensional samplin…