Steiner trees for Covariance Recovery#2476
Conversation
There was a problem hiding this comment.
Pull request overview
Adds benchmarking and plotting utilities for Bayes-tree covariance recovery while extending core GTSAM APIs to support multi-variable joint extraction (via Steiner-tree style compression) and more efficient covariance recovery (triangular solves / partial block extraction).
Changes:
- Added a new benchmark executable + CSV writers for multiple covariance recovery variants and query families.
- Added plotting + “visuals” export tooling for paper-ready figures.
- Extended
BayesTreewith multi-keyjoint()/jointBayesNet()and addedMarginals::crossCovariance()plus updated covariance recovery implementation and tests.
Reviewed changes
Copilot reviewed 11 out of 12 changed files in this pull request and generated 5 comments.
Show a summary per file
| File | Description |
|---|---|
| timing/timeBayesTreeCovariance.cpp | New benchmark executable measuring legacy vs Steiner localization + dense inversion vs solve-based covariance recovery. |
| timing/plot_bayes_tree_covariance.py | New script to turn summary CSV output into paper-ready plots and optional visual-data figures. |
| timing/exportBayesTreeCovarianceVisuals.cpp | New exporter producing query selections + covariances for illustrative w100 figures. |
| timing/README.md | Documentation for building/running the benchmark, exporting visuals, and generating plots. |
| tests/testMarginals.cpp | Adds tests for ordering-stable joint/cross covariance behavior and agreement with legacy computation. |
| tests/testGaussianBayesTreeB.cpp | Adds tests that multi-key joint() matches existing pairwise and legacy multifrontal marginalization. |
| gtsam/nonlinear/Marginals.h | Adds crossCovariance(left, right) API. |
| gtsam/nonlinear/Marginals.cpp | Implements cross-covariance block recovery via selected-column triangular solves; updates marginal/joint covariance routines. |
| gtsam/linear/GaussianBayesTree.cpp | Updates marginal covariance computation to avoid direct matrix inversion and handle non-finite information. |
| gtsam/inference/BayesTree.h | Adds multi-key overloads for joint() and jointBayesNet(). |
| gtsam/inference/BayesTree-inst.h | Implements multi-key joint extraction using compressed support (Steiner-tree style). |
timeSFMBAL benchmark
Worker runs
|
ProfFan
left a comment
ProfFan
left a comment
There was a problem hiding this comment.
Looks great to me 
I think the only problem is the templated magic should have more documentation, but that can be a future improvement.
gtsam/linear/GaussianBayesTree.cpp
Outdated
| } | ||
| const Matrix identity = | ||
| Matrix::Identity(information.rows(), information.cols()); | ||
| return information.selfadjointView<Eigen::Upper>().llt().solve(identity); |
There was a problem hiding this comment.
Can we use solveInPlace here? This is LAPACK's dpotri.
gtsam/nonlinear/Marginals.cpp
Outdated
|
|
||
| const Matrix identity = | ||
| Matrix::Identity(information.rows(), information.cols()); | ||
| return information.selfadjointView<Eigen::Upper>().llt().solve(identity); |
| Matrix intermediate = | ||
| R.transpose().triangularView<Eigen::Lower>().solve(selectors); | ||
| return R.triangularView<Eigen::Upper>().solve(intermediate); | ||
| } |
There was a problem hiding this comment.
Ref. recent GTSAM forum thread.
I’m still not fully convinced about the treatment of the queried-clique conditional in CovarianceRecovery.pdf.
Unless I’m misunderstanding something, my reasoning is the following:
From Eqs. (17)–(18), the interface sets A_{u,b} and B_{u,b} are constructed from separator variables along the path. Under the usual Bayes tree construction, the frontal variables of the queried clique u do not appear in ancestor cliques, so it seems that F_u = F_{d_0} is not contained in A_{u,b} \cup B_{u,b}.
If that is right, then from Eq. (19), F_u \subseteq Z_{u,b}. But Eq. (20) integrates over Z_{u,b}, so it appears that the frontal variables of the queried clique are integrated out in the shortcut \chi_{u->b}.
That is where I get confused about Eq. (21): the final integral seems to treat q_1 and q_2 as variables still present in the integrand, but if they are frontal variables of the queried cliques, it looks like they would already have been integrated out by Eq. (20).
So I may be missing something in the intended role of the descendant-side interface B_{u,b} in Eq. (18), but at the moment I don’t see how the queried clique’s frontal variables are retained.
Feel free to let me know where my reasoning goes wrong.
|
@Ovardo I had another look and you're right! I updated the PDF with an example, and what I think are now the correct definitions for A and B. Let me know what you think. I'm actually on travel so I'm doing this quickly in between activities - so they could still be wrong :-/ I appreciate your help! |
|
I've had a look, and to me it now looks consistent. One could perhaps mention that in the edge case(s) of one or both of the queried cliques themselves being the lowest common ancestor, then one should not include the respective clique potentials in the final pairwise assembly, as they are already embedded in the ancestor clique marginal. Thanks again for updating this — I really appreciate it. |
This PR contributes two main contributions: