Membership testing for Bernoulli and tail-dependence matrices

Daniel Krause, Matthias Scherer, Jonas Schwinn and Ralf Werner

Journal of Multivariate Analysis, 2018, vol. 168, issue C, 240-260

Abstract: Testing a given matrix for membership in the family of Bernoulli matrices is a long-standing problem; the many applications of Bernoulli vectors in computer science, finance, medicine, and operations research emphasize its practical relevance. After the three-variate case was covered by Chaganty and Joe (2006) by means of partial correlations, a novel approach towards this problem was taken by Fiebig et al. (2017) for low-dimensional settings, i.e., d≤6. The latter authors were the first to exploit the close relationship between the probabilistic world of Bernoulli matrices and the well-studied correlation and cut polytopes. Inspired by this approach, we use results from Deza and Laurent (1997), Embrechts et al. (2016), and Fiebig et al. (2017) in a pre-phase of a novel algorithm to check necessary as well as sufficient conditions, before actually testing a matrix for Bernoulli compatibility. In our main approach, however, we build upon an early attempt by Lee (1993) based on the vertex representation of the correlation polytope and directly solve the corresponding linear program. To deal appropriately with the issue of exponentially many primal variables, we propose a specifically tailored column generation method. A straightforward, yet novel, analysis of the arising subproblem of determining the most violated dual constraint in the column generation process leads to an exact algorithm for membership testing. Although the membership problem is known to be NP-complete, we observe very promising performance up to dimension d=40 on a broad variety of test problems. An important byproduct of the numerical solution is a representation for Bernoulli matrices with (only) d2 many vertices that gives rise to an efficient simulation routine.

Keywords: Bernoulli-compatible matrix; Binary quadratic programming; Column generation; Tail-dependence matrix (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0047259X1730564X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jmvana:v:168:y:2018:i:c:p:240-260

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.jmva.2018.07.014

Access Statistics for this article

Journal of Multivariate Analysis is currently edited by de Leeuw, J.

More articles in Journal of Multivariate Analysis from Elsevier
Bibliographic data for series maintained by Catherine Liu ().