Symmetric Linear Dynamical Systems are Learnable from Few Observations

Andrey Y. Lokhov; Marc Vuffray; Minh Vu

REVIEW 3 major objections 5 minor 3 references

Symmetric Linear Dynamical Systems are Learnable from Few Observations

T0 review · 3 major / 5 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For any symmetric, stable linear system driven by Gaussian noise, a single trajectory of length O(log N) suffices to recover the dynamics matrix A elementwise, whether A is sparse or dense.

desk verdict Elegant lag-difference estimator gives a real O(log N) guarantee, but only for zero initial state; the paper overclaims in the abstract. read the letter →

arxiv 2512.05337 v2 pith:O2BZVNK5 submitted 2025-12-05 stat.ML cs.LGcs.SYeess.SYmath.OC

Minh Vu , Andrey Y. Lokhov , Marc Vuffray This is my paper · ORCID

classification stat.MLcs.LGcs.SYeess.SYmath.OC MSC 62M1093E1260F10

keywords lineardynamicalsystemssystemidentificationmethodofmomentssamplecomplexitypartialobservationsGaussiannoisehigh-dimensionalestimationsupportrecovery

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper introduces a method-of-moments estimator that recovers the dynamic matrix of a symmetric linear system from a single trajectory using only about log N time steps. The estimator combines time-shifted covariance samples: it subtracts a further-shifted term to cancel a low-order bias. The main theorem proves a finite-sample, elementwise maximum-norm error bound with probability 1 - delta when the trajectory length T exceeds a constant times log(2N^2/delta). This is notable because the total data count O(N log N) can be smaller than the number of unknown matrix entries, and the method works for both sparse and dense matrices without regularization.

What carries the argument

The estimator S_m(T) is the difference of two sliding-window autocovariance averages: (1/(T-m)) sum_{t=0}^{T-m-1} x_t x_{t+m}^T minus the analogous lag-(m+2) average. Because E[x_t x_s^T] = sigma^2 A^{s-t} (I - A^{2t})(I - A^2)^{-1}, this difference cancels the time-dependent (I - A^{2t}) factors, leaving a bias that decays as O(1/T). The concentration proof represents each element as a quadratic form X^T G_{ij} X in Gaussian variables, bounds the spectral radius of L^T G_{ij} L via Gershgorin's circle theorem on a tridiagonalized form of (LL^T)^{-1}, and uses the log-determinant trace identity together with a Chernoff bound to obtain the exponential tail.

What would settle it

Simulate a symmetric A with rho(A) = 0.9 and a nonzero deterministic initial state x0, then run the estimator with T = C log N for a constant C large enough to satisfy the theorem's bound. If the elementwise error stays small across many trials, the guarantee extends beyond the stated initialization; if the error grows roughly as rho(A)^T and cannot be reduced by increasing N, the log N claim fails outside the zero-initial-state assumption.

Watch

Extended reading notes

Core claim

The central claim is Theorem 2: for any symmetric A with spectral radius rho(A) < 1, initial state x0 = 0, and i.i.d. Gaussian noise with covariance sigma^2 I, the estimator S_m(T) defined in Eq. (5) satisfies ||S_m(T) - sigma^2 A^m||_max <= epsilon with probability at least 1 - delta, provided T >= max{64 sigma^4 (1 + 2 sqrt(log(2N^2/delta)))^2 / (epsilon^2 (1 - rho(A))^4), 2(m+2)}. This implies that A and its powers can be estimated elementwise with fixed precision using O(log N) samples. The same estimator extends to partial observations, recovering the observed block B of A in O(log N) steps, and the composite blocks CC^T and CEC^T with additional polynomial-in-N factors.

Load-bearing premise

The proof assumes the trajectory starts at x0 = 0; the unbiasedness and the O(1/T) bias that enable log N sampling rely on a cancellation that fails for a general nonzero initial state.

Editorial extensions

If this is right

Total data points O(N log N) can be smaller than the number of unknown off-diagonal entries (about N^2/2), enabling structure discovery in high-dimensional systems.
Both sparse and dense symmetric systems are handled by the same estimator with identical O(log N) sample complexity, requiring no tuning of a sparsity-promoting regularizer.
In the partial-observation setting, the observed block B of the dynamics matrix is recovered in O(log N) steps; the composite moments CC^T and CEC^T require O(N^2 log N) and O(N^4 log N) steps respectively.
The elementwise maximum-norm guarantee supports entrywise thresholding for support recovery of A, relevant to applications such as anomaly detection and graph discovery.
The bound holds uniformly across all entries without incoherence or restricted-eigenvalue-type conditions, unlike LASSO-based alternatives.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The zero-initial-state assumption x0 = 0 is load-bearing: with a nonzero deterministic initial state, the lag-m minus lag-(m+2) subtraction no longer cancels the transient term, and the bias decays only as rho(A)^T, which for rho(A) close to 1 breaks the O(log N) guarantee.
If the initialization limitation can be removed, the same lag-subtraction scheme could extend to marginally stable systems with a pre-filtering step, since the bias cancellation is algebraic rather than relying on mixing times.
The estimator produces consistent Markov parameters (sigma^2 A^m) in O(log N) steps, so it could serve as a warm-start initializer for subspace-identification methods in the partially observed setting.
A stress test with rho(A) close to 1 (e.g., 0.99) would probe the O(1/(1 - rho(A))^4) constant in the bound; the theory predicts the required T grows steeply, and numerical experiments could confirm whether the constant is tight.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The short version: this paper has a genuinely elegant estimator and a real O(log N) finite-sample guarantee for elementwise recovery of symmetric stable transition matrices — but only when the trajectory starts at zero, an assumption the paper never flags. That's the thing to know before you cite it.

What's new: the lag-difference identity S_m = (lag m) - (lag m+2) cancels the stationary covariance term and leaves σ² A^m. It's a neat way to avoid inverting the stationary covariance, and it gives a max-norm concentration bound via Gaussian quadratic-form MGFs with no incoherence conditions, so the log N sample complexity holds for both sparse and dense A. The partial-observation corollary is a useful extension. The proof is internally coherent; the union bound and bias calculation check out.

Soft spots, in rough order of seriousness:

1. The x0=0 assumption is load-bearing. If x0 is nonzero, the deterministic transient contributes a term of order ||x0||^2/T to the bias, not O(ρ^T). For a generic x0 with entries O(1), that's O(N/T), so T must scale with N to get fixed elementwise error — the advertised O(log N) is gone. The paper states x0=0 in Section 3.1 but never mentions it in the abstract or conclusion, and the experiments presumably initialize at zero.

2. Theorem 2 bounds S_m - σ² A^m, not A - A_hat. Recovering A itself requires knowing or estimating σ². The full-observation setting never formalizes the division; the partial-observation version does estimate σ² from the trace, so it's not a fatal gap, but the abstract says "recovery of symmetric dynamic matrices" as if A is directly estimated.

3. The "dense" experiment is a star graph with O(N) edges — sparse, not dense. The paper's claim of working for dense matrices rests on theory, not the simulation. Also, no code is released and the baselines are standard LS and L1-LS, which is fine, but the comparison is thin.

4. Minor: the bound's T scales as 1/(1-ρ)^4, so O(log N) only when ρ is fixed away from 1. That's standard for the literature, but worth saying.

The central result appears correct under its stated assumptions. The main problem is a mismatch between the advertised claims and the actual theorem. I'd send it to a serious referee — the identity is worth publishing even if the title needs tempering — but the authors should be asked to either extend the analysis to generic x0 or clearly restrict the claims.

Recommendation: engage with it in review; don't let it through as-is.

Referee Report

3 major / 5 minor

Summary. The paper studies estimation of the N×N symmetric stable matrix A in xt = A x_{t-1} + ξ_t, ξ_t ~ N(0, σ²I), from a single trajectory of length T, under full and partial observations. It proposes a method-of-moments estimator that differences lag-m and lag-(m+2) sample autocovariances, proves asymptotic unbiasedness (Theorem 1) and a finite-sample elementwise concentration bound (Theorem 2) giving T = O(log N) for a fixed max-norm error on σ² A^m. For partial observations, Corollary 1 shows the observed block B is recoverable with T = O(log N), while CC^⊤ and CEC^⊤ require T = O(N² log N) and O(N⁴ log N) samples, respectively. Numerical experiments on sparse and dense graphs illustrate the claimed logarithmic scaling.

Significance. If the result holds, it is a notable contribution to high-dimensional system identification: it gives a non-regularized estimator that recovers elementwise entries of a symmetric stable matrix with only O(log N) time samples, which is below the number of unknown parameters when N is large. The estimator is explicit, has no tuned free parameters, and the proof is largely self-contained, relying on standard Gaussian quadratic-form concentration and a union bound. The numerical experiments support the qualitative scaling. However, the advertised claim depends on the zero-initialization assumption and on a separate estimation of σ² for full observations; these points must be stated and handled before the result can be accepted as presented.

major comments (3)

[3.1, Eq. (2), Theorem 2] The central finite-sample guarantee is proved only for x0 = 0. For a deterministic x0 ≠ 0, x_t = A^t x0 + noise, and the deterministic part contributes D_T = (1/(T-m)) Σ_{t=0}^{T-m-1} A^t x0 x0^T A^{t+m} - (1/(T-m-2)) Σ_{t=0}^{T-m-3} A^t x0 x0^T A^{t+m+2} to E[\hat S_m(T)]. Since A is contracting, D_T = O(||x0||²/T); for generic initial states with ||x0||² = Θ(N), the bias is Θ(N/T), so to reach a fixed ε the trajectory length must scale as N, not log N. The abstract and introduction present T = O(log N) without this initialization condition. This is not a technicality: the lag-m/lag-(m+2) cancellation is what removes the bias, and it does not cancel the deterministic transient. The authors should either prove a version for arbitrary initial states (e.g., with a burn-in of O(log N) steps), or explicitly restrict all claims to x0 = 0 and state so in the abstract.
[Theorem 2 / Section 3.1] Theorem 2 bounds ||\hat S_m(T) - σ² A^m||_max. The text then states that A and its powers can be estimated, but a bound on σ² A^m does not by itself yield a bound on A unless σ² is known. The full-observation part never defines an estimator of A or gives its elementwise error. The partial-observation Corollary 1 does handle σ² via \hat σ² = (1/n_o)Tr([\hat S_0]_O), but the analogous statement for full observations is missing. Please add a corollary for \hat A = \hat S_1 / \hat σ² (with \hat σ² = (1/N)Tr(\hat S_0)), including the resulting O(ε/σ²) elementwise error, or state explicitly that the result concerns σ² A^m only.
[4.3, Proof of Theorem 2] The derivation after the union bound contains an apparent algebraic error. From Lemma 5 and the union bound, the high-probability concentration term is proportional to √T (1/(T-m)+1/(T-m-2)) / (1-ρ)², which after bounding the sum by 4/T gives O(1/(√T (1-ρ)²)). The manuscript instead writes a denominator T(1-ρ)^4. As written, the subsequent triangle inequality with the bias term and the final bound 8σ²(1+2√log)/((1-ρ)²√T) do not follow. The final T condition may be correct, but the proof needs correction.

minor comments (5)

[Abstract] Typo: 'aN-dimensional' should be 'an N-dimensional'.
[Section 3.1, Eq. (2)] In Eq. (2), the noise vector is written as ξt∈R n; it should be R^N for consistency with the N-dimensional state.
[Corollary 1] The notation [CC⊤ and \CEC⊤ is hard to read; use \widehat{CC^\top} and \widehat{CEC^\top}.
[Section 5.1 / 5.2] Minor typos: 'achive' -> 'achieve'; Figure 2 caption has 'other other'.
[Lemma 3] The proof uses σ_max for the spectral norm of a matrix and λ_max for the largest eigenvalue; this is clear but should be defined explicitly to avoid confusion with the elementwise max norm.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the estimator and all theorems are derived self-contained from the moment relation; the only self-citations are contextual and not load-bearing.

full rationale

The paper's derivation chain is self-contained. The estimator S_m(T) in Eq. (5) is constructed directly from the moment identity E[x_t x_s^T] = sigma^2 A^{s-t} ... in Eq. (4), which is derived from the model Eq. (2) without assuming the target result. Theorem 1 computes E[S_m(T)] explicitly, and Theorem 2's finite-sample bound follows from standard Gaussian concentration (MGF, Chernoff, Gershgorin) with no fitted parameter and no appeal to the quantity being estimated. The x0=0 assumption is a modeling restriction that limits the scope of the claims, but it is not a circular step: it is stated upfront and the bounds are derived from it. The partial-observation Corollary 1 is derived from the same S_m estimators and block algebra, again without fitting. The self-citations [VML20, HDJ+21] appear only as context for the elementwise/support-recovery setting and applications; they do not carry the argument. No ansatz is smuggled in via citation, no uniqueness theorem is imported from the authors' prior work, and no known result is merely renamed. Hence there is no significant circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The estimator is parameter-free apart from the fixed moment order m (m = 1 for A recovery); no number is fitted to data. The proof relies on the stated model assumptions (Gaussian noise, symmetric stable A, zero initial state) and standard matrix-analysis tools. No new physical or mathematical entity is introduced.

assumptions (4)

domain assumption Noise xi_t are i.i.d. zero-mean Gaussian with covariance sigma^2 I.
Used throughout: Lemma 2 and Lemma 5 require Gaussianity for the exact MGF/determinant computation. Section 3.1.
domain assumption A is symmetric with spectral radius rho(A) < 1.
Symmetry makes (I - A^2)Gamma = sigma^2 I, the key cancellation in Eq. (4) and Theorem 1. Stability ensures finite covariance and bias decay. Section 3.1.
domain assumption The initial state is x0 = 0.
Needed for the moving-sum representation in Eq. (3) with no deterministic transient; Section 3.1 explicitly assumes x0 = 0.
standard math Standard Gaussian quadratic-form MGF, log-determinant identity, and Gershgorin circle bounds.
Used in Lemmas 3-5 to obtain exponential concentration; these are standard mathematical tools, not ad hoc to the paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Symmetric Linear Dynamical Systems are Learnable from Few Observations." pith.science (2026). https://pith.science/paper/O2BZVNK5

@misc{pith2026251205337,
  author       = {Pith},
  title        = {Pith review of: Symmetric Linear Dynamical Systems are Learnable from Few Observations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/O2BZVNK5}},
  note         = {Machine review of arXiv:2512.05337}
}

abstract

We consider the problem of learning the parameters of a $N$-dimensional stochastic linear dynamics under both full and partial observations from a single trajectory of time $T$. We introduce and analyze a new estimator that achieves a small maximum element-wise error on the recovery of symmetric dynamic matrices using only $T=\mathcal{O}(\log N)$ observations, irrespective of whether the matrix is sparse or dense. This estimator is based on the method of moments and does not rely on problem-specific regularization. This is especially important for applications such as structure discovery.

Figures

Figures reproduced from arXiv: 2512.05337 by the authors.

**Figure 2.** Performance under partial observability. The curves represent the best fit of the empirical [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

3 extracted references · 2 linked inside Pith

[3]

Learning linear dynamical systems under convex constraints.arXiv preprint arXiv:2303.15121,

[TE23] Hemant Tyagi and Denis Efimov. Learning linear dynamical systems under convex constraints.arXiv preprint arXiv:2303.15121,

arXiv
[2011]

Revisiting ho–kalman-based system identification: Robustness and finite-sample analysis.IEEE Transactions on Automatic Control, 67(4):1914–1928,

[OO21] Samet Oymak and Necmiye Ozay. Revisiting ho–kalman-based system identification: Robustness and finite-sample analysis.IEEE Transactions on Automatic Control, 67(4):1914–1928,

1914
[2021]

Large vector auto regressions.arXiv preprint arXiv:1106.3915,

[SB11] Song Song and Peter J Bickel. Large vector auto regressions.arXiv preprint arXiv:1106.3915,

arXiv

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.

[1] [3]

Learning linear dynamical systems under convex constraints.arXiv preprint arXiv:2303.15121,

[TE23] Hemant Tyagi and Denis Efimov. Learning linear dynamical systems under convex constraints.arXiv preprint arXiv:2303.15121,

arXiv

[2] [2011]

Revisiting ho–kalman-based system identification: Robustness and finite-sample analysis.IEEE Transactions on Automatic Control, 67(4):1914–1928,

[OO21] Samet Oymak and Necmiye Ozay. Revisiting ho–kalman-based system identification: Robustness and finite-sample analysis.IEEE Transactions on Automatic Control, 67(4):1914–1928,

1914

[3] [2021]

Large vector auto regressions.arXiv preprint arXiv:1106.3915,

[SB11] Song Song and Peter J Bickel. Large vector auto regressions.arXiv preprint arXiv:1106.3915,

arXiv