Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2404.06302 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916384143835136 |
|---|---|
| author | Brunel, Victor-Emmanuel Urschel, John |
| author_facet | Brunel, Victor-Emmanuel Urschel, John |
| contents | We consider the inverse problem of finding a magnitude-symmetric matrix (matrix with opposing off-diagonal entries equal in magnitude) with a prescribed set of principal minors. This problem is closely related to the theory of recognizing and learning signed determinantal point processes in machine learning, as kernels of these point processes are magnitude-symmetric matrices. In this work, we prove a number of properties regarding sparse and generic magnitude-symmetric matrices. We show that principal minors of order at most $\ell$, for some invariant $\ell$ depending only on principal minors of order at most two, uniquely determines principal minors of all orders. In addition, we produce a polynomial-time algorithm that, given access to principal minors, recovers a matrix with those principal minors using only a quadratic number of queries. Furthermore, when principal minors are known only approximately, we present an algorithm that approximately recovers a matrix, and show that the approximation guarantee of this algorithm cannot be improved in general. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_06302 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Recovering a Magnitude-Symmetric Matrix from its Principal Minors Brunel, Victor-Emmanuel Urschel, John Combinatorics 05C50, 15A15, 15A29 We consider the inverse problem of finding a magnitude-symmetric matrix (matrix with opposing off-diagonal entries equal in magnitude) with a prescribed set of principal minors. This problem is closely related to the theory of recognizing and learning signed determinantal point processes in machine learning, as kernels of these point processes are magnitude-symmetric matrices. In this work, we prove a number of properties regarding sparse and generic magnitude-symmetric matrices. We show that principal minors of order at most $\ell$, for some invariant $\ell$ depending only on principal minors of order at most two, uniquely determines principal minors of all orders. In addition, we produce a polynomial-time algorithm that, given access to principal minors, recovers a matrix with those principal minors using only a quadratic number of queries. Furthermore, when principal minors are known only approximately, we present an algorithm that approximately recovers a matrix, and show that the approximation guarantee of this algorithm cannot be improved in general. |
| title | Recovering a Magnitude-Symmetric Matrix from its Principal Minors |
| topic | Combinatorics 05C50, 15A15, 15A29 |
| url | https://arxiv.org/abs/2404.06302 |