{"id":"3407cffb-5f04-4476-a215-f52b07ff95f7","arxiv_id":"2501.18853","paper_version":5,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"Subspace identification is claimed to have O(1/sqrt N) finite-sample matrix errors, O(N^{-1/(2n)}) pole errors, and a super-polynomial sample complexity in n/m; the last claim is not proven.","lead":"This paper derives finite-sample error bounds for subspace identification of stochastic linear systems, claiming matrix errors shrink like 1/sqrt(N) and pole errors like N^{-1/(2n)}. It also claims that constant accuracy requires a super-polynomial sample size in the state-to-output ratio, a conclusion this review finds unsupported.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The advertised super-polynomial sample-complexity claim is not established: eqs. (32)-(33) are sufficient-sample conditions derived from upper bounds, not necessary lower bounds, and Lemma 2's appeal to Lemma 6 requires a normality assumption that Assumption 1 does not provide.","rationale":"The reader's REJECT verdict is supported: the central super-polynomial sample-complexity claim is load-bearing and is not justified. I agree with the reader that Lemma 6's normality requirement creates a gap in Lemma 2, and that the numerical experiments do not test the n/m scaling. I would place equal or greater weight on a separate logical flaw: eqs. (32)-(33) are phrased as necessary conditions ('must satisfy', 'requires'), but they are derived by inverting upper bounds on the estimation error, which can only produce sufficient sample-size conditions. Even if Lemma 2 were repaired, the advertised conclusion would still not follow unless a matching lower bound on the estimation error is proved. The matrix and pole error rates in Theorems 1-3 appear to follow from standard concentration and perturbation arguments, and the paper gives reasonable credit to prior work; the problem is localized to the third contribution. Since the reader already rejected on these grounds, I do not recommend changing the verdict.","tokens_in":18187,"tokens_out":8327,"duration_ms":93232,"concrete_test":"Independently re-derive eqs. (32)-(33) as genuine lower bounds on the sample size needed to reach constant error. If the derivation uses only Theorem 2 and Lemma 2 upper bounds, it cannot yield necessity; check whether replacing 'must satisfy' with 'is sufficient' makes the proof go through unchanged. Separately, test Lemma 2 numerically for a nonnormal A = P Lambda P^{-1} with P a 40x40 Hilbert matrix, eigenvalues uniformly spaced in [-1,1], C a unit row, and T = ceil(log N): if sigma_n(Gamma_T) does not obey the claimed 4 c k T m n rho^{-floor((n-1)/(2m))} log(2mT) bound, the normality hypothesis in Lemma 6 is indispensable.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's third advertised contribution — that constant-error identification 'requires' a super-polynomial sample size in n/m — is not supported by the proof. In Section 3, eqs. (32)-(33) are obtained by inverting the upper bounds of Theorem 2 and Lemma 2: the text concludes that N must be at least Omega(poly(n,m,log N) * rho^{...}). An upper bound on the estimation error gives a sufficient N, not a necessary one; no lower bound on the error of the SIM estimate or of any estimator is proved. Hence the abstract's 'requires' and Section 3's 'must satisfy' overstate the result. The technical basis is also fragile: Lemma 2's proof (Appendix 6.4) invokes Lemma 6 (Appendix 6.1) to upper-bound sigma_n(Gamma_T), but Lemma 6 assumes D is unitary diagonalizable, while Assumption 1 only gives A with real distinct eigenvalues in [-1,1] and no normality. Thus the super-polynomial decay of sigma_n(Gamma_T), and therefore the entire sample-complexity conclusion, is unproved under the paper's assumptions.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies finite-sample error bounds for subspace identification of discrete-time LTI stochastic systems with no external inputs. It derives high-probability upper bounds on the identification errors of A, C, and the Kalman gain K (Theorems 1 and 2), an upper bound on the decay of the smallest singular value of the block Hankel matrix (Lemma 2), and a bound on the Hausdorff distance between the true and estimated system poles (Theorem 3). The abstract and Section 6 further claim a super-polynomial sample size requirement in n/m for constant-error identification, expressed in eqs. (32) and (33).","tokens_in":18409,"tokens_out":4202,"duration_ms":47481,"significance":"The paper contains a genuinely useful concentration analysis for the block Hankel estimate and a clean robustness lemma for subspace identification; those parts are presented with explicit constants and detailed proofs. If the advertised sample-complexity and pole-rate results were valid, they would be a meaningful contribution to the finite-sample system identification literature. However, the central 'super-polynomial sample size is required' claim is not actually proved, and the singular-value lemma that drives it is applied outside its stated assumptions. The strength of the paper therefore rests on the Hankel-error and perturbation bounds, which may be salvageable, but the headline contributions as stated are not established.","major_comments":[{"comment":"The derivation of eqs. (32) and (33) is logically invalid. These equations are obtained by inverting the upper bounds of Theorem 2 and Lemma 2 and then concluding that N 'must satisfy' a lower bound of the displayed order. An upper bound on the estimation error of the form error <= f(N) implies a sufficient condition on N for the error to be below a target threshold; it does not imply that N has to be that large. No lower bound on the SIM estimation error, and no minimax or information-theoretic lower bound, is proved anywhere in the manuscript. Therefore the abstract's claim that constant-error identification 'requires' a super-polynomial sample size in n/m, and the analogous wording in Section 6, are unsupported. The authors should reframe these statements as sufficient sample-size conditions, or provide a genuine lower-bound argument.","section":"Section 3, eqs. (32)-(33); also Abstract and Section 6"},{"comment":"The proof of Lemma 2 applies Lemma 6 to the extended observability matrix Gamma_T, but Lemma 6 requires the base matrix D to be unitary diagonalizable with real eigenvalues. Assumption 1 only requires A to have real distinct eigenvalues in [-1,1] and does not imply that A, or the matrix D arising in the Krylov structure, is normal or unitary diagonalizable. Consequently the inequality sigma_n(Gamma_T) <= 4 rho^{-...} log(2mT) ||Gamma_T|| is not justified under the assumptions of the paper. Since Lemma 2 is used to obtain sigma_n(H_T) <= ... and hence eqs. (31)-(33), the super-polynomial decay of sigma_n(H_T) and all sample-complexity conclusions depending on it are unproved.","section":"Appendix 6.4, Lemma 2 proof; Appendix 6.1, Lemma 6"},{"comment":"The advertised pole-rate O(N^{-1/(2n)}) is a corollary of Theorem 3 and Lemma 2 through the quantity Delta in eq. (38). Because Lemma 2 is not established under Assumption 1 (see the previous comment), the pole-rate claim is not established either. Additionally, even if Lemma 2 were available, the rate statement uses eq. (37) with Delta containing T^5 and sigma_n(H_T); the paper does not verify that the condition of Theorem 3, namely the perturbation bound ||H_T - hat H_T|| <= sigma_n(H_T)/4, is satisfied with high probability by the sample bound of Theorem 1. This is a conditional statement, but the paper presents it as an unconditional rate result.","section":"Section 4 and Theorem 3"}],"minor_comments":[{"comment":"The statement of Lemma 3 introduces a matrix M but the inequalities are written for A; please replace M with A for consistency.","section":"Appendix 6.1, Lemma 3"},{"comment":"The notation hat K_T(:, -m:-1) for the last m columns should be explicitly defined, since negative-index slicing is not standard in all readers' conventions.","section":"Section 2.1, eq. (19)"},{"comment":"The phrase 'decreases at a rate of at least O(...)' is misleading: an upper bound of order O(1/sqrt N) means the error decreases no slower than 1/sqrt N, so the standard phrasing is 'at most O(...)' or 'with high probability bounded by O(...)'.","section":"Abstract and Section 6"},{"comment":"The caption's subfigure indices are confusing: the text refers to subfigures (b) and (e) for pole errors, but the caption lists the pole error panels as (b) and (e) after (a) and (d); please check that the references in the text match the actual arrangement.","section":"Section 5, Figure 2"}],"recommendation":"reject","confidential_remarks":"The main reasons for rejection are the invalid inference from upper bounds to necessary sample size in eqs. (32)-(33) and the inapplicability of Lemma 6 to the non-normal matrices allowed by Assumption 1. Both are load-bearing for the paper's headline claims, and fixing them would require either a substantive lower-bound proof or a new singular-value analysis for non-normal A, which goes well beyond local revision. The concentration bound for the block Hankel estimate and the perturbation analysis may be publishable as a separate contribution if the overclaimed conclusions are removed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the matrix and pole bounds are real, the concentration argument is mostly coherent, and the paper deserves a serious referee. But the headline result about super-polynomial sample complexity in n/m is not proved, and the proof as written relies on an imported lemma whose assumptions don't match the paper's setting.\n\nWhat's good: Theorem 1's analysis of the block Hankel regression error is careful. The three-step split — lower bound on the past-output covariance, cross-term bound, and Kalman truncation bias — is standard but executed cleanly, and the resulting O((log N)^{5/2}/sqrt(N)) rate with T ~ Theta(log N) is consistent with prior work. Lemma 1's perturbation bound is useful, and Theorem 3's pole bound is a legitimate corollary of the matrix bound plus eigenvalue perturbation theory. The simulations show the predicted matrix and pole trends, though they don't stress the n/m scaling.\n\nThe soft spots are where the reader's report finds them, and they are load-bearing for the advertised contribution. Equations (32)-(33) invert upper bounds and conclude that N 'must satisfy' a super-polynomial condition. That's logically invalid: an upper bound on the error gives a sufficient N to reach a target accuracy, not a necessary one. No lower bound on the estimation error of the SIM estimator or any estimator is proved. So the abstract's 'requires' should be downgraded to 'the upper bound has this shape' unless a real lower bound appears. That's still an interesting observation, but it is not the negative result the abstract claims.\n\nThe second issue is Lemma 2's use of Lemma 6. Lemma 6 assumes D is unitary diagonalizable, while Assumption 1 only gives A with real distinct eigenvalues in [-1,1]. Distinct real eigenvalues imply diagonalizability over the reals, not normality, so the lemma does not apply as stated. It's possible a similar super-polynomial upper bound holds for the non-normal case, but the paper doesn't prove it. This is fixable: the authors should either prove the needed version under Assumption 1 or restate the claim.\n\nWho this is for: people working on finite-sample guarantees for subspace identification and output-feedback LTI systems. I would send it to peer review, not desk reject, because the core matrix analysis is competent and the structural questions are worth hashing out. But it needs major revision before acceptance: fix the upper-bound/lower-bound conflation and close the Lemma 6 gap.","headline":"Finite-sample matrix and pole bounds for SIM are solid and worth a referee's time, but the advertised super-polynomial sample-complexity lower bound is not established and the key imported lemma has a mismatch with the paper's own assumptions.","tokens_in":18941,"tokens_out":3224,"would_cite":false,"duration_ms":36566,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["93E12","93B30"],"pacs":[],"model":"deepseek-v4-flash","headline":"Finite-sample subspace identification of stochastic LTI systems achieves $O(1/\\sqrt{N})$ error for $A,C,K$, $O(N^{-1/(2n)})$ for poles, and needs super-polynomial samples in the state-to-output ratio for constant error.","keywords":["system identification","subspace identification method","finite sample analysis","stochastic LTI systems","block Hankel matrix","sample complexity","system poles","Kalman filter gain"],"falsifier":"Compute the smallest singular value $\\sigma_n(H_T)$ for a non-normal but diagonalizable $A$ with real distinct eigenvalues in $[-1,1]$, for example $A=PDP^{-1}$ with $D=\\mathrm{diag}(0.99,0.98,\\dots)$ and a badly conditioned $P$, with $m=1$ and $T\\approx\\log N$, and compare it with the bound $\\rho^{-(n-1)/(2m)}\\log(2mT)$. If $\\sigma_n(H_T)$ does not decay at that super-polynomial rate, Lemma 2 and the derived sample complexity fail; if it does decay, the paper's hardness conclusion survives for non-normal systems.","tokens_in":17948,"feed_emoji":"📉","tokens_out":7665,"duration_ms":67161,"temperature":0.7,"pith_summary":"This paper tries to prove that the subspace identification method (SIM), applied to an $n$-dimensional discrete-time linear time-invariant system with no external inputs and $m$ outputs, has finite-sample error guarantees driven by the number $N$ of independent output trajectories. The claimed rates, up to logarithms, are $O(1/\\sqrt{N})$ for the estimated system matrices $A$, $C$, and the Kalman gain $K$, and $O(N^{-1/(2n)})$ for the estimated system poles. The paper also claims that forcing the estimation error below a constant requires a sample size that grows super-polynomially in the state-to-output ratio $n/m$, because the smallest singular value of the associated block Hankel matrix decays super-polynomially. A reader should care because these are non-asymptotic, data-independent bounds for a widely used identification method in the stochastic, input-free setting.","feed_headline":"Stochastic system identification: matrix errors shrink at 1/√N","feed_subtitle":"New bounds show pole estimates lag at N^{-1/(2n)}; constant accuracy needs super-polynomial samples in n/m.","key_machinery":"The load-bearing object is the block Hankel matrix $H_T=\\Gamma_T K_T$ built from the extended observability matrix of $(A,C)$ and the reversed extended controllability matrix of $(A-KC,K)$ in the innovation form. Its smallest nonzero singular value $\\sigma_n(H_T)$ controls the robustness of the whole SIM pipeline: the perturbation lemmas show that errors in $A$, $C$, $K$ are bounded by multiples of $\\|\\widehat H_T-H_T\\|/\\sqrt{\\sigma_n(H_T)}$, while Lemma 2 upper-bounds $\\sigma_n(H_T)$ by a quantity decaying super-polynomially in $n/m$. The second object is the regression identity $\\widehat H_T=Y_f Y_p^\\dagger$, whose error splits into a Gaussian cross term and a Kalman-filter truncation bias; Gaussian concentration bounds on $Y_pY_p^\\top$ and on the cross terms supply the $1/\\sqrt N$ rate once $T\\sim\\log N$.","core_discovery":"The central claim is an end-to-end finite-sample analysis of SIM for a minimal stochastic LTI system in innovation form. The estimate $\\widehat H_T$ of the block Hankel matrix $H_T=\\Gamma_T K_T$ is formed by least-squares regression of future outputs on past outputs, then rank-$n$ truncated and factored to recover $\\widehat\\Gamma_T$ and $\\widehat K_T$, and hence $\\widehat A$, $\\widehat C$, and $\\widehat K$ up to a unitary similarity. The paper proves that with $T$ of order $\\log N$ the regression error is $O((\\log N)^{5/2}/\\sqrt N)$, and that this error propagates to $A$, $C$, $K$ at the same $1/\\sqrt N$ rate scaled by $n/\\sigma_n(H_T)$, because $\\sigma_n(H_T)$ controls how near-observable the weakest mode is. For the poles, the Hausdorff distance between true and estimated spectra is bounded by a power of the $A$-error, yielding the slower $N^{-1/(2n)}$ rate. The same $\\sigma_n(H_T)$ bound implies that the sample size needed for constant error grows like a power of $\\rho^{(n-1)/(2m)}$ with $\\rho=e^{\\pi^2/4}$, i.e., super-polynomially in $n/m$.","pith_inferences":["Inference: The super-polynomial sample complexity suggests that SIM-style identification is impractical for large $n/m$ in the no-input regime; a natural extension would be to test whether adding a known excitation input removes the $\\sigma_n(H_T)$ penalty, since the paper's proof is restricted to the input-free case.","Inference: Because the pole bound passes through the Hausdorff distance via an $n$-th root, the $N^{-1/(2n)}$ rate is a worst-case over all $n$ poles; a finer per-pole analysis might show that only the weakly observable modes suffer the slow rate.","Inference: The same $\\sigma_n(H_T)$ decay mechanism would likely appear in any identification method that reconstructs $A$ from a finite Hankel matrix of output covariances, suggesting the hardness is a property of the problem rather than of SIM specifically; a comparison against a least-squares innovation-form estimator would test this.","Inference: The numerical experiments cover only $n=4$; a direct check of the super-polynomial prediction would evaluate $\\sigma_n(H_T)$ for non-normal $A$ with real distinct eigenvalues and increasing $n/m$."],"forward_implications":["With $T$ chosen as $\\Theta(\\log N)$, the matrix identification errors $\\|\\widehat C-CU\\|$, $\\|\\widehat K-U^\\top K\\|$, and $\\|\\widehat A-U^\\top AU\\|$ for a unitary $U$ fall at least as fast as $(\\log N)^{O(1)}/\\sqrt N$ with high probability.","The Hausdorff distance between the true poles and the estimated poles falls at least as $N^{-1/(2n)}$, meaning the pole estimates converge more slowly for larger state dimension.","For a constant-error target, the required number of trajectories must scale at least super-polynomially in $n/m$; high-dimensional state spaces with few outputs are therefore fundamentally harder for SIM-based identification.","The finite-sample guarantees are data-independent: they depend on $N$, $n$, $m$, $T$, noise covariances, and entry-size bounds for $C$ and $K$, not on the particular observed trajectories.","In the input-free setting, noise plays a double role: it excites the modes needed for identifiability, but it also inflates the least-squares cross term, a trade-off captured by the appearance of $\\lambda_{\\min}(R)$ in the denominator."],"supporting_citations":[{"why":"Supplies the prior finite-sample stochastic system identification bound that this paper extends, and the comparison point for the new matrix and pole rates.","marker":"[32]"},{"why":"Supplies the Hankel-matrix robustness lemma and the Ho-Kalman style perturbation framework used to convert regression error into realization error.","marker":"[35]"},{"why":"Provides the Krylov-matrix singular-value bound (Lemma 6) that produces the super-polynomial decay of $\\sigma_n(H_T)$; the sample-complexity claim stands on it.","marker":"[45]"},{"why":"Supplies the Gaussian cross-term concentration bound (Lemma 4) used to control the noise term in the Hankel estimate.","marker":"[30]"},{"why":"Supplies the two-sided Gaussian smallest-singular-value bounds used for persistent excitation of the past output matrix.","marker":"[44]"},{"why":"Provides the deterministic SIM error analysis whose steps are followed for the pole robustness theorem.","marker":"[42]"},{"why":"Supplies the spectral-variation bound that turns the estimated-$A$ error into the Hausdorff pole error.","marker":"[46]"},{"why":"Supplies the low-rank matrix perturbation bound used to show that SVD recovery of $\\Gamma_T$ and $K_T$ is Lipschitz in the Hankel error.","marker":"[47]"},{"why":"Supplies the pseudo-inverse perturbation inequality used to bound the error of $A$ recovered from estimated observability matrices.","marker":"[48]"}],"fun_headline_variants":["Matrix errors shrink at 1/√N, but poles pay a penalty","Finite-sample subspace ID: 1/√N matrices, slower poles","Super-polynomial samples needed for constant accuracy","Subspace ID: matrix errors easy, pole errors hard"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The conclusion that constant-error identification needs super-polynomial sample size rests on a singular-value bound imported from another paper that assumes the system matrix is unitarily diagonalizable (normal), whereas the main theorem here only assumes real distinct eigenvalues; if that imported bound does not apply to non-normal $A$, the super-polynomial sample-complexity claim is unsupported.","fun_headline_variants_meta":{"raw":{"variants":["Matrix errors shrink at 1/√N, but poles pay a penalty","Finite-sample subspace ID: 1/√N matrices, slower poles","Super-polynomial samples needed for constant accuracy","Subspace ID: matrix errors easy, pole errors hard"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000608,"raw_usage":{"total_tokens":2865,"prompt_tokens":1009,"completion_tokens":1856,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":625,"completion_tokens_details":{"reasoning_tokens":1784}},"tokens_in":625,"tokens_out":1856,"duration_ms":15401,"temperature":1.0,"reasoning_tokens":1784,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T22:13:29.815563+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the smallest singular value $\\sigma_n(H_T)$ for a non-normal but diagonalizable $A$ with real distinct eigenvalues in $[-1,1]$, for example $A=PDP^{-1}$ with $D=\\mathrm{diag}(0.99,0.98,\\dots)$ and a badly conditioned $P$, with $m=1$ and $T\\approx\\log N$, and compare it with the bound $\\rho^{-(n-1)/(2m)}\\log(2mT)$. If $\\sigma_n(H_T)$ does not decay at that super-polynomial rate, Lemma 2 and the derived sample complexity fail; if it does decay, the paper's hardness conclusion survives for non-normal systems.","supporting_citations":[{"cited_title":"Zheng, L","cited_arxiv_id":null,"evidence_quote":"Supplies the prior finite-sample stochastic system identification bound that this paper extends, and the comparison point for the new matrix and pole rates."},{"cited_title":"Zheng, N","cited_arxiv_id":null,"evidence_quote":"Supplies the Hankel-matrix robustness lemma and the Ho-Kalman style perturbation framework used to convert regression error into realization error."},{"cited_title":"Rudelson, R","cited_arxiv_id":null,"evidence_quote":"Provides the Krylov-matrix singular-value bound (Lemma 6) that produces the super-polynomial decay of $\\sigma_n(H_T)$; the sample-complexity claim stands on it."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the two-sided Gaussian smallest-singular-value bounds used for persistent excitation of the past output matrix."},{"cited_title":"Hausdor ff, Grundz ¨uge der mengenlehre, V ol","cited_arxiv_id":null,"evidence_quote":"Provides the deterministic SIM error analysis whose steps are followed for the pole robustness theorem."},{"cited_title":"Elsner, An optimal bound for the spectral variation of two 13 matrices, Linear algebra and its applications 71 (1985) 77–80","cited_arxiv_id":null,"evidence_quote":"Supplies the low-rank matrix perturbation bound used to show that SVD recovery of $\\Gamma_T$ and $K_T$ is Lipschitz in the Hankel error."},{"cited_title":"Low-rank Solutions of Linear Matrix Equations via Procrustes Flow","cited_arxiv_id":"1507.03566","evidence_quote":"Supplies the pseudo-inverse perturbation inequality used to bound the error of $A$ recovered from estimated observability matrices."}],"review_version":1}