Constrained ℓ1 Minimization Algorithm

A Constrained ℓ1 Minimization Algorithm is an ℓ1 Minimization Algorithm that is a Constrained Optimization Algorithm.

• See: ℓ2 Minimization Algorithm, Covariance Matrix, Gaussian Graphical Model, Precision Matrix, Rate of Convergence, Spectral Norm.

---

---

References

2011

• (Cai et al., 2011) ⇒ Tony Cai, Weidong Liu, and Xi Luo. (2011). “A Constrained ℓ 1 Minimization Approach to Sparse Precision Matrix Estimation.” In: Journal of the American Statistical Association 106, no. 494
  • ABSTRACT: This article proposes a constrained ℓ1 minimization method for estimating a sparse inverse covariance matrix based on a sample of n iid p-variate random variables. The resulting estimator is shown to have a number of desirable properties. In particular, the rate of convergence between the estimator and the true s-sparse precision matrix under the spectral norm is [math]\displaystyle{ ^s\sqrt{log \ p/n} }[/math]when the population distribution has either exponential-type tails or polynomial-type tails. We present convergence rates under the element-wise ℓ∞ norm and Frobenius norm. In addition, we consider graphical model selection. The procedure is easily implemented by linear programming. Numerical performance of the estimator is investigated using both simulated and real data. In particular, the procedure is applied to analyze a breast cancer dataset and is found to perform favorably compared with existing methods.

---