Sparse Estimation and Covariance

Assume the Axiom of Choice as used by Standard normal and normal laws. For integers $d,n\ge 1$, a noise scale $\sigma \ge 0$, and a parameter $\theta \in {\mathbb{R}}^d$, the Gaussian sequence observation is $Y_j={\theta }_j+\frac{\sigma }{\sqrt{n}}{Z}_j,1\le j\le d,$ where $Z_1,\dots ,Z_d$ are independent random variables with law $N(0,1)$. The parameter is $s$-sparse when $0\le s\le d$ is an integer and at most $s$ coordinates of $\theta$ are nonzero. This is an observation model; it does not itself assert a risk bound or an optimal estimator.

[F1] Standard normal and normal laws: under AC, $N(0,1)$ is the probability law with density $(2\pi {)}^{-1\mathrm{/}2}{e}^{-x^2\mathrm{/}2}$. [F2] Independent random elements: independence means independence of the sigma-algebras generated by the random variables; no coordinate independence is inferred unless stated.

Let $n,d\ge 1$ be integers, let $X\in {\mathbb{R}}^{n\times d}$ be deterministic, and let ${\theta }^{\ast }\in {\mathbb{R}}^d$. The fixed-design regression model is $Y=X{\theta }^{\ast }+\epsilon ,$ where $Y,\epsilon$ are random vectors in ${\mathbb{R}}^n$. For ${\sigma }^2\ge 0$, the noise is centered sub-Gaussian with proxy ${\sigma }^2$ when $\mathbb{E}{e}^{\lambda ⟨u,\epsilon ⟩}\le e^{{\sigma }^2{\lambda }^2\mathrm{\parallel }u{\mathrm{\parallel }}_2^2\mathrm{/}2}(u\in {\mathbb{R}}^n,\lambda \in \mathbb{R}),$ using the vector convention of Sub-Gaussian variables and vectors, and sub-exponential variables. No independence among the coordinates of $\epsilon$ is assumed. The parameter is $s$-sparse when $1\le s\le d$ and $\mathrm{\mid }\{j:{\theta }_j^{\ast }\mathrm{\ne }0\}\mathrm{\mid }\le s$.

For integers $n,d,s$ with $n\ge 1$ and $1\le s\le d$, and a deterministic matrix $X\in {\mathbb{R}}^{n\times d}$, write $G=X^{\mathsf{T}}X\mathrm{/}n$. The design satisfies the incoherence condition at sparsity $s$ if ${\max }_{1\le j,k\le d}\mathrm{\mid }{G}_{jk}-{\mathbf{1}}_{\{j=k\}}\mathrm{\mid }\le \frac{1}{14s}\mathrm{.}$ Here the maximum is entrywise, ${\mathbf{1}}_{\{j=k\}}$ is $1$ when $j=k$ and $0$ otherwise, and no probabilistic assumption on $X$ is made. The constant $1\mathrm{/}(14s)$ is the exact premise used in the local restricted-eigenvalue derivation; it is not a generic definition of design compatibility.

Let $n,d\ge 1$, $1\le s\le d$, and $X\in {\mathbb{R}}^{n\times d}$. For $S\subseteq \{1,\dots ,d\}$, let $v_S$ be the vector agreeing with $v\in {\mathbb{R}}^d$ on $S$ and equal to zero off $S$; write $\mathrm{\parallel }v{\mathrm{\parallel }}_1={\sum }_j\mathrm{\mid }{v}_j\mathrm{\mid }$ and use the Euclidean norm $\mathrm{\parallel }\cdot {\mathrm{\parallel }}_2$ of Euclidean spheres and closed balls as subspaces of ${\mathbb{R}}^n$. The cone associated to $S$ is $\mathcal{C}(S)=\{v\in {\mathbb{R}}^d:\mathrm{\parallel }{v}_{S^c}{\mathrm{\parallel }}_1\le 3\mathrm{\parallel }{v}_S{\mathrm{\parallel }}_1\}\mathrm{.}$ The design satisfies the restricted eigenvalue condition with constant ${\kappa }^2>0$ at sparsity $s$ when $\frac{\mathrm{\parallel }Xv{\mathrm{\parallel }}_2^2}{n}\ge {\kappa }^2\mathrm{\parallel }{v}_S{\mathrm{\parallel }}_2^2$ for every $S$ with $\mathrm{\mid }S\mathrm{\mid }\le s$ and every nonzero $v\in \mathcal{C}(S)$. The denominator is the norm of the supported component; this condition does not assert a lower bound for all vectors in ${\mathbb{R}}^d$.

For $n,d\ge 1$, a deterministic design $X\in {\mathbb{R}}^{n\times d}$, response $y\in {\mathbb{R}}^n$, and penalty $\tau >0$, define the Lasso objective $Q_y(\theta )=\frac{1}{n}\mathrm{\parallel }y-X\theta {\mathrm{\parallel }}_2^2+2\tau \mathrm{\parallel }\theta {\mathrm{\parallel }}_1\mathrm{.}$ Its minimizer set is $\mathcal{M}(y)={\mathrm{argmin}}_{\theta \in {\mathbb{R}}^d}{Q}_y(\theta )$. The penalty is strictly positive; no full-rank condition on $X$ is imposed. The nonemptiness, compactness, and convexity of this set are proved separately; this page defines the objective and minimizer set but does not select one minimizer.

Fix integers $n,d\ge 1$, a deterministic matrix $X\in {\mathbb{R}}^{n\times d}$, a response $y\in {\mathbb{R}}^n$, and a penalty $\tau >0$. The minimizer set $\mathcal{M}(y)$ of Lasso estimator for fixed design is nonempty, compact, and convex.

Let $Y=X{\theta }^{\ast }+\epsilon$ be the fixed-design model of Fixed-design regression with sub-Gaussian noise, let $S=\{j:{\theta }_j^{\ast }\mathrm{\ne }0\}$, and let $\widehat{\theta }$ be any minimizer of the objective in Lasso estimator for fixed design with $\tau >0$. Write $\mathrm{\Delta }=\widehat{\theta }-{\theta }^{\ast }$. If ${\parallel X^{\mathsf{T}}\epsilon \mathrm{/}n\parallel }_{\mathrm{\infty }}\le \tau \mathrm{/}2,$ then $\frac{\mathrm{\parallel }X\mathrm{\Delta }{\mathrm{\parallel }}_2^2}{n}+\tau \mathrm{\parallel }{\mathrm{\Delta }}_{S^c}{\mathrm{\parallel }}_1\le 3\tau \mathrm{\parallel }{\mathrm{\Delta }}_S{\mathrm{\parallel }}_1\mathrm{.}$ In particular, $\mathrm{\parallel }{\mathrm{\Delta }}_{S^c}{\mathrm{\parallel }}_1\le 3\mathrm{\parallel }{\mathrm{\Delta }}_S{\mathrm{\parallel }}_1$, so $\mathrm{\Delta }\in \mathcal{C}(S)$ for the cone in Restricted eigenvalue condition on the Lasso cone.

Let $n\ge 1$, $1\le s\le d$, and let $X\in {\mathbb{R}}^{n\times d}$ satisfy the incoherence condition of Fixed-design incoherence condition. For every $S\subseteq \{1,\dots ,d\}$ with $\mathrm{\mid }S\mathrm{\mid }\le s$ and every $v\in \mathcal{C}(S)$, $\frac{\mathrm{\parallel }Xv{\mathrm{\parallel }}_2^2}{n}\ge \frac{1}{2}\mathrm{\parallel }{v}_S{\mathrm{\parallel }}_2^2\mathrm{.}$ Consequently the restricted eigenvalue condition of Restricted eigenvalue condition on the Lasso cone holds with ${\kappa }^2=1\mathrm{/}2$.

Let $Y=X{\theta }^{\ast }+\epsilon$ be as in Fixed-design regression with sub-Gaussian noise, with $n\ge 1$, $d\ge 1$, noise proxy ${\sigma }^2\ge 0$, and $X$ satisfying the incoherence condition of Fixed-design incoherence condition at some $1\le s\le d$. For $\delta \in (0,1)$ define $\tau =4\sigma (\sqrt{\frac{\log (2d)}{n}}+\sqrt{\frac{\log (1\mathrm{/}\delta )}{n}})\mathrm{.}$ Then $P\text{\hspace{0.17em}⁣}({\parallel X^{\mathsf{T}}\epsilon \mathrm{/}n\parallel }_{\mathrm{\infty }}\le \tau \mathrm{/}2)\ge 1-\delta \mathrm{.}$

Let $n,d,s$ be integers with $n\ge 2$, $d\ge 1$, $1\le s\le d$, and let $\sigma >0$, $\delta \in (0,1)$. In the model $Y=X{\theta }^{\ast }+\epsilon$ of Fixed-design regression with sub-Gaussian noise, suppose $\mathrm{\mid }\{j:{\theta }_j^{\ast }\mathrm{\ne }0\}\mathrm{\mid }\le s$ and the deterministic design satisfies the incoherence condition of Fixed-design incoherence condition. Define $\tau =4\sigma (\sqrt{\frac{\log (2d)}{n}}+\sqrt{\frac{\log (1\mathrm{/}\delta )}{n}})\mathrm{.}$ For every response realization the minimizer set in Lasso estimator for fixed design is nonempty by The Lasso objective has a nonempty compact convex minimizer set. The measurable score event has probability at least $1-\delta$, and on that event every minimizer $\widehat{\theta }$ in the set satisfies $\frac{\mathrm{\parallel }X\widehat{\theta }-X{\theta }^{\ast }{\mathrm{\parallel }}_2^2}{n}\le 576s{\sigma }^2\frac{\log (2d\mathrm{/}\delta )}{n},\mathrm{\parallel }\widehat{\theta }-{\theta }^{\ast }{\mathrm{\parallel }}_1\le 96\sqrt{2}s\sigma \sqrt{\frac{\log (2d\mathrm{/}\delta )}{n}}\mathrm{.}$ In particular, the prediction and coefficient rates are respectively $O(s{\sigma }^2\log (2d\mathrm{/}\delta )\mathrm{/}n)$ and $O(s\sigma \sqrt{\log (2d\mathrm{/}\delta )\mathrm{/}n})$. Incoherence is sufficient for these bounds, but not necessary. Without any design restriction, the coefficient bound can fail.

Let $n,p\ge 1$ be integers and let $X_1,\dots ,X_n$ be independent identically distributed random vectors in ${\mathbb{R}}^p$ with finite second moments, mean $\mu =\mathbb{E}{X}_1$, and covariance matrix $\mathrm{\Sigma }=\mathbb{E}[(X_1-\mu )(X_1-\mu {)}^{\mathsf{T}}]\mathrm{.}$ The oracle-centered sample covariance and the sample-centered covariance are respectively ${\widehat{\mathrm{\Sigma }}}_{\mu }=\frac{1}{n}{\sum }_{i=1}^n(X_i-\mu )(X_i-\mu {)}^{\mathsf{T}},{\widehat{\mathrm{\Sigma }}}^{\ast }=\frac{1}{n}{\sum }_{i=1}^n(X_i-\bar{X})(X_i-\bar{X}{)}^{\mathsf{T}},\bar{X}=\frac{1}{n}{\sum }_{i=1}^n{X}_i\mathrm{.}$ For a matrix estimate $A$, squared operator loss is $\mathrm{\parallel }A-\mathrm{\Sigma }{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}^2$, with the operator norm of The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||. This definition distinguishes the known-mean raw second moment from the estimator that removes an unknown mean.

Let $p\ge 2$ be an integer, $0\le q<1$, $c_{n,p}\ge 0$, and $\tau >0$. For a symmetric covariance matrix $\mathrm{\Sigma }=({\sigma }_{ij}{)}_{1\le i,j\le p}$, write $\mathrm{\mid }{\sigma }_{-j,j}{\mathrm{\mid }}_{(1)}\ge \cdots \ge \mathrm{\mid }{\sigma }_{-j,j}{\mathrm{\mid }}_{(p-1)}$ for the magnitudes of the off-diagonal entries in column $j$, arranged in nonincreasing order. Define $G_q(c_{n,p})=\{\mathrm{\Sigma }:{\max }_{1\le j\le p}{\max }_{1\le k\le p-1}k\mathrm{\mid }{\sigma }_{-j,j}{\mathrm{\mid }}_{(k)}^q\le c_{n,p}\}(0<q<1)\mathrm{.}$ For $q=0$, define $G_0(c_{n,p})$ to be the symmetric covariance matrices with at most $c_{n,p}$ nonzero off-diagonal entries in each column. The corresponding law class ${\mathcal{P}}_q(\tau ,c_{n,p})$ consists of iid laws of $X\in {\mathbb{R}}^p$ whose covariance lies in $G_q(c_{n,p})$ and which satisfy

for every unit vector $v$ and every $t>0$. This is a clean sub-Gaussian model; it assumes neither coordinate independence nor robustness to contamination.

Let $\mathcal{Q}$ be a family of probability laws on a common measurable sample space $(\mathcal{Z},\mathcal{C})$, and let $\mathrm{\Sigma }(Q)\in {\mathbb{R}}^{p\times p}$ be a specified matrix parameter for each $Q\in \mathcal{Q}$, with fixed $p\ge 1$. Give ${\mathbb{R}}^{p\times p}$ its usual Euclidean topology and Borel sigma-algebra. An estimator is a measurable map $\widehat{\mathrm{\Sigma }}:(\mathcal{Z},\mathcal{C})\to ({\mathbb{R}}^{p\times p},\mathcal{B}({\mathbb{R}}^{p\times p}))$. Define its squared operator risk at $Q$ and the minimax risk over $\mathcal{Q}$ by $R_Q(\widehat{\mathrm{\Sigma }})={\mathbb{E}}_Q\mathrm{\parallel }\widehat{\mathrm{\Sigma }}-\mathrm{\Sigma }(Q){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}^2,\mathfrak{R}(\mathcal{Q})={\inf }_{\widehat{\mathrm{\Sigma }}}{\sup }_{Q\in \mathcal{Q}}{R}_Q(\widehat{\mathrm{\Sigma }})\mathrm{.}$

For a family $\mathcal{P}$ of one-observation laws on a common measurable space $(\mathcal{X},\mathcal{A})$, specify a matrix parameter $\mathrm{\Sigma }(P)\in {\mathbb{R}}^{p\times p}$ for every $P\in \mathcal{P}$, with fixed $p\ge 1$. For an integer $n\ge 1$, the $n$-observation experiment observes $n$ independent observations, each with law $P$. Its sample space is $({\mathcal{X}}^n,{\mathcal{A}}^{\otimes n})$ and its sample law is the finite product probability measure $P^{\otimes n}$; this is the joint law of the IID family in Identical distribution and IID families and Independent random elements. For estimators $\widehat{\mathrm{\Sigma }}:({\mathcal{X}}^n,{\mathcal{A}}^{\otimes n})\to ({\mathbb{R}}^{p\times p},\mathcal{B}({\mathbb{R}}^{p\times p}))$, define $R_{n,P}(\widehat{\mathrm{\Sigma }})={\mathbb{E}}_{P^{\otimes n}}\mathrm{\parallel }\widehat{\mathrm{\Sigma }}-\mathrm{\Sigma }(P){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}^2,{\mathfrak{R}}_n(\mathcal{P})={\inf }_{\widehat{\mathrm{\Sigma }}}{\sup }_{P\in \mathcal{P}}{R}_{n,P}(\widehat{\mathrm{\Sigma }})\mathrm{.}$

An infinite expectation is allowed, so every measurable estimator has an extended nonnegative risk. Suprema of risks are taken in the ordered range $[0,\mathrm{\infty }]$, with $\sup \mathrm{\varnothing }:=0$, its least element. Thus when $\mathcal{Q}$ or $\mathcal{P}$ is empty the corresponding supremum is zero for every estimator, and its minimax risk is zero. The estimator class is nonempty because the constant zero matrix map is measurable. The operator norm is from The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||.

For $\tau >0$ and $z\in \mathbb{R}$, define the soft-thresholding map $S_{\tau }(z)=\{\begin{array}{ll}z-\tau ,& z>\tau ,\\ 0,& -\tau \le z\le \tau ,\\ z+\tau ,& z<-\tau \mathrm{.}\end{array}$

Let $U,V$ be centered real random variables, not necessarily independent, each sub-Gaussian with proxy $K^2>0$ as in Sub-Gaussian variables and vectors, and sub-exponential variables. Then $W=UV-\mathbb{E}[UV]$ is sub-exponential with parameters $(256K^4,16K^2)$ under the restricted-MGF convention of that definition.

Let $A\in {\mathbb{R}}^{p\times p}$ be symmetric and let $\mathcal{N}$ be a $1\mathrm{/}4$-net of the Euclidean unit sphere in ${\mathbb{R}}^p$. Then $\mathrm{\parallel }A{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le 2{\max }_{v\in \mathcal{N}}\mathrm{\mid }{v}^{\mathsf{T}}Av\mathrm{\mid }\mathrm{.}$ The operator norm is the finite-dimensional norm of The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||.

Let $A\in {\mathbb{R}}^{p\times p}$ be symmetric, where $p\ge 1$. Then $\mathrm{\parallel }A{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}={\max }_{\mathrm{\parallel }v{\mathrm{\parallel }}_2=1}\mathrm{\mid }{v}^{\mathsf{T}}Av\mathrm{\mid }={\max }_j\mathrm{\mid }{\lambda }_j\mathrm{\mid },$ where ${\lambda }_1,\dots ,{\lambda }_p$ are the eigenvalues of $A$.

Let $Z_1,\dots ,Z_n$ be iid centered random vectors in ${\mathbb{R}}^p$ with covariance $\mathrm{\Sigma }$ and finite second moments. Suppose each $Z_i$ is sub-Gaussian with vector proxy $L=\mathrm{\parallel }\mathrm{\Sigma }{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}$, as in Sub-Gaussian variables and vectors, and sub-exponential variables. For $\delta \in (0,1)$ put $r=\frac{p+\log (4\mathrm{/}\delta )}{n}\mathrm{.}$ For both the known-mean estimator ${\widehat{\mathrm{\Sigma }}}_0=n^{-1}{\sum }_i{Z}_i{Z}_i^{\mathsf{T}}$ and the sample-centered estimator ${\widehat{\mathrm{\Sigma }}}^{\ast }=n^{-1}{\sum }_i(Z_i-\bar{Z})(Z_i-\bar{Z}{)}^{\mathsf{T}}$, where $\bar{Z}=n^{-1}{\sum }_i{Z}_i$, $P(\mathrm{\parallel }{\widehat{\mathrm{\Sigma }}}_0-\mathrm{\Sigma }{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le CL(\sqrt{r}+r))\ge 1-\delta ,P(\mathrm{\parallel }{\widehat{\mathrm{\Sigma }}}^{\ast }-\mathrm{\Sigma }{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le CL(\sqrt{r}+r))\ge 1-\delta$ for a universal constant $C$ (the proof permits $C=176$). Since $p\ge 1$, this is equivalent up to a universal factor to the displayed dense rate with $p+\log (1\mathrm{/}\delta )$. If $L=0$, both estimators equal $\mathrm{\Sigma }=0$ almost surely.