View in EDS HTML Full Text PDF Full Text

Covariance selection for nonchordal graphs via chordal embedding.

Saved in:
Bibliographic Details
Title: Covariance selection for nonchordal graphs via chordal embedding.
Authors: Dahl, Joachim1 (AUTHOR) joachim@es.aau.dk, Vandenberghe, Lieven2 (AUTHOR), Roychowdhury, Vwani2 (AUTHOR)
Source: Optimization Methods & Software. Aug2008, Vol. 23 Issue 4, p501-520. 20p. 5 Diagrams, 3 Charts.
Subjects: Sparse matrix software, Mathematical optimization, Mathematical analysis, Embeddings (Mathematics), Analysis of covariance
Abstract: We describe algorithms for maximum likelihood estimation of Gaussian graphical models with conditional independence constraints. This problem is also known as covariance selection, and it can be expressed as an unconstrained convex optimization problem with a closed-form solution if the underlying graph is chordal. The focus of the paper is on iterative algorithms for covariance selection with nonchordal graphs. We first derive efficient methods for evaluating the gradient and Hessian of the log-likelihood function when the underlying graph is chordal. The algorithms are formulated as simple recursions on a clique tree associated with the graph. We also show that the gradient and Hessian mappings are easily inverted when the underlying graph is chordal. We then exploit these results to obtain efficient implementations of Newton's method and the conjugate gradient method for large nonchordal graphs, by embedding the graph in a chordal graph. [ABSTRACT FROM AUTHOR]
Copyright of Optimization Methods & Software is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Full text is not displayed to guests.
FullText Links:
  – Type: pdflink
Text:
  Availability: 1
Header DbId: egs
DbLabel: Engineering Source
An: 33141065
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Covariance selection for nonchordal graphs via chordal embedding.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Dahl%2C+Joachim%22">Dahl, Joachim</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> joachim@es.aau.dk</i><br /><searchLink fieldCode="AR" term="%22Vandenberghe%2C+Lieven%22">Vandenberghe, Lieven</searchLink><relatesTo>2</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Roychowdhury%2C+Vwani%22">Roychowdhury, Vwani</searchLink><relatesTo>2</relatesTo> (AUTHOR)
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Optimization+Methods+%26+Software%22">Optimization Methods & Software</searchLink>. Aug2008, Vol. 23 Issue 4, p501-520. 20p. 5 Diagrams, 3 Charts.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Sparse+matrix+software%22">Sparse matrix software</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+optimization%22">Mathematical optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+analysis%22">Mathematical analysis</searchLink><br /><searchLink fieldCode="DE" term="%22Embeddings+%28Mathematics%29%22">Embeddings (Mathematics)</searchLink><br /><searchLink fieldCode="DE" term="%22Analysis+of+covariance%22">Analysis of covariance</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: We describe algorithms for maximum likelihood estimation of Gaussian graphical models with conditional independence constraints. This problem is also known as covariance selection, and it can be expressed as an unconstrained convex optimization problem with a closed-form solution if the underlying graph is chordal. The focus of the paper is on iterative algorithms for covariance selection with nonchordal graphs. We first derive efficient methods for evaluating the gradient and Hessian of the log-likelihood function when the underlying graph is chordal. The algorithms are formulated as simple recursions on a clique tree associated with the graph. We also show that the gradient and Hessian mappings are easily inverted when the underlying graph is chordal. We then exploit these results to obtain efficient implementations of Newton's method and the conjugate gradient method for large nonchordal graphs, by embedding the graph in a chordal graph. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Optimization Methods & Software is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=33141065
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1080/10556780802102693
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 20
        StartPage: 501
    Subjects:
      – SubjectFull: Sparse matrix software
        Type: general
      – SubjectFull: Mathematical optimization
        Type: general
      – SubjectFull: Mathematical analysis
        Type: general
      – SubjectFull: Embeddings (Mathematics)
        Type: general
      – SubjectFull: Analysis of covariance
        Type: general
    Titles:
      – TitleFull: Covariance selection for nonchordal graphs via chordal embedding.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Dahl, Joachim
      – PersonEntity:
          Name:
            NameFull: Vandenberghe, Lieven
      – PersonEntity:
          Name:
            NameFull: Roychowdhury, Vwani
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 08
              Text: Aug2008
              Type: published
              Y: 2008
          Identifiers:
            – Type: issn-print
              Value: 10556788
          Numbering:
            – Type: volume
              Value: 23
            – Type: issue
              Value: 4
          Titles:
            – TitleFull: Optimization Methods & Software
              Type: main
ResultId 1