Restricted Eigenvalue Properties for Correlated Gaussian Designs

By Garvesh Raskutti, Martin J. Wainwright, Bin Yu. Journal of machine learning research, 2010

530 citations recorded by the source corpus.

Subfields: Computational Mechanics, Computer Networks and Communications, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/ece5045d0f495834b25d2188735bcee982edd8c2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Networks and Communications

In Statistics and Probability

Citations in the corpus

Group bound: confidence intervals for groups of variables in sparse high dimensional regression without assumptions on the design (2013, methodology): “Note that φ2cc.1/>0 is also sometimes called the null space condition that is used to show equivalence of the l1- and l0-sparsest solutions to the regression problem; see for example Raskutti et al. (2010) and references therein.”
Communication-efficient sparse regression: a one-shot approach (2015, background): “When the rows of X are i.i.d. Gaussian random vectors with mean zero and covariance Σ , Raskutti, Wainwright and Yu (2010) show there are constants µ 1 , µ 2 > 0 such that Their result implies the RE condition for any S ⊂ [ p ] with constant µ 1 2 as long as n > 32 µ 2 µ 1 | S | log p.”
Robust Lasso With Missing and Grossly Corrupted Observations (2011, background): “This bound, which is stated below, has been established in equation (42) of [8]: there exists some numerical constant c such that P ( T1 ≥ 20 √ σ2 log k Cmin(n− s) ) ≤ 4 exp(−c(n− s)).”
Event-Triggered State Observers for Sparse Sensor Noise/Attacks (2013, unknown): “3, in this section we discuss a more quantitative version termed the s-restricted eigenvalue property [20].”
STRONG ORACLE OPTIMALITY OF FOLDED CONCAVE PENALIZED ESTIMATION (2012, background): “ke the following restricted eigenvalue condition, (C1) κLS = min u6=0: kuAckℓ 1 ≤3kuAkℓ 1 √kXukℓ2 nkukℓ2 ∈ (0,∞). Such acondition hasbeenstudied inBickel et al.(2009);Van De Geer and Bu¨hlmann(2009); Raskutti et al. (2010) and Negahban et al. (2012). Under the sub-Gaussian noise assumption (A1) and ”
On Bayes Risk Lower Bounds (2014, background): “It is worth noting that the lower bounds of Raskutti et al. (2011) were proved by constructing a uniform prior over a discrete packing set over the parameter space.”
Communication-Efficient Distributed Statistical Inference (2016, background): “For this class of design, it is known that Assumption HA is satisfied with high probability as long as (cid:11) is strictly positive definite and n ≥ C 0 s log d for some constant C 0 > 0 depending on the minimal eigenvalue of (cid:11) (Raskutti, Wainwright, and Yu 2010).”
Lower bounds on the performance of polynomial-time algorithms for sparse linear regression (2014, unknown): “[17].”
Maximin effects in inhomogeneous large-scale data (2014, unknown): “2, we have an additional term in the bound that is proportional to Dtimes the squared ‘ 1-norm of b maximinand b g, g= 1;:::;G. A more careful analysis for the special case of Gaussian random design [Raskutti et al., 2010] could render the bound again linear in , with more general design treated in ”
A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers (2009, background): “[55, 56], who showed that if the design matrix X ∈ Rn×p is formed by independently sampling each row Xi ∼ N(0, ), referred to as the -Gaussian ensemble, then there are strictly positive constants (κ1, κ2), depending only on the positive definite matrix , such that”
Hypothesis Testing in High-Dimensional Regression Under the Gaussian Random Design Model: Asymptotic Theory (2013, unknown): “They considered the asymptotic behavior as s 0 , p, n → ∞ with s 0 /p → ε ∈ (0 , 1) and n/p → δ ∈ (0 , 1).”
On asymptotically optimal confidence regions and tests for high-dimensional models (2013, methodology): “In the sub-Gaussian case, we use that √ sj log(p)/n = o(1) and an extension of Theorem 1 in [39] from the Gaussian case to the sub-Gaussian case.”
On the uniform convergence of empirical norms and inner products, with application to causal inference (2013, methodology): “We refer to [1] and with sub-Gaussian random vectors to [24, 16] and [26].”
Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization (2013, background): “It is possible to further weaken this assumption to a restricted eigenvalue (RE) condition which is often used in the sparse regression literature as well [28, 23].”
Two-Step Lasso Estimation of the Spatial Weights Matrix (2015, background): “The restricted eigenvalue conditions hold under general conditions; see, e.g., [27,31,47].”
Statistical significance in high-dimensional linear models (2012, background): “…minimum, typically over a cone. to This leads the concept of restricted eigenvalues (Bickel, Ritov and Tsybakov 2009; Koltchinskii 2009a, 2009b; Raskutti, Wainwright and Yu 2010) or weaker forms such as the compatibility constants (van de Geer, 2007) or further slight weakening of the latter…”