Weighted microscopic image reconstruction

Assume we inspect a specimen represented as a collection of points and our task is to learn a physical value associated with each point. However, performing a direct measurement is impossible since it damages the specimen. The alternative is to employ aggregate measuring techniques (e.g., CT or MRI), whereby measurements are taken over subsets of points, and the exact values at each point are subsequently extracted by computational methods. In the Minimum Surgical Probing problem (MSP) the inspected specimen is represented by a graph G and a vector ℓ ∈ R n that assigns a value ℓ i to each vertex i. An aggregate measurement (called probe) centred at vertex i captures its entire neighbourhood, i.e., the outcome of a probe at i is P i = ∑ j ∈ N ( i ) ∪ { i } ℓ j where N ( i ) is the open neighbourhood of vertex i. Bar-Noy et al. (2022) gave a criterion whether the vector ℓ can be recovered from the collection of probes P = { P v ∣ v ∈ V ( G ) } alone. However, there are graphs where the vector ℓ cannot be recovered from P alone. In these cases, we are allowed to use surgical probes. A surgical probe at vertex i returns ℓ i. The objective of MSP is to recover ℓ from P and G using as few surgical probes as possible.

In this paper, we introduce the Weighted Minimum Surgical Probing (WMSP) problem in which a vertex i may have an aggregation coefficient w i, namely P i = ∑ j ∈ N ( i ) ℓ j + w i ℓ i. We show that WMSP can be solved in polynomial time. Moreover, we analyse the number of required surgical probes depending on the weight vector w. For any graph, we give two boundaries outside of which no surgical probes are needed to recover the vector ℓ. The boundaries are connected to the (Signless) Laplacian matrix.

In addition, we consider the special case where w = 0 → and explore the range of possible behaviour of WMSP by determining the number of surgical probes necessary in certain graph families, such as trees and various grid graphs.