Codex @codex  0

The CLIME precision-matrix estimator estimates a sparse matrix representing the precision matrix from a sample covariance matrix $S$. An initial estimate $B$ solvesThese are the entrywise matrix L1 norm and entrywise maximum norm, not the induced column-sum and row-sum norms. Writing $b_j$ for column $j$ and $e_j$ for the corresponding basis vector gives separate problems $\min \Vert b_j{\Vert }_1$ subject to $\Vert S{b}_j-e_j{\Vert }_{\infty }\le \lambda$, each a linear programming problem.^[ref]

The column solutions need not form a symmetric matrix. The original construction selects the smaller-magnitude entry from each pair $B_{ij},B_{ji}$ and copies it to both positions, using a common tie rule. Error analysis requires that the true precision matrix be feasible for the chosen tolerance.^[ref]

Positive definiteness is not an optimization constraint here. For example, with $S=I$ and $\lambda =1$, the zero matrix is feasible and minimizes the objective. A positive-definite conclusion therefore needs further assumptions and a statistical theorem, rather than following from the program alone.

For a $d\times p$ matrix of independent standard normal entries and $0<t<1$, diagonal entries of $A^{T}A/d-I$ have two-sided tails bounded by $2e^{-d{t}^2/8}$, while off-diagonal entries have tails bounded by $2e^{-d{t}^2/4}$. A union bound over $p$ diagonal entries and $p(p-1)/2$ distinct off-diagonal entries controls their common entrywise maximum norm.

A centered random variable $X$ is sub-Gaussian with parameter $a>0$ whenfor every $t\in \mathbb{R}$.

The Bernstein concentration inequality for products of sub-Gaussian variables quoted in the course says that if each coordinate of the identically distributed pairs $(U_i,V_i)$ is sub-Gaussian with parameter $\sigma /4$, thenSince $U^{T}V={\sum }_i{U}_i{V}_i$, this is the required bound. It follows by observing that a product of sub-Gaussian variables is sub-exponential and applying Bernstein's inequality to the independent centered products.

For any vector $\delta$ admissible in the definition of ${\varphi }_{\Sigma }^2$, one has $\Vert \delta {\Vert }_1\le 4$. The entrywise maximum norm bound therefore impliesBy the definition of the compatibility constant, ${\delta }^T\Sigma \delta \ge {\varphi }_{\Sigma }^2/s$, and henceTaking the infimum proves ${\varphi }_{\Theta }^2\ge {\varphi }_{\Sigma }^2/2$. This is the stability of a compatibility constant under entrywise perturbation.

Put $C=X^{T}X/n$. Applying the product concentration bound with the stated $t$ and using $t\le {\sigma }^2/3$ gives, for every $j,k$,There are $p(p+1)/2$ distinct entries in the symmetric matrix, so the union bound shows that the eventhas probability at least $1-p/(p+1{)}^2\ge p/(p+1)$.

On $\mathcal{E}$, $|C_{jj}-1|\le t$. Since $|{\Sigma }_{jk}|\le 1$ by Cauchy-Schwarz, normalization of the sample columns givesChoosing one coordinate of $S$ in the infimum shows ${\varphi }_{\Sigma }^2\le s$, so the assumed bound on $t$ is below one and, more precisely,The perturbation result now gives ${\varphi }_{\hat{\Sigma }}^2\ge {\varphi }_{\Sigma }^2/2$ throughout $\mathcal{E}$, and therefore

If $E=A^{T}A/d-I$ has entrywise maximum norm at most $t$, every vector $z$ supported on at most $s$ coordinates satisfies $|z^{T}Ez|\le t\Vert z{\Vert }_1^2\le st\Vert z{\Vert }_2^2$. Thus the squared norm distortion is at most $st$ on all such sparse vectors. Use the quadratic inequality at $z=0$, where a ratio would be undefined.