Source-linked AI summary
Faster dynamic programming for tridiagonal maximum-entropy sampling
Marcia Fampa, Jon Lee
TL;DR
For tridiagonal covariance or precision structure, prior MESP methods required O(n^5) time. This paper exploits the recursion, a point-selection formulation, and spider structure to obtain faster algorithms, including O(n^2) bounds for both tridiagonal cases.
Problem
For tridiagonal covariance or precision structure, the prior MESP approach takes O(n^5), motivating faster algorithms for these cases.
Source: §1 · p. 3Method
The paper prunes the recursion using prefix and budget structure, exploits the Ornstein–Uhlenbeck/Monge formulation for tridiagonal precision, and models spider-leg interaction through a scalar Schur complement.
Source: §1 · pp. 2–3Results
O(n^2) replaces O(n^5) in both tridiagonal structures; the paper also gives O(ns^2) and O(ns) algorithms, plus spider algorithms exponential only in the number of legs.
Source: §1 · pp. 2–3Takeaways & Limitations
On spiders, scalar coupling is the source of hardness; stars are the unrestricted-coupling case and MESP is NP-hard on them.
Source: §1 · p. 3For bandwidth k≥2, polynomial solvability for fixed k remains open, while MESP is NP-hard on stars.
Source: §6 · p. 18, §7 · p. 19
Abstract
from arXiv · showhide
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.
1. Introduction
MESP selects an order-s principal submatrix of a covariance matrix to maximize its log-determinant, and earlier work solved tridiagonal cases in O(n^5) time. This paper improves the bounds for tridiagonal matrices and spiders, including an O(n^2) algorithm when C or C^-1 is tridiagonal.
1. Introduction
- MESP seeks an order-s principal submatrix of C with maximum log-determinant; the problem is NP-hard in general.Al-Thani and Lee give an O(n^5)-time dynamic program when C or C^-1 is tridiagonal.Source: §1 · p. 2
- O(ns^2) time improves the tridiagonal-C dynamic program by reusing prefix maxima and limiting pieces to length s.The algorithm uses O(ns) memory and returns optimal values for every budget t ≤ s.Source: §1 · p. 2
- O(ns) time solves the tridiagonal-C^-1 case by viewing MESP as point selection with a concave gap function and the Monge property.The first-order autoregressive case also has a closed-form solution.Source: §1 · p. 2
- O(n^2) replaces O(n^5) for either tridiagonal structure, with input-only algorithms that also recognize these cases within O(n^2) time.Table 1 compares the methods and includes preprocessing; the O(n^2) recognition bound applies when it is not known whether C^-1 is tridiagonal.Source: §1 · p. 3, Table 1 · p. 3
- For spiders, the legs interact through the body and a single scalar Schur complement, yielding time linear in n and exponential only in the number of legs.Stars are NP-hard, and the paper identifies them as the case where the scalar coupling is unrestricted.Source: §1 · p. 3
2. Preliminaries
For tridiagonal C, selected indices split into consecutive runs whose log-determinants add. The preliminaries provide interval log-determinants through a determinant recursion and explain how the algorithms avoid requiring logarithms as primitive operations.
2. Preliminaries
- Because tridiagonal C makes the selected submatrix block diagonal across maximal consecutive runs, its log-determinant is the sum of the runs’ log-determinants.The runs are separated by at least one unselected index.Source: §2 · p. 4
- A three-term determinant recursion computes the pivots and interval log-determinants needed by the algorithms.The pivots are ratios of consecutive leading principal minors, which are positive for positive-definite C.Source: §2 · p. 4
- O(ns) time suffices to compute every needed interval log-determinant whose length is at most s.These are the interval values used by the later dynamic program.Source: §2 · p. 4
- The algorithms need not evaluate logarithms or exponentials: they can compare and combine the corresponding determinant products instead.The stated running times use an arithmetic model where basic arithmetic and comparisons cost O(1).Source: §2 · p. 4
3. The dynamic program of Al-Thani and Lee
Al-Thani and Lee’s dynamic program records the best log-determinant for a subset whose last consecutive piece is a specified interval. Its direct evaluation scans many candidate earlier pieces, producing an O(n^5) running time.
3. The dynamic program of Al-Thani and Lee
- The state f(k,ℓ,t) is the best value among t-element subsets whose last piece is [k,ℓ].Its boundary value is the log-determinant of that interval when t equals its length.Source: §3 · p. 5
- The recurrence requires j ≤ k−2 so the preceding chosen piece cannot touch [k,ℓ], and the optimum is the maximum over final intervals.The direct method stores Θ(ns^2) values for f.Source: §3 · p. 5
- O(n^5) time results from O(n^2s) states, each scanning O(n^2) candidate pairs.Restricting piece lengths still leaves costs of Θ(n^3s^2) or Θ(n^2s^3) under the described scans.Source: §3 · p. 5
4. The faster dynamic program
The faster dynamic program replaces repeated inner maximizations with prefix-based states and builds solutions by extending or omitting the current index. It computes optimal values for every budget t ≤ s in O(ns^2) time and O(ns) memory.
4. The faster dynamic program
- The earlier inner maximum depends only on the prefix endpoint and residual budget, so one running prefix maximum replaces repeated scans.As the prefix grows, the admissible pieces only grow; this reduces the total to O(ns^2).Source: §4 · p. 5
- The state g(i,t) records the best t-subset of [1,i] omitting i, while H(i,t) records the best such subset containing i.This separates solutions according to whether the current index is selected.Source: §4 · p. 6
- O(ns^2) time and O(ns) memory compute z(C,t) for every t ≤ s.The tables also yield an optimal set by traceback.Source: §4 · p. 6
- For a subset containing i, the recurrence appends its unique last piece of length ℓ to a feasible subset ending before that piece.For subsets omitting i, the recurrence considers whether i−1 is omitted or included.Source: §4 · p. 6
- When only optimal values are needed, working memory beyond the input drops to O(s^2) by retaining only recent rows.The method regenerates the needed interval values in O(s) time per index.Source: §4 · p. 7
5. Tridiagonal precision matrices
When the inverse covariance is tridiagonal, MESP can be viewed as selecting points on a line with concave gap rewards; the Monge property yields an O(ns)-time dynamic program. The section also gives a closed-form autoregressive solution and O(n^2)-time methods, including recognition, for tridiagonal structure up to symmetric permutation.
5. Tridiagonal precision matrices
- With tridiagonal inverse covariance, MESP becomes selecting points on a line to maximize node weights plus a concave, increasing function of consecutive gaps.The covariance corresponds, up to scaling, to an Ornstein–Uhlenbeck process observed at unevenly spaced times.Source: §5 · pp. 8–9
- For the first-order autoregressive case, every optimum includes both endpoints and has gaps only q or q+1, with exactly θ gaps of q+1.The result gives a closed-form optimal design; when s−1 divides n−1, the design is evenly spaced.Source: §5 · p. 9
- The Monge inequality for gap rewards enables computing optimal values for every budget t ≤ s and an optimal set in O(ns) time.The algorithm uses SMAWK to find row maxima across dynamic-programming layers.Source: §5 · pp. 10–11
- The characterization determines whether C is nonsingular with a tridiagonal inverse; when its conditions hold, it writes down C−1 and ldetC in O(n^2) time.Condition (i) costs O(n), condition (ii) consists of O(n^2) constant-time tests, and the formulas for C−1 and ldetC cost O(n).Source: §5 · p. 12
- Given C, the paper solves MESP in O(n^2) time when C or C−1 is tridiagonal, including cases detectable only after a symmetric permutation.Recognizing a permuted tridiagonal inverse also fits within O(n^2).Source: §5 · p. 13
- For tridiagonal C, the faster dynamic-programming route depends on s: use O(ns^2) for small s or O(n(n−s)) for larger s.The asymptotic crossover is roughly s < √n; for tridiagonal C−1, the corresponding comparison depends on n−s.Source: §5 · p. 14
6. Spiders with few legs
For spider support graphs, the legs interact through the body only via a scalar Schur complement, yielding a running time linear in n and with explicit dependence on the number of legs. The results also extend to known spiders in G(C^-1), while hardness on stars constrains how the running-time exponent can depend on the number of legs.
6. Spiders with few legs
- The legs interact only through the total budget and, when the body is selected, one scalar Schur-complement term; otherwise they are independent.The body-containing determinant separates into the body block and independent leg blocks.Source: §6 · pp. 15–16
- For fixed r, Theorem 14 computes z(C,s) in O(ns^2 + s^(r+1)) time.The running time is linear in n, with dependence on r confined to the body-containing case.Source: §6 · pp. 16–17
- The body-containing case enumerates depth vectors and merges leg tables, while the leg tables themselves cost O(ns^2) time to compute.The tables are computed by applying the path dynamic program to each leg in reverse order.Source: §6 · pp. 16–17
- For known G(C^-1) spiders, the same conclusions hold with budget n-s; recognizing an unknown case and computing the needed quantities takes O(n^2) time.The algorithm using C^-1 requires only its diagonal and entries on spider edges, obtainable from C in O(n) time.Source: §6 · p. 17
- On stars, MESP is NP-hard and W[1]-hard in s; unless P=NP, the running-time exponent for spiders cannot stay bounded as r grows.The paper also rules out an f(s)n^O(1) running time on stars unless FPT and W[1] coincide.Source: §6 · p. 18
7. Closing remarks
The dynamic-programming tables provide optimal values for every budget up to s, allowing independent blocks to be combined by a knapsack-type recursion. For wider banded matrices, the paper identifies interactions between pieces and leaves fixed-bandwidth polynomial solvability open.
7. Closing remarks
- The tables of Theorems 4 and 8 give z(C,t) for every t≤s, enabling a knapsack-type recursion to combine independent blocks.The recursion covers k-tridiagonal matrices and is also used for spiders.Source: §7 · p. 19
- For (2k+1)-diagonal matrices with k≥2, pieces separated by fewer than k unchosen indices interact, and polynomial solvability for fixed bandwidth remains open.The number of possible pieces grows exponentially in this setting.Source: §7 · p. 19
- The authors report equal contributions, no data used, and Claude assistance in developing and checking the work.The authors state that they take full responsibility for the published content.Source: §7 · p. 19
Appendix A. Recognizing an unknown spider
The appendix recognizes whether the precision support graph is a tree in O(n^2) time, recovering the tree and needed precision-matrix quantities. The recognition uses a maximum-weight spanning tree of correlations and a verification step, and the quadratic worst-case bound cannot be improved.
Appendix A. Recognizing an unknown spider
- O(n^2) time suffices to test whether G(C^-1) is a tree, recover the tree, the diagonal and edge entries of C^-1, and ldet C; spider recognition follows.The same bound applies when the spider structure is not known in advance.Source: Appendix A · p. 19
- The procedure builds a maximum-|ρ_ij| spanning tree, constructs a candidate precision matrix, then checks whether its product with C is the identity.The tree construction uses O(n^2) time; constructing the candidate quantities takes O(n).Source: Appendix A · p. 20
- For a true precision-support tree, path conditional independence makes -log ρ_ij^2 a tree metric, so the tree is the unique maximum-weight spanning tree.The proof uses the strict path-distance inequality for nonedges.Source: Appendix A · p. 20
- No worst-case algorithm can run in o(n^2) time, because an unread entry of C could be changed to destroy the tree structure of G(C^-1).Source: Appendix A · p. 20