CS Paper Radar

A Nonuniform-Sampling Theory for Static Multi-Threshold Sampling

Ao Qiu, Qingguo Xie

eess.SP cs.ITphysics.ins-detphysics.med-ph ·submitted 2026-08-27 06:49 UTC · v1
theory

Abstract

Multi-Threshold (MT) sampling fixes voltage levels and records when a waveform crosses them. The resulting signal-generated event stream is governed not by a prescribed clock but by the nonuniform geometry of the realized crossing set. Within classical nonuniform sampling, we develop a retained-event MT theory for static, uniformly spaced thresholds. For a realized retained MT time set, Beurling's weak-limit theorem gives the exact necessary-and-sufficient condition for stable sampling of $PW_Ω$. For a fixed signal class, the same principle gives the a priori criterion: uniform stable MT sampling is equivalent to Bernstein uniqueness for every set in the class weak-limit hull. This criterion reduces to computable forms under structured priors. Periodic templates give finite fiber/rank tests, periodic-gap streams give a Shannon-type complete-interpolation boundary and a stable-sampling density rule, and finite-state gap priors reduce noncritical certification to a maximum-cycle-mean condition. Kadec-type local certificates, retained-density bounds, and finite-matrix tests provide practical sufficient conditions for finite active records, while conditional perturbation bounds quantify how jitter, front-end noise, and threshold error consume a clean sampling margin under event correspondence. The theory also identifies the unavoidable boundary of this model: unrestricted finite-energy retained MT records have zero full-line lower Beurling density and therefore cannot provide a universal prior-free sampling theorem for $PW_Ω$. Within retained-event point sampling, the MT recovery question is resolved precisely: exact recovery is governed by event-set geometry, computable guarantees require structural priors or finite-dimensional/tail assumptions, and the unrestricted static finite-energy problem is impossible.

Closest papers

Nearest neighbours by meaning across the whole index.

Multi-Threshold Sampling: Local and Global Parameter Identifiability

eess.SP physics.ins-det ·2026-10-20 ·Ao Qiu, Qingguo Xie
theory similarity 0.60
Abstract

Multi-threshold (MT) sampling records threshold-crossing times for parameter estimation in applications including positron emission tomography, oil well logging, and photon-counting X-ray imaging. We study whether the distribution of recorded crossings uniquely determines the signal parameters and how many thresholds are required for this identifiability. For a fixed MT sampler, we show that the ranks of distribution derivatives with respect to the parameters cannot increase through crossing, timing, and selection. Under suitable regularity assumptions, we characterize local identifiability by a full-rank Jacobian of finitely many event probabilities defined on recorded crossings and establish a necessary and sufficient global identifiability criterion under additional rank and topological assumptions. For a nonhomogeneous Poisson signal model with four intensity parameters, a fixed known single-photon response, and deterministic MT sampling, we prove that four cumulative probabilities of the first recorded crossing time establish local and global identifiability under their respective conditions using a single sufficiently small positive threshold. This attains the minimum number of thresholds for the specified model and sampler. Numerical experiments illustrate these results and reveal weak parameter sensitivity and substantial finite-sample estimation errors when estimation uses these probabilities. The results establish parameter uniqueness while highlighting the role of statistical sensitivity in accurate estimation.

0.12

Multi-Threshold Sampling: Signal Space, Sampling Operators, and First Recorded Crossing-Time Distributions

eess.SP physics.ins-det ·2026-09-10 ·Ao Qiu, Qingguo Xie
theory similarity 0.60
Abstract

Multi-threshold (MT) sampling records crossing times for parameter estimation and waveform reconstruction. We develop signal and observation spaces and stochastic crossing, timing, and selection operators with associated Markov kernels. Finite point measures accommodate variable crossing counts and preserve multiplicity after quantization. For nonhomogeneous Poisson photon arrivals with shared threshold noise, shared timing jitter before quantization, and identity selection, we derive exact first recorded crossing-time distributions. A Poisson series covers general admissible paths with a time-uniform truncation bound. For continuous paths, interval extrema give the exact cumulative distribution function (CDF) and a Fourier representation with contact corrections. A biexponential arrival-intensity and response model admits a two-dimensional first-crossing integral equation on arbitrary finite observation windows, with a unique bounded measurable solution and a Poisson-tail approximation bound. For continuous causal responses with finitely many analytic pieces and bounded first and second branch derivatives, we prove a conditional standard-deviation (SD) limit at first mean crossings with positive slope under relative threshold-noise and fine timing scales. For the biexponential model, its coefficient increases strictly on a parameter-uniform interval and, under a shape condition, up to the first mean peak. Scintillation experiments compare the calculated CDF and conditional SDs with independent waveform simulations on a window extending beyond the single-photon response peak.

0.41

Scalable Triangle Counting: The Threshold Algorithm

cs.DS cs.DB ·2026-09-14 ·Asaf Etgar, Anna Gilbert, Quanquan C. Liu, Andrew McGregor
hot direction similarity 0.53
Abstract

We study one-pass triangle counting on random-order edge streams. We present a remarkably simple algorithm---read edges from the stream until $Q$ triangles are observed in the prefix, then output $Q\,(m/S)^3$ where $S$ is the stopping length---and prove that, when the maximum number of triangles incident to any edge satisfies $η\le T^{2/3}$, this is a $(1\pm\varepsilon)$-approximation of $T$ with probability $1-δ$ using $O(\varepsilon^{-2}\log(1/δ)\, m/T^{1/3})$ memory. Crucially, the algorithm does not need any a priori estimate of $T$, in sharp contrast with state-of-the-art sampling-rate based algorithms (McGregor and Vorotnikova, PODS 2020; Tsourakakis et al., KDD 2009). It also does not need a prescribed memory budget: the stopping rule self-selects the prefix length and can return an estimate before reading the entire stream. The proof rests on a Schudy--Sviridenko concentration argument for an independent-edge-sampling estimator, coupled to the without-replacement prefix produced by the algorithm. On six real temporal streams, the algorithm's stopping prefix follows the predicted cube-root scaling and achieves at most $6\%$ error at a $10\%$ prefix, without using $T$. At a fixed stored-edge budget, variance-reduced reservoir samplers are often more accurate, but only after reading the entire stream. On a separate, much larger, $1.8\times10^9$-edge graph, the threshold algorithm reads $0.46\%$ of the stream and returns $3.8\%$ error, while the strongest reservoir baselines do not finish a pass within the wall-clock cap.

0.34

Sampling of Signals on Multigraphs: From Removable and Uniqueness sets to Spectral Proxies

eess.SP cs.LG ·2026-10-19 ·Alejandro Parada-Mayorga
theory similarity 0.52
Abstract

In this paper, we study the sampling of bandlimited signals on multigraphs, where several graphs with different shift operators are defined on the same set of nodes. Since the shift operators do not commute in general, they admit only a joint block diagonalization, and the frequencies of the multigraph signal model are matrices rather than scalars. Relying on a formal algebraic convolutional signal model, we introduce a notion of frequency and bandwidth for multigraph signals that does not depend on any individual layer, and we extend the notions of removable and uniqueness sets to multigraphs. We prove that the optimality of a sampling set is determined exclusively by the common Fourier basis and its invariant subspaces, and not by any individual layer, although the individual layers provide computable sufficient conditions that certify a sampling set as a uniqueness set. Since identifying which layers provide reliable certificates requires spectral information, we propose an aggregate operator that pools the information of all the layers, is computable directly from the shift operators, and certifies uniqueness without any assumption on the individual layers. This operator leads to a greedy sampling algorithm that does not require computing the joint block diagonalization. Numerical experiments on multigraphs whose layers order the frequencies inconsistently show that the proposed algorithm selects better-conditioned sampling sets and attains lower reconstruction errors than single-layer methods.

0.28

On the VC Dimension of Autoregressive Linear Threshold Functions

cs.LG ·2026-10-27 ·Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel
theory similarity 0.51
Abstract

Linear threshold functions (LTFs) are a canonical class of Boolean predictors. In the autoregressive setting, the same LTF reads the most recent $d$ bits, generates the next bit, and returns the bit produced after $T$ steps. While the one-step class has VC dimension $d$, for general $T$ the counting upper bound is $O(d^2)$. We prove that the VC dimension is $Θ(d^2)$ for every $T\ge d^2$, resolving the quadratic gap for deterministic autoregressive LTFs. We then adapt the same technique to show an exponential separation between deterministic and stochastic autoregressive models: replacing the sign of LTFs by logistic sampling can increase the VC dimension of the final majority prediction class from quadratic to exponential in $d$.

0.50

A complete characterization of sequential testability and change detectability in i.i.d. models

cs.IT math.STeess.SPstat.ME+1 ·2026-09-04 ·Aaditya Ramdas
similarity 0.50
Abstract · 33 pages

We give a necessary and sufficient condition for the existence of power-one sequential tests in an i.i.d. composite testing problem. A level-\(α\) test with power one against every alternative exists if and only if the alternatives are separated from the null by a countable family of finite-block events. We provide other equivalent conditions using randomized fixed-sample tests, bounded finite-block scores, e-processes, reduced-filtration test supermartingales, and a countable cover whose finite-block weak-$*$ closed convex hulls are positively separated in total variation. As a bonus, the constructive proof yields tests have pointwise expected sample size \(O_Q(\log(1/α))\). Exactly the same conditions also characterize i.i.d.\ change detectability under optional-horizon average-run-length control: for every \(η>0\), they are equivalent to an alarm family \((T_γ)_{γ\ge1}\) satisfying \(\Prob_{P^\infty}(T_γ\leσ)\le \E_{P^\infty}σ/γ\) for every null law and every stopping time \(σ\). In fact, when these conditions hold, we can construct a single e-detector such that every null-law average run length lies between \(γ\) and \((1+η)γ+1\), and having robust Lorden delay \(O_Q(\logγ)\).

0.22

Provably adaptive sampling with uniform and remasking discrete diffusion models

cs.LG cs.ITmath.STstat.ML ·2026-08-24 ·Daniil Dmitriev, Zhihan Huang, Yuting Wei
similarity 0.50
Abstract · 37 pages, 4 figures

Discrete diffusion models offer a promising alternative to autoregressive generation by enabling parallel updates, but their sampling efficiency can depend strongly on the choice of the forward process and the sampler. For the uniform forward process, existing lower bounds for the standard $τ$-leaping sampler scale linearly with the ambient dimension $d$, raising the question of whether this dependence is intrinsic to the forward process. We answer this question in the negative. We consider a first-order sampler based on the leave-one-out denoiser for uniform and remasking processes whose coordinate updates can be performed in parallel. In both cases, the sampler can correct denoising mistakes during the sampling process, which becomes necessary when many coordinates are updated together. Our main result establishes an adaptive sampling guarantee: up to logarithmic factors, $N = O(\mathrm{DTC}(X_0) / \varepsilon)$ discretization steps suffice to achieve sampling error $O(\varepsilon_{\mathrm{score}}+\varepsilon)$, where $\varepsilon_{\mathrm{score}}$ is the error in score estimation. Thus, the sampling complexity is governed by the intrinsic dependence structure of the target distribution, as measured by its dual total correlation $\mathrm{DTC}(X_0)$, rather than directly by the ambient dimension $d$. Our analysis proceeds through a Bayes-optimal auxiliary sampler that separates discretization error from score-estimation error. We also derive an exact information-theoretic representation of the discretization error in terms of the mutual information between different coordinates of the forward process at different times. This representation applies to general forward processes and, in the uniform and remasking cases, can be controlled by $\mathrm{DTC}(X_0)$. Numerical experiments on structured synthetic distributions illustrate the predicted dimension-adaptive behavior.

0.60

Beyond Observability: Sharp Sample Bounds for Minimax State Reconstruction

eess.SY ·2026-10-19 ·Jerzy Baranowski
similarity 0.50
Abstract · Submitted to the International Journal of Control. 6 figures

We study how many output samples match the worst-case state reconstruction error obtainable from a continuous history under bounded measurement noise. For observable scalar-output linear time-varying systems with $n$ states, $n$ samples suffice for exact reconstruction, whereas at most $n^2$ attain the continuous-history minimax error in the $\ell_\infty$ norm. An explicit construction proves sharpness even for real-analytic systems. For time-invariant systems, strict total positivity yields one $n$-sample schedule optimal for every state coordinate; endpoint-observed tridiagonal cooperative chains satisfy this conclusion in physical coordinates. Interior sensing behaves differently: an explicit three-state family requires four samples despite positivity and distinct real eigenvalues. The strict three-state gap persists under small stabilizing damping. A nilpotent four-state example and an interval proof for a six-state mechanical system give gaps. The results identify how temporal sampling and the prescribed state-error geometry determine the measurements required for minimax reconstruction. Time-domain experiments illustrate the resulting estimation bounds.

0.28