PaperlayerView exact revision on arXiv

Source-linked AI summary

Movement Stability of D-Optimal Sensor Placement Under Projector Perturbations

Isabella Yin, Laura P. Schaposnik

arXiv:2610.08152v1math.OCeess.SP

TL;DR

When a changing signal model alters a D-optimal sensor selection, even one changed coordinate can require a sensor to cross the graph. The paper measures movement by bottleneck matching and proves a distance-margin stability guarantee, while a weighted path shows why separation information is needed.

  • Problem

    Set replacement counts do not measure physical displacement: one changed sensor can have to cross the graph.

    Source: §1 · p. 2

  • Method

    The paper uses bottleneck matching on a fixed mobility graph and a distance margin to bound movement under projector perturbations.

    Source: §1 · p. 2

  • Results

    The theorem confines every new maximizer when drift is small and the margin exceeds the budget; a weighted path permits an n−1-hop jump under an arbitrarily small perturbation.

    Source: §1 · p. 2, §9 · p. 19

  • Takeaways & Limitations

    Under stated conditions, local P-hop and Voronoi restrictions can retain a global optimum, and the framework extends to oversampled, regularized, and dictionary criteria.

    Source: §1 · p. 2

    The results certify exact maximizers of the projector criterion associated with a learned subspace, not placements from the described approximate independent greedy updates.

    Source: §7.3 · p. 16

Abstract

from arXiv · show

In time-varying D-optimal subset selection, the number of replaced coordinates does not measure physical displacement: when the optimal selection for a set of mobile sensors changes, a single sensor may have to cross the entire graph. We therefore measure movement by a bottleneck matching distance on a fixed mobility graph, and define the distance margin at radius P as the smallest old-objective loss among configurations farther than P from the current maximizer. Our main result shows that if the projector drift is small and the distance margin at a chosen radius exceeds an explicit threshold, then every maximizer of the new objective lies within that radius, without tie-breaking rules or uniform conditioning assumptions over subsets. Moreover, we show that separation information of this kind is genuinely needed: a weighted-path construction shows that, at a fixed baseline eigengap, an arbitrarily small perturbation can move an optimal sensor from one end of the graph to the other, so no bound depending only on perturbation size and eigengap can vanish with the perturbation. We also give a finite certificate, conditions under which local and Voronoi restrictions retain a global optimum, and oversampled and regularized extensions, and we identify the learned dictionary criteria to which the results apply.

1 Introduction

When a signal model changes, a one-sensor change in the optimal set can require movement across the graph, so replacement counts do not capture mobile-sensor cost. The paper studies movement stability, when local restrictions retain a global optimum, and what can be certified about these questions.

1 Introduction

  • An arbitrarily small weight change on a path can move the optimal sensor n−1 hops, although only one coordinate changes.This shows why set replacement and physical movement are different measures.Source: §1 · p. 2
  • The analysis addresses physical movement and local-region feasibility, but does not establish that independent per-sensor greedy updates solve the centralized D-optimal problem.The paper makes no claim that those updates recover the close optimum.Source: §1 · p. 2
  • The paper bounds movement of every new maximizer using projector drift, conditioning at the current optimizer, and a distance margin.For random ensembles, the probability of any optimizer change is controlled by the lower tail of the second-best objective gap.Source: §1 · p. 2
  • A weighted-path construction shows that perturbation size and eigengap alone cannot yield a uniform movement bound that vanishes with perturbation.The construction holds at fixed eigengap.Source: §1 · p. 2
  • The paper gives conditions under which P-hop neighborhoods intersected with Voronoi regions retain a global optimum, and extends results to oversampled and regularized settings and dictionary criteria.It also gives a finite-graph distance-margin certificate testable using perfect matchings.Source: §1 · p. 2

2 Background and Setup

The paper combines a fixed graph that measures sensor movement with a potentially changing signal subspace that defines D-optimal objectives. It situates this framework among related literatures and specifies the matching distance and distance margin used in later results.

2.1 Related work

  • Prior work studies fixed-model graph sampling, D-optimal subset selection, subspace perturbation, and dynamic placement; this paper studies how maximizing configurations move as the subspace changes.The framework uses projector-level perturbation control, including for subspaces from learned dictionaries.Source: §2.1 · p. 3

2.2 Setup

  • The framework separates a fixed mobility graph, which determines reconfiguration cost, from a changing low-dimensional subspace, encoded by an orthogonal projector.In the graph-signal application, the support is fixed while edge weights may change.Source: §2.2 · pp. 3–4
  • Bottleneck matching measures the smallest radius allowing a bijection between old and new sensor positions; the distance margin is the smallest old-objective loss among configurations beyond radius P.The undersampled setup needs no genericity assumption on graph weights or projector entries for nondegeneracy, and no tie-breaking is needed for new maximizers.Source: §2.2 · pp. 4–5

3 Movement Stability Under Projector Perturbations

For undersampled selection, the paper converts projector drift into a bound on the old-objective loss of every new maximizer, then uses the distance margin to bound movement. It also derives persistence and perturbation results while avoiding uniform conditioning assumptions over all configurations.

3 Movement Stability Under Projector Perturbations

  • Projector drift bounds changes in compressed matrices; optimality transfers a determinant lower bound to each new maximizer, enabling comparison under the old objective.A determinant bounded away from zero supplies a lower bound on the smallest eigenvalue in the undersampled case.Source: §3 · pp. 5–6
  • If the distance margin at radius P exceeds the perturbation budget, every new maximizer lies within bottleneck distance P of the reference maximizer.The theorem assumes undersampling and smallness conditions; conditioning is required at the reference optimizer, not uniformly over all configurations.Source: §3 · pp. 6–7
  • The determinant-based movement bound uses an alternative condition, and its constant 6m is not claimed to be sharp.The bound also yields a second-best-gap criterion for average-case persistence of a unique optimizer.Source: §3 · p. 7
  • Under a stated lower-tail assumption on the second-best gap, the probability of an optimizer change is controlled by the perturbation budget.For Laplacian perturbations with fixed m and uniformly positive eigengap and optimizer conditioning, the budget is O(ε); the lower-tail exponent for natural models remains open.Source: §3 · pp. 7–8

4 Laplacian Perturbations and Why Projector Drift Alone Is Not Enough

For Laplacian perturbations, the section specializes projector-based movement stability and shows why perturbation size and eigengap alone cannot guarantee small movement. On positively weighted paths, arbitrarily small changes can move the optimizer across the graph while the baseline eigengap stays fixed.

4 Laplacian Perturbations and Why Projector Drift Alone Is Not Enough

  • Corollary 4.3 specializes the projector-based movement guarantee to Laplacian perturbations, using r = 4ε/δ under its stated smallness conditions.The Laplacian setting assumes fixed edges and ε < δ; Davis–Kahan controls projector drift.Source: §4 · pp. 8–9

4.1 Perturbation Size and Eigengap Alone Do Not Bound Movement

  • For every n ≥4, positively weighted paths can keep a fixed baseline eigengap while εk→0 and the optimizer moves n−1.The same construction works under any fixed baseline tie-breaking rule.Source: §4.1 · p. 9
  • The path construction breaks a tie between endpoint optimizers with a small weight change, making one endpoint the unique maximizer for either perturbation sign.At θ = 0 both endpoints maximize; for small nonzero θ the sign selects the endpoint.Source: §4.1 · pp. 9–10
  • The impossibility result relies on a baseline tie and does not establish discontinuity when the baseline optimum is unique and distant competitors are separated.In that tied construction, the distance margin is zero for radii below n−1.Source: §4.1 · pp. 10–11

5 Computing the Distance Margin and Certifying Movement

The distance margin measures the smallest old-objective loss among configurations farther than a chosen matching radius, and its monotonicity supports movement certification. On finite graphs it can be computed by enumeration, with matching tests deciding which configurations lie outside that radius.

5.1 Formulation

  • The distance margin is the old optimum minus the best objective value among configurations farther than P from the reference; it is non-decreasing in P.The far-configuration family shrinks as P increases, so its best objective cannot increase.Source: §5.1 · p. 11
  • A configuration is within matching radius P exactly when the bipartite graph linking pairs at distance at most P has a perfect matching.The matching test can be solved in O(m^2.5) time in the worst case.Source: §5.1 · p. 11

5.2 Computing the Distance Margin by Enumeration

  • Exact finite-graph evaluation enumerates m-subsets, computes their old objectives, and uses matching tests to retain only configurations farther than P.The algorithm returns the smallest objective loss among retained configurations, or +∞ if none exists; exhaustive numerical evaluation is practical for moderate finite instances.Source: §5.2 · p. 11

6 Losslessness of P-Hop and Voronoi Restrictions

A distance-margin condition ensures that every new global maximizer lies within the P-hop matching ball, making the restriction lossless in objective value. The same guarantee can extend to strict Voronoi regions under an assignment condition or sufficient sensor spacing, but local restrictions can lose the optimum without separation.

6 Losslessness of P-Hop and Voronoi Restrictions

  • If the hypotheses of Theorem 3.4 hold and Mt(P) > Bt, every new maximizer lies within the P-hop matching ball, so restricting the search preserves the global optimum.If the global maximizer is unique, the constrained and unconstrained maximizers agree.Source: §6 · p. 12
  • Without the distance-margin condition, a P-hop restriction can exclude the unique perturbed optimum even when the perturbation is arbitrarily small.The weighted-path construction places tied baseline optima at opposite endpoints, then makes one endpoint the unique perturbed maximizer beyond P hops.Source: §6 · p. 12

6.1 Intersection with the Voronoi Region

  • The spacing condition ensures vertices within P hops of a sensor remain in its strict Voronoi cell, making the matching assignment compatible with the local region.The condition is sufficient but not necessary, and the regions are centered at the reference maximizer.Source: §6.1 · p. 13
  • Under Theorem 6.1's hypotheses, the Voronoi restriction is lossless for one sensor or, with multiple sensors, when the stated spacing condition holds.A matching assignment consistent with the strict cells also suffices; the results concern containment of a global maximizer, not whether independent sensor updates find it.Source: §6.1 · p. 13

7 Extensions

The movement-stability framework extends to oversampled and regularized D-optimality and to learned dictionaries. These extensions retain explicit movement bounds under their stated conditions, while dictionary guarantees concern a projector criterion that may differ from raw row-volume selection.

7.1 Oversampled D-Optimality, m ≥K

  • For oversampled D-optimality with m ≥ K, the movement bound applies under Assumption 2.1; under Assumption 4.1, the stated conditions use r = 4ε/δ and threshold 48Kε/(σ⋆,ov_t δ).The sufficient smallness conditions include 4ε/δ ≤ σ⋆,ov_t/8 and 16Kε/(σ⋆,ov_t δ) ≤ log 2.Source: §7.1 · p. 14

7.2 Regularized D-Optimality

  • For regularized D-optimality, if r ≥ ρt and r/τ ≤ 1/2, the movement theorem applies; under Assumption 4.1, it suffices that 4ε/(τδ) ≤ 1/2 and Mτ_t(P) > 16mε/(τδ).The regularized stability bound is uniform over configurations.Source: §7.2 · p. 15

7.3 Dictionaries

  • For a full-column-rank learned dictionary, its column-span projector can be used directly in the framework, with projector drift computed from the two dictionaries and no eigengap estimate needed.For m ≤ K, the criterion is the row-volume criterion for the orthonormalized dictionary, which can differ from raw row-volume selection when m < K.Source: §7.3 · pp. 15–16
  • The guarantees certify movement of exact maximizers of the associated projector criterion, not placements from the independent greedy algorithm; the criteria coincide up to an S-independent factor when sensor count equals dictionary rank.When fewer sensors than atoms are selected, the projector and raw row-volume criteria can choose different sets.Source: §7.3 · p. 16

8 Experiments on Synthetic Graphs

Synthetic experiments examine certificate tightness and the distance-margin curve rather than benchmark performance. Across the eligible perturbation cases, certified radii bound observed movement, often nontrivially, while the illustrative margin curve shows why objective gaps alone omit distance information.

8.1 Protocol and Setup

  • The experiments use six fixed-seed weighted graphs across grid, random-geometric, and two-block community families, with K = 4 and m = 2.The movement graph is the unweighted graph, so edge-weight perturbations do not change the matching distances.Source: §8.1 · pp. 16–17

8.2 Certifying Optimizer Movement on Synthetic Graphs

  • 1,189 of 1,224 cases (97.1%) were eligible, and 1,035 eligible cases (87.0%) had nontrivial certificates; every eligible case had Pact ≤ Pcert.Among eligible cases, the median Pcert − Pact difference was two hops overall and one hop among the 33 cases with positive movement.Source: Figure 1 · p. 17, §8.2 · p. 18
  • Among eligible cases, 561 (47.2%) had integer-radius sharp certificates, including 547 with zero movement; the six baselines cannot be used to rank graph families.Only 14 of the 33 cases with optimizer movement had integer-radius sharp certificates.Source: §8.2 · p. 18

8.3 Distance Margin Curve

  • Configurations with similar objective losses can lie at very different matching distances, so the distance-margin curve retains information that a second-best gap misses.For each integer P, the margin is the smallest objective loss among configurations farther than P; Pcert is the first radius where it exceeds Bt.Source: §8.3 · p. 18, Figure 2 · p. 18

9 Conclusions

The paper develops a geometric stability framework for determinant-based subset selection, measuring sensor movement by bottleneck matching on a fixed graph. It establishes when perturbations preserve bounded movement, shows why a distance margin is needed, and describes extensions, numerical observations, and scope boundaries.

9 Conclusions

  • Small projector perturbations bound every new maximizer's movement when the distance margin exceeds the objective perturbation budget.The framework measures movement by bottleneck matching on a fixed mobility graph.Source: §9 · p. 19
  • A positively weighted path shows that perturbation size and eigengap alone cannot guarantee small movement, even for arbitrarily small perturbations.The construction rules out a uniform bound that vanishes with perturbation size at fixed eigengap.Source: §9 · p. 19
  • Distance margins certify when local restrictions retain a global optimum, with an additional compatibility condition for Voronoi restrictions.Without the distance margin, local restrictions can lose the global optimum under arbitrarily small perturbations.Source: §9 · p. 19
  • The framework extends to oversampled and regularized objectives and to learned-subspace projectors.Under suitable ensemble assumptions, the second-best objective gap controls the probability of optimizer change.Source: §9 · p. 19
  • Positive movement occurred in 33 of 1,189 numerically eligible cases, and the certificate was nontrivial in most tested cases but could be conservative.The observations motivate studying the lower tail of the second-best objective gap in concrete dynamic graph models.Source: §9 · p. 19
  • The framework may apply to environmental monitoring and robotic sensing when movement uses a fixed mobility graph and placement follows a studied determinant criterion.A next step is finding conservative distance-margin lower bounds without enumerating all configurations, beyond the small instances considered.Source: §9 · p. 19
  • The matching distance treats sensors as interchangeable and omits trajectory interactions; heterogeneous capabilities, travel costs, and collision constraints require adapted geometry.Extending guarantees to approximate maximizers is another direction, linking exact-optimum guarantees to practical algorithm outputs.Source: §9 · p. 19

Declarations

The authors acknowledge Magdalen College and the Mathematical Institute at the University of Oxford for hospitality and support during the Visiting Fellowship in which the work was completed.

Declarations

  • LPS acknowledges Magdalen College and Oxford's Mathematical Institute for hospitality and support during the Visiting Fellowship in which the work was completed.Source: Acknowledgements · p. 19

A Notation

The appendix collects the paper's main symbols in tables covering the setting and objectives, movement and certification, and extensions and local restrictions.

A Notation

  • Table 1 collects notation for the setting and objectives.Source: Table 1 · p. 20
  • The movement and certification notation includes the graph-hop radius, bottleneck matching distance, distance margin, projector-drift bound, and certified movement radius.The notation also distinguishes the observed movement of a retained numerical maximizer from the theorem's certified radius.Source: A Notation · p. 20, Table 2 · p. 20
  • Table 3 collects notation for extensions and local restrictions.Source: Table 3 · p. 20
Loading 2610.08152v1…