 CLIME precision-matrix estimator

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.