REVIEW 3 major objections 4 minor 26 references
Learning clusters of partially observed linear dynamical systems
T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read Clustering short trajectories first, then pooling each cluster's data, recovers shared linear dynamics with error that shrinks as $1/\sqrt{N}$.
desk verdict The multi-trajectory Markov parameter bound is a real advance, but condition (5) in the clustering guarantee is missing a p factor and the k-means global-minimality assumption is unsupported. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The engine is the least-squares estimator of a block of Markov parameters from multiple trajectories, $\hat G^{(L)} = Y^{(L)}(U^{(L)})^\dagger$, where $U^{(L)}$ is the $m(L+1)\times N T_{\mathrm{eff}}$ block-Toeplitz input matrix whose rows are shifted input vectors. The proof handles the statistical dependence created by the Toeplitz structure by partitioning $U$ into $L+1$ embedded Page matrices with independent Gaussian entries, giving a high-probability lower bound on the minimum singular value of $UU'$ and matching bounds on the two error terms: the noise term $WU'$ and the truncated-state term $EU'$ from the unobserved state $L$ steps back. A cluster-separation condition in impulse-response distance is then used to show that when per-trajectory estimation error is below $\Delta/2$, the global minimizer of k-means on the estimated Markov parameters recovers the true assignment. Finally, Ho-Kalman, the classical realization algorithm that factors a Hankel matrix of impulse responses, transfers the Markov-parameter error to state-space realization error, with amplification controlled by the Hankel singular value $\sigma_{2n}(H)$.
What would settle it
Take a strictly stable order-3 system with Gaussian inputs and no noise, generate $N$ independent length-$T$ trajectories, and estimate the first $L=4$ Markov parameters by least squares for increasing $N$ at fixed $T$. If the operator-norm error does not decay like $(NT)^{-1/2}$ up to log factors, the core trade-off of Theorem 4.1 is contradicted; alternatively, run Algorithm 1 with a single-start k-means on a well-separated $K=2$ instance satisfying condition (5) and check whether exact cluster recovery ever fails, since the guarantee as stated assumes the global minimum is found.
Extended reading notes
Core claim
The paper's claim, stated as Proposition 4.2, is an end-to-end guarantee for Algorithm 1. For $K$ strictly stable minimal models of known order $n$, each with $N$ length-$T$ trajectories, exact zero-width clusters separated by at least $\Delta$ in their first $L_1+1$ Markov parameters, Gaussian inputs and subgaussian noise, if the trajectory length satisfies condition (5) and k-means reaches its global minimum, cluster assignments are recovered exactly with probability at least $1-\delta$; if $N(T-L_2)$ satisfies condition (6), the per-cluster least-squares estimate of the first $L_2+1$ Markov parameters is within operator-norm error $\varepsilon$; and when $L_2 \ge 2n+1$, Ho-Kalman returns realizations whose Frobenius errors relative to the true model are bounded by roughly $\sqrt{nL_2}\,\varepsilon/\sigma_{2n}(H)$, where $H$ is the Hankel matrix of the true model. The load-bearing quantitative identity behind these bounds is the multi-trajectory sample complexity of Theorem 4.1, which implies $L_2/\varepsilon_2 \approx \sqrt{N}\, L_1/\varepsilon_1$ for fixed $T$: $N$ trajectories increase the estimable impulse-response length, or the accuracy, by a factor $\sqrt{N}$.
Load-bearing premise
The end-to-end guarantee rests on the assumption that k-means, run on the estimated Markov parameters, finds the global minimum of its squared-error objective; standard k-means is not guaranteed to do so, and the paper does not prove that its initialization does.
Editorial extensions
If this is right
- Short trajectories are enough for clustering: $L_1$ can be kept small, while only some trajectories in each cluster need to be long enough to estimate the $L_2 \ge 2n+1$ Markov parameters needed for a realization, so systems with short data can be identified by labeling them into the right cluster.
- For fixed trajectory length $T$, increasing the number $N$ of observed systems in a cluster cuts the pooled impulse-response estimation error by roughly $1/\sqrt{N}$, meaning many short trajectories can substitute for one long one.
- The bounds make the dependence on model complexity explicit: the required trajectory length grows polynomially with $L$ (the number of Markov parameters) and with $p+(m+n)L$ up to log factors, so the guarantee is not restricted to low-dimensional special cases.
- Because the Markov-parameter error feeds directly into Ho-Kalman, the final state-space realization error is the same $\varepsilon$ scaled by $\sqrt{nL_2}/\sigma_{2n}(H)$; the guarantee degrades only when the underlying realization is nearly unobservable or uncontrollable.
- In the simulations, the cluster-then-pool algorithm is more sample-efficient than the moment-based tensor-decomposition estimator at the tested trajectory lengths, suggesting the method works where moment methods need more data.
Reading between the lines
- Since the pooling step only needs correct assignments, any clustering rule that achieves exact recovery with per-trajectory error below half the cluster separation would feed the same downstream bounds; k-means is a convenient choice, not the only possible one.
- The proof's cubic-in-$L$ dependence of the required trajectory length is flagged by the authors as likely loose, so the practical short-trajectory regime may be substantially wider than the theorem states.
- A testable consequence of the truncation bound is that choosing $L_1$ too small hurts clustering even for large $N$, because the residual term $\|C A^{L_1}\|_2$ dominates; the optimal $L_1$ should track the decay rate of the state-transition matrix.
- The same pipeline should extend to heterogeneous trajectory lengths by setting $L_1$ to the minimum available length per system, which would make the method applicable to federated or irregularly sampled data sources.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a multi-stage algorithm for learning clusters of partially observed linear time-invariant systems from multiple input-output trajectories. In the first stage, short impulse responses (Markov parameters) are estimated per trajectory by least squares and clustered by k-means; in the second stage, longer impulse responses are estimated jointly from all trajectories in each cluster, and Ho-Kalman realization is applied to obtain state-space models. The main theoretical contribution is Theorem 4.1, a finite-sample bound for least-squares estimation of Markov parameters from multiple independent trajectories, and Proposition 4.2, which combines this bound with a separation condition and k-means clustering to give end-to-end guarantees for cluster recovery, Markov parameter estimation, and state-space realization. The paper also provides a simulation study illustrating the trade-off between trajectory length and number of trajectories, and a comparison with a tensor-decomposition-based method.
Significance. If the end-to-end guarantees were established as stated, the paper would make a useful contribution to system identification with limited per-system data: it explicitly quantifies the benefit of pooling trajectories across systems in a cluster, shows a 1/sqrt(N) error reduction relative to single-trajectory estimation for fixed trajectory length, and provides the first finite-sample analysis, to my knowledge, of this particular cluster-then-refine pipeline for partially observed LDS. The proof of Theorem 4.1 extends Oymak and Ozay's argument to multiple trajectories in a natural way, and the simulations support the qualitative claims. However, as detailed below, the end-to-end statement in Proposition 4.2 has load-bearing gaps that need to be corrected before the results can be accepted as proved.
major comments (3)
- [§IV-B, condition (5)] Condition (5) is missing a factor of p that is required when Theorem 4.1 is applied with target spectral error ε = Δ/(2√p). Substituting this ε into the sample-complexity condition of Theorem 4.1 yields T - L1 ≳ p L1 Φ(L1)/(Δ² σ_u²) (p + L1(m+n) + ln(T/δ))², not the printed condition without the leading p. For output dimension p that is not absorbed by the logarithmic term, a trajectory length satisfying (5) does not guarantee the spectral-norm error bound ‖hat G_i^(L1) - G_i^(L1)‖_2 ≲ Δ/(2√p), and therefore the Frobenius error bound Δ/2 used for clustering is not supported. This is a load-bearing gap in the proof of Proposition 4.2, since the exact cluster-recovery statement and all downstream realization guarantees rely on it. The condition should be corrected, or the proof should show a different route to the Δ/2 bound.
- [§IV-B and §VII-E-b] Proposition 4.2 assumes that k-means reaches the global minimum of its squared-error objective, but the paper does not provide any algorithmic mechanism or initialization that provably finds this global minimizer. Standard k-means only guarantees a local minimum, and the remark that well-separated clusters and multiple initializations 'should suffice' is not a proof. Because exact cluster recovery and all subsequent multi-trajectory estimation bounds depend on this assumption, the end-to-end guarantee is not yet a guarantee about the implementable Algorithm 1 as described. The authors should either state this as an explicit limitation of the theorem (rather than an internal assumption), or provide an initialization/rounding argument that ensures the global minimizer is found under the separation condition.
- [§IV-B, realization bound] The final Ho-Kalman error bound in Proposition 4.2 is not justified without an additional condition. Proposition 7.1, the imported robustness result from [14], only applies when ‖G^(2L+1) - hat G^(2L+1)‖_2 ≤ √n σ_n(H_-). Proposition 4.2 does not state or verify this condition from the ε bound obtained in the multi-trajectory estimation step. As printed, the bound ‖A - Q^{-1} hat A Q‖_F ≲ √(nL2) σ_{2n}(H)^{-1} ε and the analogous bounds for C, B, D do not follow from the preceding argument. The authors should add the required perturbation-size condition to the statement of Proposition 4.2, or replace the invocation of Proposition 7.1 with a version of Ho-Kalman robustness that holds without it.
minor comments (4)
- [§II-C] The sentence 'the output of system i at time t is given by is given by' contains a duplicated phrase that should be removed.
- [§V and §VII-B] The term 'Page matrices' is used several times; please clarify the intended terminology or define it explicitly, since it is not a standard term in this context.
- [§IV-B, condition (6)] Condition (6) uses ln(NT/δ) for each cluster, but the statement of Proposition 4.2 bounds the sup over k ∈ [K]. Applying Theorem 4.1 to each of the K clusters and taking a union bound would require the logarithm to be ln(KNT/δ), or the failure probability per cluster to be δ/K. This is a minor issue because it can be fixed by redefining δ, but it should be made precise.
- [§IV-B and Algorithm 1] The notation L1 and L2 is called the 'number of Markov parameters', but the algorithm and bounds actually estimate L+1 Markov parameters. A sentence clarifying this accounting would prevent confusion.
Circularity Check
No significant circularity: bounds are proved in-paper from concentration inequalities; cluster separation and k-means optimality are explicit assumptions, not fitted inputs.
full rationale
After walking the derivation chain, I find no load-bearing circular step. Theorem 4.1 is proved in Section V and Appendices VII-B through VII-D from concentration inequalities for Gaussian/subgaussian random matrices (Propositions 5.1-5.3, Lemmas 7.2-7.7) plus standard external results (Foucart-Rauhut Theorem 9.26, Vershynin's Bernstein and Hanson-Wright bounds); it is not obtained by assuming the conclusion. Proposition 4.2 composes this theorem (with N=1 and with N cluster trajectories) with the assumed Delta-separation margin and the explicit, unproved k-means global-optimality assumption. The separation condition is a margin on the ground-truth model class, not a fitted parameter, and the k-means assumption is a stated limitation, not a circular input. Ho-Kalman robustness is imported from the external Oymak-Ozay result [14, Theorem 5.2] (Proposition 7.1), not from the authors' prior work. The self-citations ([3], [11], and the co-authored [13]) appear only in related-work comparisons or as a simulation baseline, and the restricted-isometry argument that [13] discusses is re-proved in this paper, so no load-bearing claim reduces to those citations. A separate, non-circular correctness concern noted by the skeptic is that condition (5) appears to omit the factor p that enters when Theorem 4.1's single-trajectory bound is used with target Delta/(2*sqrt(p)); if real, this would make the clustering guarantee not follow from the stated sample-complexity condition, but it does not turn the derivation into its own input. I therefore assign a circularity score of 0.
Assumptions & free parameters
assumptions (6)
- domain assumption Strict stability rho(A)<1 and minimality (controllability and observability) of each cluster realization.
- domain assumption Inputs are iid isotropic Gaussian; process and measurement noises are independent zero-mean subgaussian.
- domain assumption Known number of clusters K, known order n, equal number N of trajectories per cluster, exact zero-width clusters for theory.
- domain assumption The K cluster models are separated by at least Delta in their first L1+1 Markov parameters.
- ad hoc to paper K-means converges to the global minimum of its squared-error objective.
- standard math Ho-Kalman robustness theorem from Oymak and Ozay and standard Gaussian concentration inequalities.
Cite this review
Pith. "Pith review of Learning clusters of partially observed linear dynamical systems." pith.science (2026). https://pith.science/paper/FUESS7EI
@misc{pith2026250717638,
author = {Pith},
title = {Pith review of: Learning clusters of partially observed linear dynamical systems},
year = {2026},
howpublished = {\url{https://pith.science/paper/FUESS7EI}},
note = {Machine review of arXiv:2507.17638}
}
read the original abstract
We study the problem of learning clusters of partially observed linear dynamical systems from multiple input-output trajectories. This setting is particularly relevant when there are limited observations (e.g., short trajectories) from individual data sources, making direct estimation challenging. In such cases, incorporating data from multiple related sources can improve learning. We propose an estimation algorithm that leverages different data requirements for the tasks of clustering and system identification. First, short impulse responses are estimated from individual trajectories and clustered. Then, refined models for each cluster are jointly estimated using multiple trajectories. We establish end-to-end finite sample guarantees for estimating Markov parameters and state space realizations and highlight trade-offs among the number of observed systems, the trajectory lengths, and the complexity of the underlying models.
Figures
Reference graph
Works this paper leans on
-
[14]
Revisiting ho–kalman-based syst em identifi- cation: Robustness and finite-sample analysis,
S. Oymak and N. Ozay, “Revisiting ho–kalman-based syst em identifi- cation: Robustness and finite-sample analysis,” IEEE Transactions on Automatic Control, vol. 67, no. 4, pp. 1914–1928, 2021
work page 1914
-
[1]
Joint learning of linear time-invariant dynamical systems,
A. Modi, M. K. S. Faradonbeh, A. Tewari, and G. Michailidi s, “Joint learning of linear time-invariant dynamical systems,” arXiv preprint arXiv:2112.10955, 2021
arXiv 2021
-
[2]
Multi-task imitation learning for linear dynami cal systems,
T. T. Zhang, K. Kang, B. D. Lee, C. Tomlin, S. Levine, S. Tu, and N. Matni, “Multi-task imitation learning for linear dynami cal systems,” in Learning for Dynamics and Control Conference . PMLR, 2023, pp. 586–599
work page 2023
-
[3]
Estimation of Models with Limited Data by Leveraging Shared Structure
M. Rui, T. Horel, and M. Dahleh, “Estimation of models wit h limited data by leveraging shared structure,” arXiv preprint arXiv:2310.02864, 2023
work page Pith review arXiv 2023
-
[4]
Learning mixtures of linear dynam ical systems,
Y . Chen and H. V . Poor, “Learning mixtures of linear dynam ical systems,” in International Conference on Machine Learning . PMLR, 2022, pp. 3507–3557
work page 2022
-
[5]
Learning Personalized Models with Clustered System Identification
L. F. Toso, H. Wang, and J. Anderson, “Learning personal- ized models with clustered system identification,” arXiv preprint arXiv:2304.01395, 2023
work page Pith review arXiv 2023
-
[6]
Learning dynamic al systems by leveraging data from similar systems,
L. Xin, L. Y e, G. Chiu, and S. Sundaram, “Learning dynamic al systems by leveraging data from similar systems,” arXiv preprint arXiv:2302.04344, 2023
arXiv 2023
-
[7]
Multi- task system identification of similar linear time-invarian t dynamical systems,
Y . Chen, A. M. Ospina, F. Pasqualetti, and E. Dall’Anese, “Multi- task system identification of similar linear time-invarian t dynamical systems,” arXiv preprint arXiv:2301.01430 , 2023
arXiv 2023
Show all 26 references
-
[8]
A benchmark study on t ime series clustering,
A. Javed, B. S. Lee, and D. M. Rizzo, “A benchmark study on t ime series clustering,” Machine Learning with Applications , vol. 1, p. 100001, 2020
2020
-
[9]
Time -series clustering–a decade review,
S. Aghabozorgi, A. S. Shirkhorshidi, and T. Y . Wah, “Time -series clustering–a decade review,” Information systems , vol. 53, pp. 16–38, 2015
2015
-
[10]
Tensor decompo sitions meet control theory: learning general mixtures of linear dy namical systems,
A. Bakshi, A. Liu, A. Moitra, and M. Y au, “Tensor decompo sitions meet control theory: learning general mixtures of linear dy namical systems,” in International Conference on Machine Learning . PMLR, 2023, pp. 1549–1563
2023
-
[11]
Finite sample analysis of tensor d ecom- position for learning mixtures of linear systems,
M. Rui and M. Dahleh, “Finite sample analysis of tensor d ecom- position for learning mixtures of linear systems,” arXiv preprint arXiv:2412.10615, 2024
2024 arXiv
-
[12]
Finite sample properties of sy stem identification methods,
M. C. Campi and E. Weyer, “Finite sample properties of sy stem identification methods,” IEEE Transactions on Automatic Control , vol. 47, no. 8, pp. 1329–1334, 2002
2002
-
[13]
Finite time LTI system identification,
T. Sarkar, A. Rakhlin, and M. A. Dahleh, “Finite time LTI system identification,” The Journal of Machine Learning Research , vol. 22, no. 1, pp. 1186–1246, 2021
2021
-
[15]
Ho and R
B. Ho and R. E. K´ alm´ an, “Effective construction of lin ear state- variable models from input/output functions: Die Konstruk tion von linearen Modeilen in der Darstellung durch Zustandsvar i- able aus den Beziehungen f¨ ur ein-und Ausgangsgr¨ oßen,” at- Automatisierungstech...
1966
-
[16]
A new approach t o learning linear dynamical systems,
A. Bakshi, A. Liu, A. Moitra, and M. Y au, “A new approach t o learning linear dynamical systems,” arXiv preprint arXiv:2301.09519 , 2023
2023 arXiv
-
[17]
Non-asymptotic identification of li near dynami- cal systems using multiple trajectories,
Y . Zheng and N. Li, “Non-asymptotic identification of li near dynami- cal systems using multiple trajectories,” IEEE Control Systems Letters , vol. 5, no. 5, pp. 1693–1698, 2020
2020
-
[18]
Learning partially observed linear dynam ical systems from logarithmic number of samples,
S. Fattahi, “Learning partially observed linear dynam ical systems from logarithmic number of samples,” in Learning for Dynamics and Control. PMLR, 2021, pp. 60–72
2021
-
[19]
Least squares quantization in pcm,
S. Lloyd, “Least squares quantization in pcm,” IEEE transactions on information theory , vol. 28, no. 2, pp. 129–137, 1982
1982
-
[20]
Estimating the nor ms of random circulant and toeplitz matrices and their inverses,
V . Y . Pan, J. Svadlenka, and L. Zhao, “Estimating the nor ms of random circulant and toeplitz matrices and their inverses,” Linear algebra and its applications, vol. 468, pp. 197–210, 2015
2015
-
[21]
Foucart and H
S. Foucart and H. Rauhut, A Mathematical Introduction to Compres- sive Sensing . Springer Science & Business Media, 2013
2013
-
[22]
V ershynin, High-dimensional probability: An introduction with applications in data science
R. V ershynin, High-dimensional probability: An introduction with applications in data science . Cambridge university press, 2018, vol. 47. 7 VII. A PPENDIX A. Ho-Kalman Realization We may recover a balanced minimal realization (C, A, B, D) for an order n system given its Mark...
2018
-
[23]
effective
analyzes the robustness of the Ho-Kalman algorithm wit h respect to the estimation error of the first 2L + 2 Markov parameters. Their result, tailored to our setting, is state d in Proposition 7.1. Proposition 7.1 ([14, Theorem 5.2]): Given a system of order n, let L≥ n and sup...
-
[24]
This implies that q∑ k=1 σ2 inf (Ak)≤ min v∈S m− 1 q∑ k=1 ‖Akv‖2 2 = σ2 min(U )≤ σ2 max(U ) = sup v∈S m− 1 q∑ k=1 ‖Akv‖2 2≤ q∑ k=1 σ2 max(Uk)
But for each k, σmin(Ak)≤‖ v′Ak‖2≤ σmax(Ak). This implies that q∑ k=1 σ2 inf (Ak)≤ min v∈S m− 1 q∑ k=1 ‖Akv‖2 2 = σ2 min(U )≤ σ2 max(U ) = sup v∈S m− 1 q∑ k=1 ‖Akv‖2 2≤ q∑ k=1 σ2 max(Uk). Taking the square root of each term in the chain of inequaliti es gives the claim. Lemma ...
-
[25]
Define a mapping of pairs of indices indicating the partition j∈ [0:L] and element k∈ [d] of the partition to linear indices τ : (j, k)↦→k(L+1)+( j−1)∈ [T ]
Let C1,C2 be 1/4-covers of Sp−1,Sm(L+1), respectively, such that |C1|≤ 9p and|C2|≤ 9m(L+1) and ‖ ‖ ‖EJj U ′ Jj ‖ ‖ ‖ 2 ≤ 2 sup a∈C1,b ∈C2 a′EJj U ′ Jj b. Define a mapping of pairs of indices indicating the partition j∈ [0:L] and element k∈ [d] of the partition to linear indices...
-
[26]
the estimation error for ˆG(L2) within each cluster is bounded by ε with probability at least 1− δ. d) Ho-Kalman realization: Finally, we transfer the estimation error bounds for Markov parameters to bounds on estimating a realization by using a result on the robustness of the...
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.