pith. sign in

arxiv: 1907.00892 · v1 · pith:IRA5EACKnew · submitted 2019-07-01 · 📡 eess.SP

Sampling And Reconstruction Of Diffusive Fields On Graphs

Siddartha Reddy , Sundeep Prabhakar Chepuri This is my paper

Pith reviewed 2026-05-25 11:41 UTC · model grok-4.3

classification 📡 eess.SP
keywords diffusive fieldsgraph samplingheat diffusionsource localizationsignal reconstructionsubsampled observationsgraph Laplacianrecovery formulas
0
0 comments X

The pith

Diffusive fields on graphs can be recovered exactly from subsampled vertex observations using the heat equation model without band-limiting or sparsity constraints.

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

The paper shows that by modeling diffusion via the heat equation on a graph Laplacian, the full field and its driving sources can be reconstructed from time series at far fewer vertices than the graph size. Temporal samples at observed locations compensate for the unobserved ones, yielding exact recovery when data is noiseless. This holds without band-limiting or sparsity when diffusion is driven by either an initial condition or a constant external input. When both drive the process, band-limiting on one component allows recovery. The method is demonstrated by localizing hot spots on a metal plate modeled as a graph.

Core claim

When the underlying driving sources are modeled as an initial field or external input, the sources (hence the diffusive field) can be recovered from the subsampled observations without imposing any band-limiting or sparsity constraints. When the diffusion is induced by both the initial field and external input, then the field and sources can be recovered from the subsampled observations, however, by imposing band-limiting constraints on either the initial field or external input. For heat diffusion on graphs, we can compensate for the unobserved vertices with the temporal samples at the observed vertices. If the observations are noiseless, then the recovery is exact. Nonetheless, the entwick

What carries the argument

The heat diffusion equation on the known graph Laplacian with time-invariant external input, which yields explicit recovery formulas from subsampled time series.

Load-bearing premise

The diffusion process must exactly follow the standard heat equation on the known graph Laplacian with a time-invariant external input.

What would settle it

A case where the graph Laplacian is known, the true process obeys the heat equation, yet the derived least-squares estimator applied to subsampled observations fails to recover the field or sources accurately.

read the original abstract

In this paper, the focus is on the reconstruction of a diffusive field and the localization of the underlying driving sources on arbitrary graphs by observing a significantly smaller subset of vertices of the graph uniformly in time. Specifically, we focus on the heat diffusion equation driven by an initial field and an external time-invariant input. When the underlying driving sources are modeled as an initial field or external input, the sources (hence the diffusive field) can be recovered from the subsampled observations without imposing any band-limiting or sparsity constraints. When the diffusion is induced by both the initial field and external input, then the field and sources can be recovered from the subsampled observations, however, by imposing band-limiting constraints on either the initial field or external input. For heat diffusion on graphs, we can compensate for the unobserved vertices with the temporal samples at the observed vertices. If the observations are noiseless, then the recovery is exact. Nonetheless, the developed least squares estimators perform reasonably well with noisy observations. We apply the developed theory for localizing and recovering hot spots on a rectangular metal plate with a cavity.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper claims that diffusive fields on arbitrary graphs, governed by the heat equation driven by an initial field and/or time-invariant external input, can be exactly recovered (along with source localization) from noiseless time-series observations at a significantly smaller subset of vertices, without band-limiting or sparsity constraints when only one driver is present (or with band-limiting on one when both are present). It derives recovery formulas and least-squares estimators for the noisy case, and demonstrates the approach on hot-spot localization for a rectangular metal plate with a cavity.

Significance. If the central recovery claims hold under the stated model, the work would allow spatial undersampling to be compensated purely by temporal sampling at observed nodes, extending graph signal processing to diffusive processes without conventional constraints. The exact noiseless recovery and practical noisy performance, together with the physical application example, would be notable strengths for sensor-network and diffusion-modeling applications.

major comments (2)
  1. [Abstract] Abstract and §1: the central claim that recovery is possible 'without imposing any band-limiting or sparsity constraints' for 'arbitrary graphs' and a 'significantly smaller subset' is not guaranteed, because uniqueness requires that the linear map from initial condition x0 (or constant input u) to the observations y(t)=S exp(-t L) x0 (or the forced response) be injective. This holds if and only if no eigenvector v of the graph Laplacian satisfies S v =0; the condition is not automatic for arbitrary graphs and proper subsets S (e.g., any eigenvector localized on unobserved vertices lies in the kernel). The manuscript must explicitly state and verify this observability condition for the no-constraint formulas to be valid.
  2. [§3–4] The derivations of the recovery formulas (presumably in §3–4) appear to proceed by inverting the subsampled diffusion operator without discussing rank or kernel conditions; if the observability matrix is rank-deficient, the least-squares estimator will be under-determined and the 'exact recovery' claim fails. This is load-bearing for the main result.
minor comments (1)
  1. [Application section] The application to the metal-plate example would benefit from an explicit statement of how the graph Laplacian is constructed from the finite-element discretization and how the cavity affects the unobserved vertices.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive report. The comments correctly identify that our recovery claims rely on an implicit observability condition that must be stated explicitly. We will revise the manuscript to address both points.

read point-by-point responses

  1. Referee: [Abstract] Abstract and §1: the central claim that recovery is possible 'without imposing any band-limiting or sparsity constraints' for 'arbitrary graphs' and a 'significantly smaller subset' is not guaranteed, because uniqueness requires that the linear map from initial condition x0 (or constant input u) to the observations y(t)=S exp(-t L) x0 (or the forced response) be injective. This holds if and only if no eigenvector v of the graph Laplacian satisfies S v =0; the condition is not automatic for arbitrary graphs and proper subsets S (e.g., any eigenvector localized on unobserved vertices lies in the kernel). The manuscript must explicitly state and verify this observability condition for the no-constraint formulas to be valid.

    Authors: We agree that the exact-recovery formulas are valid only when the subsampled diffusion operator is injective, i.e., when no Laplacian eigenvector lies in the kernel of the sampling matrix S. Although the derivations in the paper implicitly rely on this property, the manuscript does not state the condition explicitly. In the revision we will add a clear statement of the observability requirement in the abstract and §1, together with a brief verification for the graphs and sampling sets used in the numerical examples. revision: yes

  2. Referee: [§3–4] The derivations of the recovery formulas (presumably in §3–4) appear to proceed by inverting the subsampled diffusion operator without discussing rank or kernel conditions; if the observability matrix is rank-deficient, the least-squares estimator will be under-determined and the 'exact recovery' claim fails. This is load-bearing for the main result.

    Authors: The closed-form recovery expressions and the least-squares estimators in §§3–4 are obtained by inverting (or pseudo-inverting) the relevant linear maps; these steps are valid only when the maps have full column rank. We will revise §§3–4 to include an explicit discussion of the required rank/observability conditions and to qualify the exact-recovery statements accordingly. revision: yes

Circularity Check

0 steps flagged

No circularity; recovery derived from explicit diffusion dynamics

full rationale

The paper models the diffusive field via the standard heat equation on the known graph Laplacian (with initial condition or time-invariant input) and derives recovery formulas by solving the resulting linear system from the subsampled continuous-time observations y(t) = S exp(-t L) x0 (or forced response). This is a direct consequence of the matrix exponential solution to the ODE, not a fit or redefinition that presupposes the output. No self-citation load-bearing steps, ansatz smuggling, or renaming of known results appear; the observability condition for uniqueness is a standard linear-algebra requirement implicit in any such inverse problem but does not reduce the derivation to its inputs by construction. The paper is self-contained against the external diffusion model.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the standard graph heat-diffusion model; no free parameters, invented entities, or ad-hoc axioms beyond the usual Laplacian construction are introduced in the abstract.

axioms (1)
  • domain assumption Diffusion on the graph is governed by the heat equation using the graph Laplacian with time-invariant external input.
    This modeling choice is invoked to obtain the recovery formulas from subsampled observations.

pith-pipeline@v0.9.0 · 5718 in / 1163 out tokens · 46409 ms · 2026-05-25T11:41:06.636135+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    INTRODUCTION Graph signal processing extends tools from classical signa l process- ing to deal with data defined on networks and other irregular d o- mains [1–3]. We often come across such datasets in many diver se applications such as environmental sensing, traffic monitoring, map- ping the human brain [4], cybersecurity [5], and social netw orks, to list ...

    work page

  2. [2]

    , vN } and E represent the vertex set and edge set, respectively

    GRAPH SIGNALS Consider an undirected graph G = {V, E } with N vertices (or nodes), where V = {v1, v2, . . . , vN } and E represent the vertex set and edge set, respectively. Let us denote the graph Laplacia n matrix associated with G as L ∈ RN×N . A graph signal is a function x : V → C with x(v) being the value of the function at vertex v ∈ V . Let us col...

    work page

  3. [3]

    DATA MODEL Let us consider a signal x(D, t) in a physical domain D and temporal domain t. We will assume that x(D, t) obeys the heat equation ∂x(D, t) ∂t = α∇ 2x(D, t) + q(D), (3) where ∇ 2 is the Laplace operator, α is the diffusion constant, and q(D) is the external time-invariant input. When t = 0 , x(0) = x(D, 0) represents the initial field distributi...

    work page

  4. [4]

    More importantly, we do not impose any band-limiting constraints on the sources

    DIFFUSION FIELD INDUCED BY x(0) OR q In this section, we will develop a simple least squares estim ator for reconstructing the diffusion field induced by x(0) or q from the sub- sampled data matrix Y . More importantly, we do not impose any band-limiting constraints on the sources. This means that the sources may be sparse in the vertex domain and can mode...

    work page

  5. [5]

    Although we restrict q to be bandlimited, we do not impose any band-limiting or othe r structural constraints on x(0)

    DIFFUSION FIELD INDUCED BY x(0) AND q In this section, we consider the case in which the diffusion fi eld is induced by x(0) and a bandlimited time-invariant input q, and provide a simple least squares estimator to recover the unde rlying sources from the subsampled data matrix Y . Although we restrict q to be bandlimited, we do not impose any band-limitin...

    work page

  6. [6]

    We use the partial differential equation toolbox from MA TLAB to mesh the surface

    NUMERICAL EXPERIMENTS In this section, we apply the developed theory of graph sampl ing for reconstructing diffusive fields induced by hot spots on a met al block with a cavity. We use the partial differential equation toolbox from MA TLAB to mesh the surface. The generated mesh with N = 134 vertices is shown in Fig. 1. We observe K = 32 vertices uniformly...

    work page

  7. [7]

    The sampled vertices are also indicated in Fig. 1. We presen t results for the following two cases: (i) diffusive field indu ced by x(0), and (ii) diffusive field induced by x(0) and q. As discussed in Section 4, to recover diffusive fields induce d by x(0) with q = 0, we do not require any band-limiting constraints. To demonstrate this, for x(0), we use a v...

    work page

  8. [8]

    CONCLUDING REMARKS In this paper, we discussed the sampling and recovery of diff u- sive fields on graphs induced by possibly non-bandlimited so urces. When the diffusion field is induced by an initial field or a time - invariant external input, we can localize and recover the so urces by sampling a significantly smaller subset of nodes uniforml y in time wit...

    work page

  9. [9]

    Graph signal processing: Overview, challeng es, and applications,

    A. Ortega, P . Frossard, J. Kovaˇ cevi´ c, J. M. Moura, and P. V an- dergheynst, “Graph signal processing: Overview, challeng es, and applications,” Proceedings of the IEEE , vol. 106, no. 5, pp. 808–828, 2018

    work page 2018

  10. [10]

    The emerging field of signal processing on graphs: Extending high-dimensional data analysis to net - works and other irregular domains,

    D. I. Shuman, S. K. Narang, P . Frossard, A. Ortega, and P . V andergheynst, “The emerging field of signal processing on graphs: Extending high-dimensional data analysis to net - works and other irregular domains,” IEEE Signal Process. Mag., vol. 30, no. 3, pp. 83–98, 2013

    work page 2013

  11. [11]

    Big data analysis with si gnal processing on graphs: Representation and processing of mas - sive data sets with irregular structure,

    A. Sandryhaila and J. M. Moura, “Big data analysis with si gnal processing on graphs: Representation and processing of mas - sive data sets with irregular structure,” IEEE Signal Process. Mag., vol. 31, no. 5, pp. 80–90, 2014

    work page 2014

  12. [12]

    Graph frequency analysis of brain signals,

    W. Huang, L. Goldsberry, N. F. Wymbs, S. T. Grafton, D. S. Bassett, and A. Ribeiro, “Graph frequency analysis of brain signals,” IEEE Journ. of Sel. Topics in Signal Process., vol. 10, no. 7, pp. 1189–1203, 2016

    work page 2016

  13. [13]

    Detecting sources of computer viru ses in networks: theory and experiment,

    D. Shah and T. Zaman, “Detecting sources of computer viru ses in networks: theory and experiment,” in ACM SIGMETRICS Performance Evaluation Review, vol. 38, no. 1. ACM, 2010, pp. 203–214

    work page 2010

  14. [14]

    Detecting multiple informa tion sources in networks under the sir model,

    Z. Chen, K. Zhu, and L. Ying, “Detecting multiple informa tion sources in networks under the sir model,” IEEE Transactions on Network Science and Engineering , vol. 3, no. 1, pp. 17–31, 2016

    work page 2016

  15. [15]

    D is- crete signal processing on graphs: Sampling theory,

    S. Chen, R. V arma, A. Sandryhaila, and J. Kovaˇ cevi´ c, “D is- crete signal processing on graphs: Sampling theory,” IEEE Trans. Signal Process., vol. 63, no. 24, pp. 6510–6523, 2015

    work page 2015

  16. [16]

    Graph sampling with and without input priors,

    S. P . Chepuri, Y . C. Eldar, and G. Leus, “Graph sampling with and without input priors,” in Proc. of the IEEE Interna- tional Conference on Acoustics, Speech and Signal Processi ng (ICASSP), 2018, pp. 4564–4568

    work page 2018

  17. [17]

    Sampl ing of graph signals with successive local aggregations,

    A. G. Marques, S. Segarra, G. Leus, and A. Ribeiro, “Sampl ing of graph signals with successive local aggregations,” IEEE Trans. Signal Process., vol. 64, no. 7, pp. 1832–1843, 2015

    work page 2015

  18. [18]

    Graph sampling for covarianc e es- timation,

    S. P . Chepuri and G. Leus, “Graph sampling for covarianc e es- timation,” IEEE Transactions on Signal and Information Pro- cessing over Networks, vol. 3, no. 3, pp. 451–466, 2017

    work page 2017

  19. [19]

    Distributed spatio-temporal sam- pling of diffusion fields from sparse instantaneous sources ,

    Y . M. Lu and M. V etterli, “Distributed spatio-temporal sam- pling of diffusion fields from sparse instantaneous sources ,” in Proc. of the 3rd IEEE International W orkshop on Computa- tional Advances in Multi-Sensor Adaptive Processing (CAM- SAP), 2009, pp. 205–208

    work page 2009

  20. [20]

    Sampl ing and reconstructing diffusion fields with localized sources ,

    J. Ranieri, A. Chebira, Y . M. Lu, and M. V etterli, “Sampl ing and reconstructing diffusion fields with localized sources ,” in Proc. of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) , 2011, pp. 4016– 4019

    work page 2011

  21. [21]

    Time estimation for heat d iffu- sion on graphs,

    O. Teke and P . V aidyanathan, “Time estimation for heat d iffu- sion on graphs,” in Proc. of the 51st Asilomar Conference on Signals, Systems, and Computers , 2017, pp. 1963–1967

    work page 2017

  22. [22]

    A generalized uncertainty p rin- ciple and sparse representation in pairs of RN bases,

    A. Bruckstein and M. Elad, “A generalized uncertainty p rin- ciple and sparse representation in pairs of RN bases,” IEEE Trans. Inf. Theory, vol. 48, pp. 2558–2567, 2002

    work page 2002

  23. [23]

    Discrete signal proces sing on graphs,

    A. Sandryhaila and J. M. Moura, “Discrete signal proces sing on graphs,” IEEE Trans. Signal Process. , vol. 61, no. 7, pp. 1644–1656, 2013

    work page 2013

  24. [24]

    Strang, Differential Equations And Linear Algebra

    G. Strang, Differential Equations And Linear Algebra . Wellesley-Cambridge Press, 2015

    work page 2015

  25. [25]

    On the uniqueness of mult i- linear decomposition of N-way arrays,

    N. D. Sidiropoulos and R. Bro, “On the uniqueness of mult i- linear decomposition of N-way arrays,” Journal of Chemomet- rics: A Journal of the Chemometrics Society , vol. 14, no. 3, pp. 229–239, 2000

    work page 2000

  26. [26]

    Sparse sensing for statistic al infer- ence,

    S. P . Chepuri and G. Leus, “Sparse sensing for statistic al infer- ence,” F oundations and TrendsR⃝ in Signal Processing, vol. 9, no. 3–4, pp. 233–368, 2016

    work page 2016

  27. [27]

    Sparse sampling for inverse problems with tensors,

    G. Ortiz-Jim´ enez, M. Coutino, S. P . Chepuri, and G. Leu s, “Sparse sampling for inverse problems with tensors,” IEEE Trans. Signal Process., vol. 67, no. 12, pp. 3272–3286, 2019

    work page 2019