pISTA: preconditioned Iterative Soft Thresholding Algorithm for Graphical Lasso

DOI10.1137/22M1496128MaRDI QIDQ6399687zbMATH OpenOpenAlexWikidataFDO

Authors Gal Shalom, Eran Treister, Irad Yavneh

Publication date 20 May 2022

Full work available at URL https://doi.org/10.1137/22m1496128

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Preconditioners for iterative methods (65F08) Numerical optimization and variational techniques (65K10) Convex programming (90C25)

Abstract: We propose a novel quasi-Newton method for solving the sparse inverse covariance estimation problem also known as the graphical least absolute shrinkage and selection operator (GLASSO). This problem is often solved using a second-order quadratic approximation. However, in such algorithms the Hessian term is complex and computationally expensive to handle. Therefore, our method uses the inverse of the Hessian as a preconditioner to simplify and approximate the quadratic element at the cost of a more complex (ell_1) element. The variables of the resulting preconditioned problem are coupled only by the (ell_1) sub-derivative of each other, which can be guessed with minimal cost using the gradient itself, allowing the algorithm to be parallelized and implemented efficiently on GPU hardware accelerators. Numerical results on synthetic and real data demonstrate that our method is competitive with other state-of-the-art approaches.

Recommendations

• QUIC: quadratic approximation for sparse inverse covariance estimation
• Sparse inverse covariance estimation with the graphical lasso
• The graphical lasso: new insights and alternatives
• Sparse Gaussian graphical model estimation via alternating minimization
• Adaptive First-Order Methods for General Sparse Inverse Covariance Selection

Cited in

(1)

• Splitting alternating algorithms for sparse solutions of linear systems with concatenated orthogonal matrices

This page was built for publication: pISTA: preconditioned Iterative Soft Thresholding Algorithm for Graphical Lasso

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6399687)