Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.15608 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917527369547776 |
|---|---|
| author | Hu, Hao Sremac, Stefan Woerdeman, Hugo J. Wolkowicz, Henry |
| author_facet | Hu, Hao Sremac, Stefan Woerdeman, Hugo J. Wolkowicz, Henry |
| contents | An important yet challenging problem in numerical linear algebra is finding a principal submatrix with maximum determinant from a given symmetric positive semidefinite matrix. This problem arises in experimental design, statistics, and machine learning.
We study several exact and approximate approaches to this problem. We first derive an upper bound based on Hadamard's inequality, along with a projection scheme based on the Gram--Schmidt process without normalization. This combination yields a highly effective upper bound and leads to an exact branch-and-bound algorithm for moderate-sized instances.
For larger scale problems we propose a continuous relaxation that facilitates reliable performance evaluation when the exact method returns only near-optimal solutions. We further prove that the projection scheme strengthens the upper bound derived from this relaxation. Numerical experiments demonstrate the effectiveness of the proposed methods across a broad range of datasets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_15608 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Finding Maximum Determinant Principal Submatrices via Hadamard Bounds and Projection Methods Hu, Hao Sremac, Stefan Woerdeman, Hugo J. Wolkowicz, Henry Optimization and Control An important yet challenging problem in numerical linear algebra is finding a principal submatrix with maximum determinant from a given symmetric positive semidefinite matrix. This problem arises in experimental design, statistics, and machine learning. We study several exact and approximate approaches to this problem. We first derive an upper bound based on Hadamard's inequality, along with a projection scheme based on the Gram--Schmidt process without normalization. This combination yields a highly effective upper bound and leads to an exact branch-and-bound algorithm for moderate-sized instances. For larger scale problems we propose a continuous relaxation that facilitates reliable performance evaluation when the exact method returns only near-optimal solutions. We further prove that the projection scheme strengthens the upper bound derived from this relaxation. Numerical experiments demonstrate the effectiveness of the proposed methods across a broad range of datasets. |
| title | Finding Maximum Determinant Principal Submatrices via Hadamard Bounds and Projection Methods |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2508.15608 |