CS Paper Radar

Beyond Observability: Sharp Sample Bounds for Minimax State Reconstruction

Jerzy Baranowski

eess.SY ·submitted 2026-10-19 13:01 UTC · v1

Abstract

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.

Comment
Submitted to the International Journal of Control. 6 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Singular Sampling in Nonlinear Observability: Higher-Order Minimax Laws and Timing Crossovers

eess.SY ·2026-10-11 ·Jerzy Baranowski
unusual similarity 0.62
Abstract · This work has been submitted to the IEEE for possible publication

We study deterministic bounded-noise state reconstruction for nonlinear systems when the measurement schedule drives the sampled-output map through a rank-deficient configuration. Local reconstruction is governed by the leading pairwise separation order and its corresponding higher-order modulus, which together determine the leading minimax noise-to-state law. For corank-one cubic singular schedules, including overdetermined sampled maps, we derive the exact physical $\ell_\infty$ cubic modulus through quotient geometry in $\mathbb{R}^q/\operatorname{Im}DF$ and show how the required finite jet is computed from trajectory sensitivities. We then prove a uniform signed timing crossover: a transversal timing perturbation has transition scale $\varepsilon=O(δ^{2/3})$, linking the regular, cubic-singular, and fold regimes. A damped pendulum provides closed-form crossover coefficients and exact nonlinear minimax validation, while a four-state downward cart--pole verifies the rectangular theory. The results show that measurement timing can change not only reconstruction conditioning but the exponent governing bounded-noise state uncertainty.

0.48

Identification and Recovery of Linear Dynamics from Partial Trajectories

cs.IT ·2026-10-03 ·Le Gong
similarity 0.59
Abstract

We study the joint recovery of an unknown system matrix $A\in\mathbb R^{n\times n}$ and a rank-$r$ initial-state matrix $X_0\in\mathbb R^{n\times m}$ from partial observations of the state matrices $A^tX_0$, for $t=0,\ldots,T$. Each trajectory is observed at a fixed set of state coordinates, which may differ across trajectories. We derive necessary conditions for identifiability, including obstructions arising from incomplete spatial coverage and insufficient dynamical span, as well as lower bounds on the number of observations. We then characterize the Jacobian of the measurement map, account for the intrinsic symmetry of the low-rank factorization, and establish a rank-certificate principle yielding generic local identifiability. When the trajectories whose initial states form a basis of $\operatorname{range}(X_0)$ are fully observed, we obtain necessary and sufficient rank conditions for global recovery, together with explicit reconstruction formulas. We formulate the joint recovery problem as a nonlinear least-squares problem over the system matrix $A$ and the low-rank factors of $X_0$, and solve it using Adam. Numerical experiments on synthetic and real-world data evaluate the recovery performance under different spatial sampling rates and observation horizons.

0.22

Optimal Low-Rank Quantum State Tomography with Bounded-Sample Joint Measurements

cs.DS quant-phcs.ITcs.LG ·2026-09-09 ·Ashwin Nayak, Xingyu Zhou
theoryhighly cited similarity 0.58
Abstract · 70 pages; v2: minor revisions

We determine the optimal sample complexity of low-rank quantum state tomography when each measurement may act jointly on at most $t$ samples. For sufficiently small $\varepsilon$, estimating an unknown state on $\mathbb{C}^d$ of rank at most $r$ to trace norm error $\varepsilon$ with constant success probability requires, and is achievable with, $$Θ\left(\frac{dr}{\varepsilon^2}\mathop{\mathrm{max}}\left\{1,\frac{r}{\sqrt{t}}\right\}\right)$$ samples. The lower bound allows the protocol to choose each joint measurement adaptively using all previous classical outcomes; the matching upper bound is nonadaptive. Thus joint measurements on at most $t$ samples improve the complexity of algorithms making single-sample measurements by at most a factor $\sqrt{t}$. Further, measuring order $r^2$ samples jointly is necessary and sufficient to attain the unrestricted collective rate. For the lower bound, we vary the support of a state with fixed uniform spectrum and bound the Fisher information trace of every joint measurement on $t$ samples. The adaptive Fisher chain rule and the van Trees inequality then give the trace norm lower bound. For the upper bound, we construct and analyze a nonadaptive tomography protocol based on a Gaussian joint measurement. An explicit second moment identity and a conditional Gaussian law outside the state's support give a rank-dependent error analysis, yielding the matching rate.

0.51

Uniform observability criteria for linear time-varying systems

eess.SY math.OC ·2026-10-25 ·Soulaimane Berkane
similarity 0.57
Abstract · 17 pages including a technical-report cover, 2 figures

Verifying uniform observability of a linear time-varying system generally requires its state-transition matrix. This paper develops necessary and sufficient conditions that can be checked directly from the coefficient matrices for two classes of systems. For constant dynamics with real spectrum and a measurable, essentially bounded output matrix, uniform observability is equivalent to persistent excitation of the output matrix on each eigenspace. An equivalent condition requires persistent excitation of the Kalman observability stack. The second result concerns cascades with a constant observable measured subsystem coupled to a hidden state. Under uniform regularity assumptions, linear combinations of output derivatives eliminate the measured state and yield an equivalent observability test for the hidden dynamics. When those dynamics have real spectrum, the test reduces to excitation on each eigenspace intersected with the kernel of the direct measurements. An application to arbitrary-order integrator chains with measurements of ranges to fixed anchors gives an exact excitation condition for the associated lifted LTV system. A second application treats direct hidden measurements and compares the condition with existing sufficient tests.

0.34

Observability Blocking in a Linear Synchronization Network with Partial State Measurements

eess.SY ·2026-08-26 ·Alexis Moreno, Abdullah Al Maruf
similarity 0.55
Abstract · 8 pages, 3 figures, submitted to the IEEE Conference on Decision and Control (CDC)

Large-scale networked systems are increasingly vulnerable to adversaries that can infer system dynamics from a small set of compromised nodes. This paper addresses the problem of blocking such inference using limited state information. While existing state-feedback methods achieve observability blocking with eigenvalue preservation, they require full state access and are impractical for large networks. We propose multiple control strategies that operate under partial state measurements. The first approach employs output feedback to achieve observability blocking while preserving a subset of open-loop eigenvalues. The second approach leverages an observer to reconstruct the system state and enables full-state feedback control, preserving all eigenvalues and providing greater flexibility in sensor placement. We further extend the observer-based design to a distributed framework. Numerical examples demonstrate the scope and validity of the proposed methods.

0.30

Tight Lower Bounds for State Tomography with Limited Entanglement

cs.IT quant-phcs.LG ·2026-09-04 ·Ufuk Keskin, Jason Luo, Mahbod Majid, Matthew Radzihovsky
theoryhighly cited similarity 0.54
Abstract · 36 pages

We study state tomography when each measurement acts on at most $k$ fresh copies and no quantum memory is retained between blocks. We prove a lower bound matching the upper bound in [arXiv:2510.07788]. Thus the copy complexity of estimating an arbitrary $d$-dimensional state to trace distance $ε$ is, up to absolute constant factors, $\max\{d^3/(\sqrt{k}ε^2),d^2/ε^2\}$ for every $k$ and all sufficiently small $ε$. This removes the earlier restriction that $k$ be small as a function of the accuracy. The lower bound applies to arbitrary measurements within each block and adaptive choices between blocks. The lower bound already applies in a small neighborhood of any state whose smallest eigenvalue is of order $1/d$, even when the center is known. The main ingredient is a uniform Fisher information bound for one measurement block that depends only on the smallest eigenvalue of the state. The proof avoids the perturbative expansion responsible for the restriction in [arXiv:2402.16353]. Fano's inequality for metric balls and a log-Sobolev comparison between mutual and Fisher information then reduce the adaptive protocol to this block bound [arXiv:1607.00550, arXiv:1902.08582].

0.41

Optimal Hamiltonian Parameter Estimation in the Presence of Nuisance Parameters

cs.IT quant-ph ·2026-09-11 ·Zhiyao Hu, Haidong Yuan, Liang Jiang, Zain H. Saleem
similarity 0.53
Abstract · 21 pages, 1 figure

In many sensing applications, the quantity of interest is not the only unknown, there are also additional unknown parameters, known as nuisance parameters, that affect the precision of estimation. While the ultimate local precision limit for a target parameter is well understood in the absence of nuisance parameters, the problem becomes significantly more challenging when they are present. In this work, we develop a framework for optimal Hamiltonian parameter estimation in the presence of nuisance parameters. We introduce an effective generator that captures the influence of nuisance parameters on the target precision, providing an explicit characterization of the ultimate precision limit for estimating the target parameter. Finally, we provide explicit optimal protocols, including probe state, control, and measurement that saturate this fundamental limit.

0.29

Recovering linear images of sparse signals from indirect observations

cs.IT stat.MLcs.LGmath.OC ·2026-09-05 ·Anatoli Juditsky, Arkadi Nemirovski
hot direction similarity 0.52
Abstract

In this paper, we develop and analyze techniques for recovering a linear image $Bx$ of an unknown signal $x$ from indirect noisy observation $ω=Ax+ξ$. It is {\em a priori} known that $x\in \cX$, a given convex compact set, and that $x$ is $s$-sparse---has at most $s$ nonvanishing entries. The proposed estimates belong to a large family of recovery routines by $\ell_1$-minimization. However, unlike the classical result describing performance of such estimates, we do not make any special (and hard to check) assumptions about the sensing matrix $A$ such as nullspace or Restricted Isometry condition and the like. As a consequence, parameters of the estimates and the upper bounds on their risks are not available in a closed analytic form, but are delivered instead by efficient computation as solutions to explicit convex optimization problems.

0.26