arXiv preprint ·
Faster dynamic programming for tridiagonal maximum-entropy sampling
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
The maximum-entropy sampling problem (MESP) seeks, for an order-$n$ covariance matrix $C$, a principal submatrix of order $s$ with maximum log-determinant. Mostly for convenience, we assume that $C$ is nonsingular. Al-Thani and Lee (2023) solved MESP in $O(n^5)$ time when $C$ or $C^{-1}$ is tridiagonal. We show that the inner maximization of their recursion depends only on a prefix of the index set and that no piece of a solution is longer than $s$; this gives an $O(ns^2)$-time algorithm that returns the optimal value for every budget $t\le s$. When $C^{-1}$ is tridiagonal, $C$ is, up to scaling, the covariance matrix of an Ornstein--Uhlenbeck process observed at unevenly spaced times, and MESP becomes choosing points on a line under a concave gap function with the Monge property; this gives an $O(ns)$-time algorithm and, in the first-order autoregressive case, a closed-form solution. Given only $C$, we solve MESP in $O(n^2)$ time whenever $C$ or $C^{-1}$ is tridiagonal, up to a symmetric permutation, and we recognize these cases within the same bound. For spiders, we make explicit, and sharpen, the dependence on the number of legs, and, drawing on a hardness result of Ohsaka for stars, we observe that, unless $\mathrm{P}=\mathrm{NP}$, the exponent of the running time must grow with the number of legs.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Explicit Asymptotic Bounds for Sequential Calibration Beyond $T^{2/3}$
Generating cyclic pivot Gray codes for well-ordered $k$-degenerate graphs in constant amortized time
How to Fix a Broken Metric: A Linear Kernel, Tight Bounds, and Tree Metrics
Envy-free Allocations with Individual Payments
When Can Stateless Recovery Defeat Byzantine Quorum Safety? A Tight Normal Form for Single-Step BFT
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.