Sparse Estimation and Covariance — Examples

Expanding [F1] and using $X^{T}X=n{I}_d$ and $X^{T}Y\mathrm{/}n=Z$ gives $Q_Y(\theta )=\mathrm{\parallel }Y{\mathrm{\parallel }}_2^2\mathrm{/}n-2Z^T\theta +\mathrm{\parallel }\theta {\mathrm{\parallel }}_2^2+2\tau \mathrm{\parallel }\theta {\mathrm{\parallel }}_1$. Hence $Q_Y(\theta )=c(Y)+{\sum }_{j=1}^d((Z_j-{\theta }_j{)}^2+2\tau \mathrm{\mid }{\theta }_j\mathrm{\mid })$, where $c(Y)=\mathrm{\parallel }Y{\mathrm{\parallel }}_2^2\mathrm{/}n-\mathrm{\parallel }Z{\mathrm{\parallel }}_2^2$ is independent of $\theta$. The objective therefore separates into one-coordinate objectives plus a constant.

For a scalar $z$, on $\theta \ge 0$ completing the square gives $(z-\theta {)}^2+2\tau \theta =(\theta -(z-\tau ){)}^2+2\tau z-{\tau }^2$, whose constrained minimum is at $\max \{z-\tau ,0\}$. On $\theta \le 0$, $(z-\theta {)}^2-2\tau \theta =(\theta -(z+\tau ){)}^2-2\tau z-{\tau }^2$, whose constrained minimum is at $\min \{z+\tau ,0\}$. If $z>\tau$, the positive candidate has value $2\tau z-{\tau }^2$ and is below the negative-branch boundary value $z^2$ by $(z-\tau {)}^2$; if $z<-\tau$, the negative candidate is below the positive-branch boundary value by $(z+\tau {)}^2$; if $\mathrm{\mid }z\mathrm{\mid }\le \tau$, both constrained minima occur uniquely at $0$. Thus the unique scalar minimizer is $S_{\tau }(z)$.

By [F4] the minimizer set is nonempty. Since each coordinate term in step 1.1 has the unique minimizer from step 1.2, their vector of minimizers is the unique global minimizer, and its coordinates satisfy ${\widehat{\theta }}_j=S_{\tau }(Z_j)$ for every $j$. In the Gaussian specialization, $Y=X{Z}_0$ gives $Z=X^{T}X{Z}_0\mathrm{/}n=Z_0$, so the formula applies pointwise to every realization of [F2]. When $n=d$ and $X=\sqrt{n}{I}_d$, this response is $Y=\sqrt{n}{Z}_0$, recovering the square case.

The Gram matrix is $X^{\mathsf{T}}X\mathrm{/}n=\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right)$, so its maximum entrywise deviation from $I$ is $1>1\mathrm{/}14$ and the incoherence condition fails.

Set $v=(1,-1)$. Then $\mathrm{\parallel }{v}_{S^c}{\mathrm{\parallel }}_1=1\le 3\mathrm{\parallel }{v}_S{\mathrm{\parallel }}_1=3$, but $Xv=0$ while $\mathrm{\parallel }{v}_S{\mathrm{\parallel }}_2^2=1$. The ratio required to be bounded below by a positive restricted-eigenvalue constant is therefore zero. The two distinct one-sparse parameters $(1,0)$ and $(0,1)$ also have the same fitted mean $X\theta =1$. Thus sparsity by itself gives neither the RE condition nor coefficient identifiability.

Let $C$ be the $n\times p$ matrix with rows $(X_i-\bar{X}{)}^{\mathsf{T}}$. Since ${\sum }_i(X_i-\bar{X})=0$, every column of $C$ lies in $\ker ({\mathbf{1}}_n^{\mathsf{T}})$. The functional ${\mathbf{1}}_n^{\mathsf{T}}:{\mathbb{R}}^n\to \mathbb{R}$ is nonzero because $n\ge 1$, so its rank is one and [F2] gives kernel dimension $n-1$. Thus $\mathrm{rank}(C)\le n-1$.

By [F1], ${\widehat{\mathrm{\Sigma }}}^{\ast }=C^{\mathsf{T}}C\mathrm{/}n$. If $v\in N(C)$, then $C^{\mathsf{T}}Cv=0$, so $N(C)\subseteq N(C^{\mathsf{T}}C)$. The matrices have the same $p$-dimensional domain; [F2] and this nullspace inclusion give $\mathrm{rank}(C^{\mathsf{T}}C)\le \mathrm{rank}(C)\le n-1<p$. Multiplication by $1\mathrm{/}n\mathrm{\ne }0$ does not change rank, so ${\widehat{\mathrm{\Sigma }}}^{\ast }$ is singular.