Abstract | ||
---|---|---|
The restricted eigenvalue (RE) condition characterizes the sample complexity of accurate recovery in the context of high-dimensional estimators such as Lasso and Dantzig selector (Bickel et al., 2009). Recent work has shown that random design matrices drawn from any thin-tailed (sub-Gaussian) distributions satisfy the RE condition with high probability, when the number of samples scale as the square of the Gaussian width of the restricted set (Banerjee et al., 2014; Tropp, 2015). We pose the equivalent question for heavy-tailed distributions: Given a random design matrix drawn from a heavy-tailed distribution satisfying the smallball property (Mendelson, 2015), does the design matrix satisfy the RE condition with the same order of sample complexity as sub-Gaussian distributions? An answer to the question will guide the design of highdimensional estimators for heavy tailed problems. |
Year | Venue | Field |
---|---|---|
2015 | COLT | Mathematical optimization,Open problem,Matrix (mathematics),Lasso (statistics),Gaussian,Design matrix,Sample complexity,Eigenvalues and eigenvectors,Mathematics,Estimator |
DocType | Volume | Issue |
Conference | 40 | 2015 |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Arindam Banerjee | 1 | 31 | 3.77 |
Sheng Chen | 2 | 56 | 11.04 |
Vidyashankar Sivakumar | 3 | 6 | 1.58 |