Pith. sign in

REVIEW 1 major objections 6 minor 1 cited by

Submodularity of the expected information gain in infinite-dimensional linear inverse problems

T0 review · 1 major / 6 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read In infinite-dimensional linear Gaussian inverse problems, the expected information gain is a monotone submodular function, so greedy sensor placement keeps its near-optimality guarantee.

desk verdict The core theorem is new and the proof is sound; the only real debt is a standard EIG formula, so send it to referees. read the letter →

arxiv 2602.09285 v2 pith:5ET4HEZ2 submitted 2026-02-10 math.OC

Alen Alexanderian , Steven Maio This is my paper · ORCID
classification math.OC MSC 35R3062K0590C2749K4047B02
keywords expectedinformationgainsubmodularityinfinite-dimensionalinverseproblemsBayesianoptimalsensorplacementgreedyalgorithmFredholmdeterminantPDE-constrainedoptimization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves that the expected information gain (EIG) for linear Gaussian Bayesian inverse problems on an infinite-dimensional Hilbert space is a monotone submodular set function. This extends a well-known finite-dimensional result to the function-space setting, meaning the classical greedy approximation guarantee of (1 − 1/e) holds for the infinite-dimensional problem itself, independent of any discretization. The proof works by writing the prior-preconditioned data misfit Hessian as a sum of rank-one operators and reducing submodularity to a diminishing-returns check on one-element increments. The paper also presents computational accelerations, including a measurement-space formula for marginal gains and a lazy greedy procedure.

What carries the argument

The proof decomposes H̃(S) as a sum of rank-one operators f̃ᵢ ⊗ f̃ᵢ (one per candidate sensor). Two identities do the work: a Fredholm-determinant rank-one update formula (Lemma 4.1), which expresses log det(I + K + u ⊗ u) as log det(I + K) + log(1 + ‖(I+K)^{-1/2}u‖²), and an infinite-dimensional Sherman–Morrison–Woodbury formula (Lemma 3.2) for rank-one perturbations. Together they reduce submodularity to verifying that marginal gains decrease when a sensor is added to a larger set, which follows from a positive-term subtraction in the update.

What would settle it

Implement greedy sensor placement for a concrete infinite-dimensional linear Gaussian inverse problem (e.g., a 1D heat-source inversion with a trace-class Gaussian prior) using the exact marginal gain formula (23). Compare the resulting EIG against exhaustive search for small sensor budgets k; if the ratio ever falls below 1 − 1/e, the theorem's claim would be false. Alternatively, search for a linear Gaussian inverse problem with a non-trace-class prior covariance where the KL-divergence EIG remains finite but log det(I + H̃) is not defined, which would show the analytic expression (7) is not

Watch

Extended reading notes

Core claim

The central result is Theorem 4.2: the function Φ_eig(S) = log det(I + H̃(S)), where H̃(S) is the prior-preconditioned data misfit Hessian restricted to a sensor set S, is monotone and submodular. Since EIG = ½ Φ_eig, the expected information gain inherits these properties. Consequently, the greedy algorithm for cardinality-constrained sensor placement achieves an approximation ratio of at least 1 − 1/e relative to the optimal placement, and this guarantee is valid in the infinite-dimensional setting without relying on a finite-dimensional discretization.

Load-bearing premise

The analytic expression EIG = ½ log det(I + H̃) is imported from earlier work and is not proved in this paper; since the entire submodularity proof is a proof about this determinant, the theorem would not establish submodularity of EIG if that expression failed for the KL-divergence definition of EIG.

Editorial extensions

If this is right

  • Greedy sensor placement for PDE-constrained linear inverse problems is guaranteed to achieve at least 63% of the optimal expected information gain in function space, not merely after discretization.
  • The approximation guarantee extends to matroid and knapsack constraints, making the result applicable to sensor scheduling and heterogeneous-cost sensor selection problems.
  • The measurement-space formula for marginal gains allows greedy updates using inverses of k×k matrices rather than operators on the infinite-dimensional parameter space, enabling efficient implementation.
  • Lazy greedy, which exploits submodularity to reduce marginal-gain evaluations, can be applied while preserving the same approximation guarantee.
  • The result provides a rigorous foundation for linearized and adaptive experimental design in nonlinear inverse problems, as discussed in the conclusion.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The rank-one update structure suggests that any objective of the form log det(I + Σ uᵢ ⊗ uᵢ) is submodular, so the proof technique may transfer to other determinant-based criteria, such as Bayesian A-optimality variants, when expressed through the same decomposition.
  • While the paper fixes a finite candidate set V, a natural extension is to study how the greedy guarantee behaves as the candidate set is refined or grows; the paper does not address this asymptotic regime.
  • The combination of lazy greedy with the measurement-space formula (24) could be pushed further by randomized or stochastic greedy, which the paper mentions only briefly; this is a likely practical route for very large candidate sets.
  • The theorem hinges on the trace-class assumption for the prior covariance; if this assumption is relaxed, the Fredholm determinant may not exist, suggesting that the submodularity result may not extend to improper priors without additional structure.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 6 minor

Summary. The paper studies Bayesian optimal sensor placement for linear Gaussian inverse problems in an infinite-dimensional separable Hilbert space M, with observations y = Fm + η at a finite set of candidate sensors and uncorrelated Gaussian noise. The prior is Gaussian with trace-class covariance C_pr. The expected information gain (EIG), defined in Eq. (2), is represented as (1/2) log det(I + \tilde H(S)) in Eq. (7), where \tilde H(S) is the prior-preconditioned data-misfit Hessian for the selected sensors. The authors introduce a design-dependent posterior covariance, prove a rank-one update formula (Prop. 3.4), and then prove in Theorem 4.2 that Φ_eig(S) = log det(I + \tilde H(S)) is monotone and submodular. Consequently the standard greedy algorithm for cardinality-constrained sensor selection inherits the (1 - 1/e) approximation guarantee in the infinite-dimensional setting. They also discuss computational strategies, including a measurement-space formula for marginal gains and lazy greedy.

Significance. The main theorem is correct, and the proof is concise and transparent. Lemma 4.1 gives the exact marginal gain from adding a sensor, and the submodularity comparison reduces to the elementary inequality log(1 + α_rr - α_rt^2/(1 + α_tt)) ≤ log(1 + α_rr). This is a genuine extension of finite-dimensional submodularity results to infinite-dimensional parameters and is likely to be useful for PDE-constrained inverse problems. The argument has no free parameters and, modulo Eq. (7), is self-contained. The computational section provides practical, structure-exploiting algorithms. The scope is explicitly limited to uncorrelated scalar sensor observations, and this limitation is clearly stated.

major comments (1)
  1. [§2.2, Eq. (7)] The analytic expression EIG = (1/2) log det(I + \tilde H) is imported from Refs. [3,6] and is not derived in this paper. Since Theorem 4.2 concerns exactly this determinant, the connection to the stochastic definition in Eq. (2) rests entirely on Eq. (7). Please add a short derivation or a precise theorem statement with proof, or at least point to a specific theorem in [3,6] where it is proved. This is a standard result, so I do not view it as a correctness defect, but it is load-bearing and should be made explicit.
minor comments (6)
  1. [§4, proof of Theorem 4.2] The line after Eq. (19) writes det(A + \tilde f_r ⊗ \tilde f_r + \tilde f_r ⊗ \tilde f_r); the second tensor term should be \tilde f_t ⊗ \tilde f_t.
  2. [Appendix A, proof of Lemma 5.1] The sentence assigning GG^* and G^*G to L^+_sym(M) and L^+_sym(K) is reversed: G^*G is an operator on M and GG^* is an operator on K.
  3. [§3.2, Eq. (14) area] "For each S ⊂ 2^V" should be "for each S ⊆ V"; as written it is a set-theoretic abuse.
  4. [§2.2, Eq. (7)] Since EIG was already defined in Eq. (2), the notation "EIG :=\ in Eq. (7) is confusing; use "EIG =" or "EIG admits the analytic expression".
  5. [§5.1, before Eq. (24)] In the displayed derivation of (I + \tilde H(S))^{-1}m, the second equality appears to be missing the inverse on (I + \tilde F(S)\tilde F(S)^*); the correct operator is (I + \tilde F(S)\tilde F(S)^*)^{-1}.
  6. [Abstract and §6] The phrase "infinite-dimensional limit" suggests a limiting argument over discretizations, but the theorem is proved directly for a fixed infinite-dimensional Hilbert space. Rephrase as "infinite-dimensional setting" or define the limit precisely.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the submodularity theorem is proved from standard determinant identities; the one imported EIG formula is independently supported.

full rationale

The paper's central claim is Theorem 4.2, submodularity of Φ_eig(S)=log det(I+\tilde H(S)). The proof is self-contained given standard facts: the multiplicative property of Fredholm determinants, the Hilbert-space Sherman–Morrison update (Lemma 3.2), and the one-element increment identity (Lemma 4.1). No parameter is fitted and then renamed as a prediction; no uniqueness theorem from the authors is invoked to force the choice; no ansatz is smuggled in by citation. The only externally imported input is the analytic EIG formula (7), EIG = 1/2 log det(I+\tilde H), cited to the authors' earlier papers [3,6]. This formula is parameter-free, standard in linear Gaussian Bayesian inversion, and independently derivable from the Gaussian posterior covariance formula in (5); it does not incorporate the target submodularity result. Under the hard rules, a self-citation that carries independent mathematical support does not raise the circularity score. Therefore the derivation chain is non-circular.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central proof introduces no free parameters and no invented entities. It relies on standard functional analysis plus the imported EIG closed form.

assumptions (6)
  • domain assumption EIG admits the closed form EIG = (1/2) log det(I + \tilde H) (Eq. 7), cited to [3,6].
    Bridges the probabilistic definition (2) to the determinant objective Φ_eig; the paper does not derive this formula.
  • domain assumption Posterior is Gaussian with C_post = (F^* Γ^{-1} F + C_pr^{-1})^{-1} (Eq. 5), cited to [29].
    Standard framework for infinite-dimensional linear Gaussian Bayesian inverse problems.
  • standard math Fredholm determinant multiplicative property for trace-class perturbations (Eq. 4).
    Used in Lemma 4.1 to factor det(B + u⊗u).
  • standard math Submodularity can be verified via one-element increments [25, Theorem 44.1].
    Reduces the proof to comparing single additions rather than all nested subsets.
  • standard math I+K has a bounded square root (I+K)^{-1/2} for K positive self-adjoint trace-class (spectral theorem).
    Used in Lemma 4.1 to express the rank-one determinant factor as 1 + ||B^{-1/2}u||^2.
  • domain assumption Observation operator F is continuous to R^d with uncorrelated diagonal noise Γ_noise.
    Gives H = Σ f_i⊗f_i (Lemma 3.1) and the finite candidate set V; limits scope to single-snapshot, uncorrelated sensors.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Submodularity of the expected information gain in infinite-dimensional linear inverse problems." pith.science (2026). https://pith.science/paper/5ET4HEZ2

@misc{pith2026260209285,
  author       = {Pith},
  title        = {Pith review of: Submodularity of the expected information gain in infinite-dimensional linear inverse problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5ET4HEZ2}},
  note         = {Machine review of arXiv:2602.09285}
}
read the original abstract

We consider infinite-dimensional linear Gaussian Bayesian inverse problems with uncorrelated measurement errors and focus on the problem of selecting sensor placements that maximize the expected information gain (EIG). This study is motivated by optimal sensor placement for linear inverse problems constrained by partial differential equations (PDEs). We consider measurement models where each sensor collects a single-snapshot measurement. This covers sensor placement for inverse problems governed by linear steady PDEs or evolution equations with final-in-time observations. It is well-known that in the finite-dimensional (discretized) formulations of such inverse problems, the EIG is a monotone submodular function. This also entails a theoretical guarantee for greedy sensor placement in the discretized setting. We extend the result on submodularity of the EIG to the infinite-dimensional setting, proving that the approximation guarantee of greedy sensor placement remains valid in the infinite-dimensional limit. We also discuss computational considerations and present strategies that exploit problem structure and submodularity to yield efficient implementations of the greedy procedure.

Figures

Figures reproduced from arXiv: 2602.09285 by the authors.

Figure 1
Figure 1. One step of the lazy greedy algorithm. The lth step of the lazy greedy method is outlined in [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Multi-type Sensor Placement for PDE-based Bayesian Inverse Problems

    math.NA 2026-07 accept novelty 6.0 of 10

    A stochastic cost-benefit greedy algorithm with approximation guarantees is proposed for multi-type sensor placement in linear Bayesian inverse problems, and a non-intrusive BAE-based lower bound on EIG is used for no...

Reference graph

Works this paper leans on

30 extracted references · 1 linked inside Pith · cited by 1 Pith paper

  1. [1]

    Alexanderian, Optimal experimental design for infinite-dimensional Bayesian inverse prob- lems governed by PDEs: A review,Inverse Problems,37(2021), 043001

    A. Alexanderian, Optimal experimental design for infinite-dimensional Bayesian inverse prob- lems governed by PDEs: A review,Inverse Problems,37(2021), 043001

    2021

  2. [2]

    Alexanderian, H

    A. Alexanderian, H. D ´ ıaz, V. Rao and A. K. Saibaba, Optimal sensor placement under model uncertainty in the weak-constraint 4d-var framework,Foundations of Data Science, Accepted

  3. [3]

    Alexanderian, P

    A. Alexanderian, P. J. Gloor and O. Ghattas, On Bayesian A-and D-optimal experimental designs in infinite dimensions,Bayesian Analysis,11(2016), 671–695

    2016

  4. [4]

    Alexanderian, N

    A. Alexanderian, N. Petra, G. Stadler and O. Ghattas, A-optimal design of experiments for infinite-dimensional Bayesian linear inverse problems with regularizedℓ0-sparsification,SIAM Journal on Scientific Computing,36(2014), A2122–A2148

    2014

  5. [5]

    Alexanderian, N

    A. Alexanderian, N. Petra, G. Stadler and I. Sunseri, Optimal design of large-scale Bayesian linear inverse problems under reducible model uncertainty: Good to know what you don’t know,SIAM/ASA Journal on Uncertainty Quantification,9(2021), 163–184

    2021

  6. [6]

    Alexanderian and A

    A. Alexanderian and A. K. Saibaba, Efficient D-optimal design of experiments for infinite- dimensional Bayesian linear inverse problems,SIAM Journal on Scientific Computing,40 (2018), A2956–A2985

    2018

  7. [7]

    Asch,A toolbox for digital twins: from model-based to data-driven, SIAM, 2022

    M. Asch,A toolbox for digital twins: from model-based to data-driven, SIAM, 2022

    2022

  8. [8]

    A. C. Atkinson and A. N. Donev,Optimum Experimental Designs, Oxford, 1992

    1992

Show all 30 references
  1. [9]

    Boyd and N

    C. Boyd and N. Snigireva, On the analyticity of the fredholm determinant,Monatshefte f¨ ur Mathematik,190(2019), 675–687

    2019

  2. [10]

    Chaloner and I

    K. Chaloner and I. Verdinelli, Bayesian experimental design: A review,Statistical Science, 10(1995), 273–304

    1995

  3. [11]

    Dashti, K

    M. Dashti, K. J. Law, A. M. Stuart and J. Voss, Map estimators and their consistency in Bayesian nonparametric inverse problems,Inverse Problems,29(2013), 095017

    2013

  4. [12]

    C. Y. Deng, A generalization of the Sherman–Morrison–Woodbury formula,Applied Mathe- matics Letters,24(2011), 1561–1564

    2011

  5. [13]

    Eswar, V

    S. Eswar, V. Rao and A. K. Saibaba, Bayesian D-optimal experimental designs via column subset selection,arXiv preprint arXiv:2402.16000

    arXiv

  6. [14]

    A. K. Kelmans and B. N. Kimelfeld, Multiplicative submodularity of a matrix’s principal minor as a function of the set of its rows and some combinatorial applications,Discrete Mathematics,44(1983), 113–116

    1983

  7. [15]

    Krause and D

    A. Krause and D. Golovin, Submodular function maximization.,Tractability,3(2014), 3

    2014

  8. [16]

    Krause, A

    A. Krause, A. Singh and C. Guestrin, Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies,Journal of Machine Learning Research,9

  9. [17]

    Kullback and R

    S. Kullback and R. Leibler, On information and sufficiency,The Annals of Mathematical Statistics,22(1951), 79–86

    1951

  10. [18]

    Leskovec, A

    J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen and N. Glance, Cost-effective outbreak detection in networks, inProceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, 2007, 420–429

    2007

  11. [19]

    B. D. MacCluer,Elementary functional analysis, vol. 253, Springer, 2009

    2009

  12. [20]

    Manning and H

    C. Manning and H. Schutze,Foundations of statistical natural language processing, MIT press, 1999

    1999

  13. [21]

    Minoux, Accelerated greedy algorithms for maximizing submodular set functions, inOp- timization Techniques(ed

    M. Minoux, Accelerated greedy algorithms for maximizing submodular set functions, inOp- timization Techniques(ed. J. Stoer), Springer Berlin Heidelberg, Berlin, Heidelberg, 1978, 234–243. 14 ALEN ALEXANDERIAN AND STEVEN MAIO

    1978

  14. [22]

    Mirzasoleiman, A

    B. Mirzasoleiman, A. Badanidiyuru, A. Karbasi, J. Vondr´ ak and A. Krause, Lazier than lazy greedy, inProceedings of the AAAI Conference on Artificial Intelligence, 2015

    2015

  15. [23]

    G. L. Nemhauser, L. A. Wolsey and M. L. Fisher, An analysis of approximations for maxi- mizing submodular set functions—I,Mathematical programming,14(1978), 265–294

    1978

  16. [24]

    Reed and B

    M. Reed and B. Simon,Methods of modern mathematical physics: Functional analysis, vol. 1, Gulf Professional Publishing, 1980

    1980

  17. [25]

    Schrijver,Combinatorial optimization: polyhedra and efficiency, no

    A. Schrijver,Combinatorial optimization: polyhedra and efficiency, no. 24 in Algorithms and combinatorics, Springer, Berlin Heidelberg New York, 2003

    2003

  18. [26]

    Shamaiah, S

    M. Shamaiah, S. Banerjee and H. Vikalo, Greedy sensor selection: Leveraging submodularity, in49th IEEE Conference on Decision and Control (CDC), 2010, 2572–2577

    2010

  19. [27]

    Simon, Notes on infinite determinants of hilbert space operators,Advances in Mathematics, 24(1977), 244–273

    B. Simon, Notes on infinite determinants of hilbert space operators,Advances in Mathematics, 24(1977), 244–273

    1977

  20. [28]

    Simon,Trace Ideals and Their Applications, vol

    B. Simon,Trace Ideals and Their Applications, vol. 120 of Mathematical Surveys and Mono- graphs, 2nd edition, American Mathematical Society, Providence, RI, 2005

    2005

  21. [29]

    A. M. Stuart, Inverse problems: A Bayesian perspective,Acta Numerica,19(2010), 451–559

    2010

  22. [30]

    Uci´ nski,Optimal measurement methods for distributed parameter system identification, Systems and Control Series, CRC Press, Boca Raton, FL, 2005

    D. Uci´ nski,Optimal measurement methods for distributed parameter system identification, Systems and Control Series, CRC Press, Boca Raton, FL, 2005. AppendixA.Proof of Lemma 5.1. Proof.Note that GG ∗ and G∗G belong toL + sym(M) andL + sym(K), respectively. It is straightforw...

    2005

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.