High-dimensional statistics

In statistical theory, the field of high-dimensional statistics studies data whose dimension is larger (relative to the number of datapoints) than typically considered in classical multivariate analysis. The area arose owing to the emergence of many modern data sets in which the dimension of the data vectors may be comparable to, or even larger than, the sample size, so that justification for the use of traditional techniques, often based on asymptotic arguments with the dimension held fixed as the sample size increased, was lacking.^[1][2]

There are several notions of high-dimensional analysis of statistical methods including:

• Non-asymptotic results which apply for finite ${\displaystyle n,p}$ (number of data points and dimension size, respectively).
• Kolmogorov asymptotics which studies the asymptotic behavior where the ratio ${\displaystyle n/p}$ is converges to a specific finite value.^[3]

Examples

Parameter estimation in linear models

Illustration of the linear model in high-dimensions: a data set consists of a response vector ${\displaystyle Y\in \mathbb {R} ^{n}}$ and a design matrix ${\displaystyle X\in \mathbb {R} ^{n\times p}}$ with ${\displaystyle p\gg n}$. Our goal is to estimate the unknown vector ${\displaystyle \beta =(\beta _{1},\dots ,\beta _{p})\in \mathbb {R} ^{p}}$ of regression coefficients where ${\displaystyle \beta }$ is often assumed to be sparse, in the sense that the cardinality of the set ${\displaystyle S:=\{j:\beta _{j}\neq 0\}}$ is small by comparison with ${\displaystyle p}$.

The most basic statistical model for the relationship between a covariate vector ${\displaystyle x\in \mathbb {R} ^{p}}$ and a response variable ${\displaystyle y\in \mathbb {R} }$ is the linear model

${\displaystyle y=x^{\top }\beta +\epsilon ,}$

where ${\displaystyle \beta \in \mathbb {R} ^{p}}$ is an unknown parameter vector, and ${\displaystyle \epsilon }$ is random noise with mean zero and variance ${\displaystyle \sigma ^{2}}$. Given independent responses ${\displaystyle Y_{1},\ldots ,Y_{n}}$, with corresponding covariates ${\displaystyle x_{1},\ldots ,x_{n}}$, from this model, we can form the response vector ${\displaystyle Y=(Y_{1},\ldots ,Y_{n})^{\top }}$, and design matrix ${\displaystyle X=(x_{1},\ldots ,x_{n})^{\top }\in \mathbb {R} ^{n\times p}}$. When ${\displaystyle n\geq p}$ and the design matrix has full column rank (i.e. its columns are linearly independent), the ordinary least squares estimator of ${\displaystyle \beta }$ is

${\displaystyle {\hat {\beta }}:=(X^{\top }X)^{-1}X^{\top }Y.}$

When ${\displaystyle \epsilon \sim N(0,\sigma ^{2})}$, it is known that ${\displaystyle {\hat {\beta }}\sim N_{p}{\bigl (}\beta ,\sigma ^{2}(X^{\top }X)^{-1}{\bigr )}}$. Thus, ${\displaystyle {\hat {\beta }}}$ is an unbiased estimator of ${\displaystyle \beta }$, and the Gauss-Markov theorem tells us that it is the Best Linear Unbiased Estimator.

However, overfitting is a concern when ${\displaystyle p}$ is of comparable magnitude to ${\displaystyle n}$: the matrix ${\displaystyle X^{\top }X}$ in the definition of ${\displaystyle {\hat {\beta }}}$ may become ill-conditioned, with a small minimum eigenvalue. In such circumstances ${\displaystyle \mathbb {E} (\|{\hat {\beta }}-\beta \|^{2})=\sigma ^{2}\mathrm {tr} {\bigl (}(X^{\top }X)^{-1}{\bigr )}}$ will be large (since the trace of a matrix is the sum of its eigenvalues). Even worse, when ${\displaystyle p>n}$, the matrix ${\displaystyle X^{\top }X}$ is singular. (See Section 1.2 and Exercise 1.2 in ^[1].)

It is important to note that the deterioration in estimation performance in high dimensions observed in the previous paragraph is not limited to the ordinary least squares estimator. In fact, statistical inference in high dimensions is intrinsically hard, a phenomenon known as the curse of dimensionality, and it can be shown that no estimator can do better in a worst-case sense without additional information (see Example 15.10^[2]). Nevertheless, the situation in high-dimensional statistics may not be hopeless when the data possess some low-dimensional structure. One common assumption for high-dimensional linear regression is that the vector of regression coefficients is sparse, in the sense that most coordinates of ${\displaystyle \beta }$ are zero. Many statistical procedures, including the Lasso, have been proposed to fit high-dimensional linear models under such sparsity assumptions.

Covariance matrix estimation

Another example of a high-dimensional statistical phenomenon can be found in the problem of covariance matrix estimation. Suppose that we observe ${\displaystyle X_{1},\ldots ,X_{n}\in \mathbb {R} ^{p}}$, which are i.i.d. draws from some zero mean distribution with an unknown covariance matrix ${\displaystyle \Sigma \in \mathbb {R} ^{p\times p}}$. A natural unbiased estimator of ${\displaystyle \Sigma }$ is the sample covariance matrix

${\displaystyle {\widehat {\Sigma }}:={\frac {1}{n}}\sum _{i=1}^{n}X_{i}X_{i}^{\top }.}$

In the low-dimensional setting where ${\displaystyle n}$ increases and ${\displaystyle p}$ is held fixed, ${\displaystyle {\widehat {\Sigma }}}$ is a consistent estimator of ${\displaystyle \Sigma }$ in any matrix norm. When ${\displaystyle p}$ grows with ${\displaystyle n}$, on the other hand, this consistency result may fail to hold. As an illustration, suppose that each ${\displaystyle X_{i}\sim N_{p}(0,I)}$ and ${\displaystyle p/n\rightarrow \alpha \in (0,1)}$. If ${\displaystyle {\widehat {\Sigma }}}$ were to consistently estimate ${\displaystyle \Sigma =I}$, then the eigenvalues of ${\displaystyle {\widehat {\Sigma }}}$ should approach one as ${\displaystyle n}$ increases. It turns out that this is not the case in this high-dimensional setting. Indeed, the largest and smallest eigenvalues of ${\displaystyle {\widehat {\Sigma }}}$ concentrate around ${\displaystyle (1+{\sqrt {\alpha }})^{2}}$ and ${\displaystyle (1-{\sqrt {\alpha }})^{2}}$, respectively, according to the limiting distribution derived by Tracy and Widom, and these clearly deviate from the unit eigenvalues of ${\displaystyle \Sigma }$. Further information on the asymptotic behaviour of the eigenvalues of ${\displaystyle {\widehat {\Sigma }}}$ can be obtained from the Marchenko–Pastur law. From a non-asymptotic point of view, the maximum eigenvalue ${\displaystyle \lambda _{\mathrm {max} }({\widehat {\Sigma }})}$ of ${\displaystyle {\widehat {\Sigma }}}$ satisfies

${\displaystyle \mathbb {P} \left(\lambda _{\mathrm {max} }({\widehat {\Sigma }})\geq (1+{\sqrt {p/n}}+\delta )^{2}\right)\leq e^{-n\delta ^{2}/2},}$

for any ${\displaystyle \delta \geq 0}$ and all choices of pairs of ${\displaystyle n,p}$.^[2]

Again, additional low-dimensional structure is needed for successful covariance matrix estimation in high dimensions. Examples of such structures include sparsity, low rankness and bandedness. Similar remarks apply when estimating an inverse covariance matrix (precision matrix).

History

From an applied perspective, research in high-dimensional statistics was motivated by the realisation that advances in computing technology had dramatically increased the ability to collect and store data, and that traditional statistical techniques such as those described in the examples above were often ill-equipped to handle the resulting challenges. Theoretical advances in the area can be traced back to the remarkable result of Charles Stein in 1956,^[4] where he proved that the usual estimator of a multivariate normal mean was inadmissible with respect to squared error loss in three or more dimensions. Indeed, the James-Stein estimator^[5] provided the insight that in high-dimensional settings, one may obtain improved estimation performance through shrinkage, which reduces variance at the expense of introducing a small amount of bias. This bias-variance tradeoff was further exploited in the context of high-dimensional linear models by Hoerl and Kennard in 1970 with the introduction of ridge regression.^[6] Another major impetus for the field was provided by Robert Tibshirani's work on the Lasso in 1996, which used ${\displaystyle \ell _{1}}$ regularisation to achieve simultaneous model selection and parameter estimation in high-dimensional sparse linear regression.^[7] Since then, a large number of other shrinkage estimators have been proposed to exploit different low-dimensional structures in a wide range of high-dimensional statistical problems.

Topics in high-dimensional statistics

The following are examples of topics that have received considerable attention in the high-dimensional statistics literature in recent years:

• Linear models in high dimensions. Linear models are one of the most widely used tools in statistics and its applications. As such, sparse linear regression is one of the most well-studied topics in high-dimensional statistical research. Building upon earlier works on ridge regression and the Lasso, several other shrinkage estimators have been proposed and studied in this and related problems. They include
  • The Dantzig selector, which minimises the maximum covariate-residual correlation, instead of the residual sum of squares as in the Lasso, subject to an ${\displaystyle \ell _{1}}$ constraint on the coefficients.^[8]
  • Elastic net, which combines ${\displaystyle \ell _{1}}$ regularisation of the Lasso with ${\displaystyle \ell _{2}}$ regularisation of ridge regression to allow highly correlated covariates to be simultaneously selected with similar regression coefficients.^[9]
  • The Group Lasso, which allows predefined groups of covariates to be selected jointly.^[10]
  • The Fused lasso, which regularises the difference between nearby coefficients when the regression coefficients reflect spatial or temporal relationships, so as to enforce a piecewise constant structure.^[11]
• High-dimensional variable selection. In addition to estimating the underlying parameter in regression models, another important topic is to seek to identify the non-zero coefficients, as these correspond to variables that are needed in a final model. Each of the techniques listed under the previous heading can be used for this purpose, and are sometimes combined with ideas such as subsampling through Stability Selection.^[12][13]
• High-dimensional covariance and precision matrix estimation. These problems were introduced above; see also shrinkage estimation. Methods include tapering estimators ^[14] and the constrained ${\displaystyle \ell _{1}}$ minimisation estimator.^[15]
• Sparse principal component analysis. Principal Component Analysis is another technique that breaks down in high dimensions; more precisely, under appropriate conditions, the leading eigenvector of the sample covariance matrix is an inconsistent estimator of its population counterpart when the ratio of the number of variables ${\displaystyle p}$ to the number of observations ${\displaystyle n}$ is bounded away from zero.^[16] Under the assumption that this leading eigenvector is sparse (which can aid interpretability), consistency can be restored.^[17]
• Matrix completion. This topic, which concerns the task of filling in the missing entries of a partially observed matrix, became popular owing in large part to the Netflix prize for predicting user ratings for films.
• High-dimensional classification. Linear discriminant analysis cannot be used when ${\displaystyle p>n}$, because the sample covariance matrix is singular. Alternative approaches have been proposed based on naive Bayes,^[18] feature selection ^[19] and random projections.^[20]
• Graphical models for high-dimensional data. Graphical models are used to encode the conditional dependence structure between different variables. Under a Gaussianity assumption, the problem reduces to that of estimating a sparse precision matrix, discussed above.

Notes

1. Lederer, Johannes (2022). Fundamentals of High-Dimensional Statistics: With Exercises and R labs. Springer Textbooks in Statistics. doi:10.1017/9781108627771. ISBN 9781108498029. S2CID 128095693.
2. Wainwright, Martin J. (2019). High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press. doi:10.1017/9781108627771. ISBN 9781108498029. S2CID 128095693.
3. Wainwright MJ. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge: Cambridge University Press; 2019. doi:10.1017/9781108627771
4. Stein, C. (1956), "Inadmissibility of the usual estimator for the mean of a multivariate distribution", Proc. Third Berkeley Symp. Math. Statist. Prob., vol. 1, pp. 197–206, MR 0084922, Zbl 0073.35602
5. James, W.; Stein, C. (1961), "Estimation with quadratic loss", Proc. Fourth Berkeley Symp. Math. Statist. Prob., vol. 1, pp. 361–379, MR 0133191
6. Hoerl, Arthur E., and Robert W. Kennard. “Ridge Regression: Biased Estimation for Nonorthogonal Problems.” Technometrics, vol. 12, no. 1, 1970, pp. 55–67. [www.jstor.org/stable/1267351 JSTOR]. Accessed 13 March 2021.
7. Tibshirani, Robert (1996). "Regression Shrinkage and Selection via the lasso". Journal of the Royal Statistical Society. Series B (methodological). 58 (1). Wiley: 267–88. JSTOR 2346178.
8. Candes, Emmanuel; Tao, Terence (2007). "The Dantzig selector: Statistical estimation when p is much larger than n". Annals of Statistics. 35 (6): 2313–2351. arXiv:math/0506081. doi:10.1214/009053606000001523. MR 2382644. S2CID 88524200.
9. Zou, Hui; Hastie, Trevor (2005). "Regularization and Variable Selection via the Elastic Net". Journal of the Royal Statistical Society. Series B (statistical Methodology). 67 (2). Wiley: 301–20. doi:10.1111/j.1467-9868.2005.00503.x. JSTOR 3647580.
10. Yuan, Ming; Lin, Yi (2006). "Model Selection and Estimation in Regression with Grouped Variables". Journal of the Royal Statistical Society. Series B (statistical Methodology). 68 (1). Wiley: 49–67. doi:10.1111/j.1467-9868.2005.00532.x. JSTOR 3647556. S2CID 6162124.
11. Tibshirani, Robert, Michael Saunders, Saharon Rosset, Ji Zhu, and Keith Knight. 2005. “Sparsity and Smoothness via the Fused lasso”. Journal of the Royal Statistical Society. Series B (statistical Methodology) 67 (1). Wiley: 91–108. https://www.jstor.org/stable/3647602.
12. Meinshausen, Nicolai; Bühlmann, Peter (2010). "Stability selection". Journal of the Royal Statistical Society, Series B (Statistical Methodology). 72 (4): 417–473. doi:10.1111/j.1467-9868.2010.00740.x. ISSN 1467-9868. S2CID 1231300.
13. Shah, Rajen D.; Samworth, Richard J. (2013). "Variable selection with error control: another look at stability selection". Journal of the Royal Statistical Society. Series B (Statistical Methodology). 75 (1): 55–80. arXiv:1105.5578. doi:10.1111/j.1467-9868.2011.01034.x. ISSN 1369-7412. JSTOR 23361014. S2CID 18211609.
14. Cai, T. Tony; Zhang, Cun-Hui; Zhou, Harrison H. (August 2010). "Optimal rates of convergence for covariance matrix estimation". The Annals of Statistics. 38 (4): 2118–2144. arXiv:1010.3866. doi:10.1214/09-AOS752. ISSN 0090-5364. S2CID 14038500. Retrieved 2021-04-06.
15. Cai, Tony; Liu, Weidong; Luo, Xi (2011-06-01). "A Constrained ${\displaystyle \ell _{1}}$ Minimization Approach to Sparse Precision Matrix Estimation". Journal of the American Statistical Association. 106 (494): 594–607. arXiv:1102.2233. doi:10.1198/jasa.2011.tm10155. ISSN 0162-1459. S2CID 15900101. Retrieved 2021-04-06.
16. Johnstone, Iain M.; Lu, Arthur Yu (2009-06-01). "On Consistency and Sparsity for Principal Components Analysis in High Dimensions". Journal of the American Statistical Association. 104 (486): 682–693. doi:10.1198/jasa.2009.0121. ISSN 0162-1459. PMC 2898454. PMID 20617121.
17. Vu, Vincent Q.; Lei, Jing (December 2013). "Minimax sparse principal subspace estimation in high dimensions". The Annals of Statistics. 41 (6): 2905–2947. arXiv:1211.0373. doi:10.1214/13-AOS1151. ISSN 0090-5364. S2CID 562591.
18. Bickel, Peter J.; Levina, Elizaveta (2004). "Some theory for Fisher's linear discriminant function, naive Bayes', and some alternatives when there are many more variables than observations". Bernoulli. 10 (6): 989–1010. doi:10.3150/bj/1106314847.
19. Fan, Jianqing; Fan, Yingying (December 2008). "High-dimensional classification using features annealed independence rules". The Annals of Statistics. 36 (6): 2605–2637. arXiv:math/0701108. doi:10.1214/07-AOS504. PMC 2630123. PMID 19169416. S2CID 2982392.
20. Cannings, Timothy I.; Samworth, Richard J. (2017). "Random-projection ensemble classification". Journal of the Royal Statistical Society, Series B (Statistical Methodology). 79 (4): 959–1035. arXiv:1504.04595. doi:10.1111/rssb.12228. S2CID 88520328.

References

• Lederer, Johannes (2022). Fundamentals of High-Dimensional Statistics. Cham: Springer.
• Giraud, Christophe (2015). Introduction to High-Dimensional Statistics. Philadelphia: Chapman and Hall/CRC.
• Cai, T. Tony; Shen, Xiaotong, eds. (2011). High-dimensional data analysis. Frontiers of Statistics. Singapore: World Scientific.
• Bühlmann, Peter; van de Geer, Sara (2011). Statistics for high-dimensional data: methods, theory and applications. Heidelberg; New York: Springer.
• Wainwright, Martin J. (2019). High-dimensional Statistics: A non-asymptotic viewpoint. Cambridge, UK: Cambridge University Press.