The search functionality is under construction.
The search functionality is under construction.

Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields

Tatsuya KOYAKUMARU, Masahiro YUKAWA, Eduardo PAVEZ, Antonio ORTEGA

  • Full Text Views

    0

  • Cite this

Summary :

This paper presents a convex-analytic framework to learn sparse graphs from data. While our problem formulation is inspired by an extension of the graphical lasso using the so-called combinatorial graph Laplacian framework, a key difference is the use of a nonconvex alternative to the l1 norm to attain graphs with better interpretability. Specifically, we use the weakly-convex minimax concave penalty (the difference between the l1 norm and the Huber function) which is known to yield sparse solutions with lower estimation bias than l1 for regression problems. In our framework, the graph Laplacian is replaced in the optimization by a linear transform of the vector corresponding to its upper triangular part. Via a reformulation relying on Moreau's decomposition, we show that overall convexity is guaranteed by introducing a quadratic function to our cost function. The problem can be solved efficiently by the primal-dual splitting method, of which the admissible conditions for provable convergence are presented. Numerical examples show that the proposed method significantly outperforms the existing graph learning methods with reasonable computation time.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E106-A No.1 pp.23-34
Publication Date
2023/01/01
Publicized
2022/07/01
Online ISSN
1745-1337
DOI
10.1587/transfun.2021EAP1153
Type of Manuscript
PAPER
Category
Graphs and Networks

Authors

Tatsuya KOYAKUMARU
  Keio University
Masahiro YUKAWA
  Keio University
Eduardo PAVEZ
  University of Southern California
Antonio ORTEGA
  University of Southern California

Keyword