Learning structured linear dynamical systems from missing observations

1 INTRODUCTION

• The problem is to identify an unknown transition matrix from one dependent state trajectory when each state entry is observed with probability p; missing entries may be zero-imputed.Dependencies among the states make recovery analysis challenging.Source: §1 · pp. 1–2

1.2 Related work

• Prior guarantees for structured LDSs with missing observations focus mainly on sparse or low-rank matrices, while the paper addresses general closed convex constraints.Source: §1 · p. 2, §1.2 · p. 2, §1.1 · p. 2

1.1 Our contributions

• The constrained estimator minimizes a potentially non-convex, bias-corrected least-squares objective, with high-probability Frobenius error bounds governed by the tangent cone’s local complexity.The local complexity is measured by Talagrand’s γ1 and γ2 functionals.Source: §1.1 · p. 2
• Projected gradient descent iterates converge linearly with high probability to A∗ up to the statistical error bound.Source: §1.1 · p. 2
• The theory covers subspaces, bi-isotonic matrices, and matrices formed by sampling Lipschitz functions, extending structured LDS recovery guarantees to missing observations.The authors describe these results as new for these examples, while existing work on missing observations focuses primarily on sparsity and low-rank structures.Source: §1.1 · p. 2
• Under strict stability and suitable T and p, the results establish meaningful recovery when T = o(n^2) and p = o(1) with respect to T.For the unstructured case with p = 1, T ≳ n^2 is necessary for meaningful recovery.Source: §1.1 · p. 2

2.2 Problem setup and estimator

• The model assumes a VAR transition A* in a known closed convex set K, centered i.i.d. subgaussian unit-variance noise, and Bernoulli subsampling of observations.The objective’s population loss is equivalent to the full-information population loss when p>0, and PGD is used because the objective may be nonconvex.Source: §2.2 · p. 3

2.3 Preliminaries

• The analysis uses tangent cones and Gaussian-width or Talagrand complexity measures, alongside a stability quantity J(A*) that is bounded for strictly stable A*.The stated results are meaningful when J(A*) is small or grows mildly with dimension.Source: §2.3 · p. 4

2.4 Main result

• Theorem 1 gives an error bound; Remark 5 states that for fixed δ, ||b_A - A*||_F=o(1) even as p=o(1), under a sufficient condition.Source: §2.4 · pp. 4–5
• With high probability, PGD iterates approach a small ball around A*, with geometric contraction and an additive error on the scale of the statistical error.Theorem 1 bounds the global minimizer, while Theorem 2 controls the PGD iterates; the learning rate depends on J(A*).Source: §2.4 · pp. 4–5
• For some constraint sets, including the sparse-matrix setting described, the general convex-set bounds may be suboptimal and require specialized analysis for optimal guarantees.The passage attributes this limitation to the difficulty of bounding γ1.Source: §2.4 · p. 5

3.1 Proof sketch of Theorem 1

• For Theorem 1, conditioning on the observation masks and applying Krahmer et al. (2014) controls positive-semidefinite quadratic forms, yielding a lower bound on (I).The bounds incorporate Talagrand’s γ2 complexity; additional mask-dependent quadratic and linear terms are controlled using Theorem 3 and Wainwright (2019).Source: §3.1 · p. 5
• For (II), Dirksen (2015) controls non-positive-semidefinite quadratic forms using γ1 and γ2, while Wainwright (2019) controls linear terms; combining the bounds yields the final result.The proof first conditions on the observation masks and expresses terms as quadratic forms and linear forms over suitable sets.Source: §3.1 · pp. 5–6

3.2 Proof sketch of Theorem 2

• For Theorem 2, Lemmas 16–18 bound the three gradient terms using norm and eigenvalue bounds and concentration of suprema of random quadratic forms.The latter bounds use Dirksen (2015)’s concentration inequality.Source: §3.2 · p. 6
• Grouping the bounds and imposing ρ < 1 through sufficient condition (2.2) yields Theorem 2 by unrolling the recurrence and applying the triangle inequality twice.Source: §3.2 · p. 6

4.1 d-dimensional subspace

• Corollary 2 assumes a condition on γ and states that ρ ≤ 1 − 1/(cJ²(A*)), where c > 1.Source: §4.1 · p. 6

4.2 Bi-isotonic regression

• For bi-isotonic matrices, Corollary 3 gives a high-probability bound involving k(A*), the minimum number of rectangular blocks on which A* is constant.The text states that k(A*) ranges from 1 to n^2; when k(A*) = n^2, the rate matches Corollary 1 with d = n^2, while k(A*) = o(n^2) is the structured regime.Source: §4.2 · p. 7
• The bi-isotonic bounds use Gaussian-width and statistical-dimension estimates alongside metric-entropy bounds split between coarse and fine scales.At the fine scale, the argument uses a sharp entropy-number estimate.Source: §4.2 · p. 7

5 EXPERIMENTS

• The experiments focus on the non-convex regime with n = 100, exploring PGD numerically for subspace and bi-isotonic examples while deferring Lipschitz regression results to Appendix I.Runs used a 2025 MacBook Air with a 10-core M4 chip and 16GB of RAM.Source: §5 · p. 8

5.1 Subspace

• The subspace study covers 36 combinations of p ∈ {0.3, 0.5, 0.9}, T ∈ {50, 250, 500, 1000}, and d ∈ {5, 15, 30}, with 500 Monte Carlo replications per configuration.For each d, the subspaces are generated from Gaussian matrices followed by QR orthonormalization.Source: §5.1 · p. 8
• The subspace experiment estimates a T exponent around 0.51, close to the theoretical T^-1/2 rate, and a p exponent around 1.1, below the theoretical p^-2 bound.Figure 1 summarizes the empirical log-log rates.Source: §5.1 · p. 8, Figure 1 · p. 8

5.2 Bi-isotonic regression

• For bi-isotonic matrices, Figure 2 reports relative Frobenius errors as median curves with 25th–75th percentile bands; low T and p produce extreme outliers when data are insufficient for the class complexity.Each configuration uses 200 replications.Source: §5.2 · p. 8, Figure 2 · p. 8

AI use statement

• The paper states that generative AI tools were not used for any task pertaining to the paper.Other required disclosure tasks are reported as not applicable.Source: AI use statement · p. 9

A TECHNICAL TOOLS

• The technical appendix gives comparison, subset, and Lipschitz-map properties of Talagrand’s γα functionals, and notes that metric entropy can upper-bound them.The properties support bounding γα across related metric spaces and via covering numbers.Source: A TECHNICAL TOOLS · p. 13
• The appendix also assembles concentration tools for quadratic chaos processes from Krahmer et al. (2014), Dirksen (2015), and Wainwright (2019).The cited results cover positive-semidefinite and general matrix settings, as well as a convex Lipschitz concentration theorem.Source: A TECHNICAL TOOLS · pp. 13–14

B PROOF OF LEMMA 1

• The proof abbreviates F for the remainder and begins by considering expectations over the sampling matrices P_t.The expectation is denoted E_P[·].Source: B PROOF OF LEMMA 1 · p. 14
• The matrix S is given by S = p^2 11^T + p(1 − p)I, where 1 is the all-ones vector in R^n.Source: B PROOF OF LEMMA 1 · p. 14
• The proof uses independence of P_t and P_{t+1}, and notes that μ and F do not depend on A.Source: B PROOF OF LEMMA 1 · p. 15

C PROOF OF THEOREM 1

• Lemma 4 relates the objective minimizer to any feasible B ∈ K, using optimality of the minimizer and feasibility of B.Its proof sketch invokes g(bA) ≤ g(B) and reorders terms.Source: C PROOF OF THEOREM 1 · pp. 15–16
• Lemmas 5 and 6 provide probability-at-least-1−δ upper bounds for the left- and right-hand sides of equation C.1, respectively.The proof uses these bounds to complete the theorem argument.Source: C PROOF OF THEOREM 1 · p. 16
• Theorem 1 follows by combining the bounds from Lemmas 5 and 6 with Lemma 4 under the stated condition on T.The proof assumes T ≥ c p4 v for a sufficiently large constant c.Source: C PROOF OF THEOREM 1 · pp. 16–17

• The proof fixes the solution bA ∈ K minimizing g(A) in (2.1) and compares it with any feasible B ∈ K.Source: D PROOF OF LEMMA 4 · p. 17
• Intercalating by B rewrites the left-hand side of (D.1).Source: D PROOF OF LEMMA 4 · p. 17
• Substitution into (D.1), followed by intercalation by A∗, gives the next expression.Source: D PROOF OF LEMMA 4 · p. 17
• The proof applies Cauchy–Schwarz and combines the resulting bound with (D.2).Source: D PROOF OF LEMMA 4 · p. 18

E PROOF OF LEMMA 5

• Conditioning on the sampling matrices is necessary because Theorem 3’s standard argument does not directly handle randomness in both the sampling matrices and noise; combining events yields the desired bound with probability at least 1−5δ.The proof conditions on the sampling matrices before bounding terms, then combines events E1a, E2a, E1b, E2b, and E3b.Source: E PROOF OF LEMMA 5 · pp. 18, 22

E.6 Proof of Lemma 11

• Lemma 11’s proof applies Theorem 5 to sets R and S formed from maps of matrices in CB.The proof also uses the diagonal structure of P.Source: E PROOF OF LEMMA 5 · p. 21, §E.6 · pp. 31–32

E.1 Proof of Claim 1

• Claim 1’s setup identifies Z_:,t as the t-th column of Z.The proof of Claim 1 is deferred to Appendix E.1.Source: E PROOF OF LEMMA 5 · p. 18, §E.1 · p. 22

E.2 Proof of Lemma 7

• Lemma 7’s proof applies Theorem 3 to a matrix set, then relates its bounds to tangent cone CB via an onto mapping.The resulting probability bound is conditional on the sampling matrices.Source: E PROOF OF LEMMA 5 · p. 19, §E.2 · pp. 23–24

E.3 Proof of Lemma 8

• Lemma 8’s proof applies Theorem 3 to a matrix set and relates its bounds to CB in a similar way.The probability bound is obtained conditional on the sampling matrices.Source: E PROOF OF LEMMA 5 · p. 19, §E.3 · pp. 25–26

E.4 Proof of Lemma 9

• To prove Lemma 9, the authors construct an auxiliary matrix for the Hadamard-product term and invoke Visick (2000).They then apply Theorem 3 to an appropriately defined matrix set.Source: E PROOF OF LEMMA 5 · p. 21, §E.4 · p. 26

E.5 Proof of Lemma 10

• Lemma 10’s proof applies Theorem 3 and proceeds as in the proof of Claim 2.The proof then derives a probability bound for its matrix-set terms.Source: §E.5 · pp. 29–30

E.6 Proof of Lemma 11

• The argument uses q, whose entries are i.i.d., centered, and bounded in [−1, 1].Source: §E.6 · p. 33
• With probability at least 1 −2δ, the combined events E1c and E2c yield the stated bound for all A in CB.The bound holds for a suitably large constant c.Source: §E.6 · p. 33
• Claims 6 and 7 consider pairs of matrices in CB and their corresponding Rmat and Smat objects, respectively.Source: §E.6 · pp. 33–34

F PROOF OF LEMMA 6

• The proof of Lemma 6 is organized around bounding three terms.The final argument combines bounds on the event E1d ∩ E2d ∩ E3d.Source: F PROOF OF LEMMA 6 · p. 34

F.3 Proof of Lemma 12

• Lemma 12’s proof applies Theorem 4 to zero-mean, L-subgaussian noise after establishing Lipschitz maps.The resulting probability bound is stated conditional on the sampling matrices.Source: F PROOF OF LEMMA 6 · pp. 36–37, §F.3 · p. 42

F PROOF OF LEMMA 6

• The Lemma 12 and Lemma 13 probability bounds yield events E1d and E2d, which are combined with E3d to bound the indexed random-matrix class.The closing argument states the bound on the intersection E1d ∩ E2d ∩ E3d.Source: F PROOF OF LEMMA 6 · pp. 37, 39

F.1 Proof of Claim 8

• The Claim 8 proof uses the state recursion and observation equation to derive expressions involving adjacent sampling matrices and states.It starts from xt+1 = A∗xt + ηt+1 and yt = Ptxt.Source: §F.1 · p. 40

F.4 Proof of Lemma 13

• Lemma 13’s proof applies Theorem 4 to centered, 1-subgaussian entries of q and establishes Lipschitz maps for the indexed matrix class.The proof identifies the event E2d with probability at least 1 − δ.Source: F PROOF OF LEMMA 6 · p. 39, §F.4 · p. 44

F.5 Proof of Lemma 14

• Lemma 14’s proof reduces the trace expression to diagonal entries and applies Theorem 5 to a Lipschitz map.The diagonal entries are represented as vectors h(A); the resulting probability statement is uniform over A ∈ CB.Source: §F.5 · pp. 46–47

G PROOF OF THEOREM 2

• Under the sufficient condition, the proof makes the recurrence contract and unrolls it to obtain Theorem 2’s high-probability bound.The argument then simplifies the bound under the sufficient condition on T.Source: G PROOF OF THEOREM 2 · p. 49

Recall the projected gradient descent (PGD) algorithm

• PGD updates A(k) using a learning rate and projects onto K, with ΠK denoting orthogonal projection.The iteration A(k) is computed from the data.Source: Recall the projected gradient descent… · p. 49
• Lemmas 16 and 17 state iteration guarantees for a learning rate chosen in terms of p, T, and J2(A*).The guarantees apply for all k; Lemma 17 states its bound with probability at least 1 − δ.Source: Recall the projected gradient descent… · pp. 50–51
• The Lemma 17 proof bounds a quadratic form over the tangent cone using Theorem 4, with subgaussian rescaling affecting only constants.The proof notes that A(k) and B lie in the tangent cone and the resulting bound holds with probability at least 1 − δ.Source: Recall the projected gradient descent… · pp. 51–52
• Lemma 18 supplies a high-probability bound with positive constants.It holds with probability at least 1 − δ.Source: Recall the projected gradient descent… · p. 53
• Lemma 19 gives a projection inequality for a closed convex set; its proof follows Lv et al. (2021) and Mordukhovich and Nam (2023).The cited proof relies on Example 2.32 of Mordukhovich and Nam (2023).Source: Recall the projected gradient descent… · p. 54

H.1 Proof of Corollary 5

• Since A*∈K, there exists B∈K whose rows each consist of l+1 affine pieces with slopes ±L and adjacent entries differing by L; l is chosen by balancing the first two terms.Source: §H.1 · pp. 54–55

H.2 Proof of Corollary 6

• The Corollary 6 proof bounds the factors in Theorem 2 under its sufficient condition and uses those bounds to derive the final error bound.It also establishes a contraction factor for the resulting bound.Source: §H.2 · pp. 56–57

H.3 Proof of Lemma 2

• The Lemma 2 proof scales the Gaussian noise using projection homogeneity and applies Talagrand’s majorizing-measures theorem to the tangent-cone projection.The noise entries are independent centered Gaussians with variance σ^2.Source: §H.3 · pp. 57–58

H.4 Lemma 20 and its proof

• Lemma 20 uses a double-net argument: it covers the local set with Frobenius balls, then covers each residual with spectral balls.This approximates each H by a Frobenius-net center plus a spectral-net residual center.Source: §H.4 · p. 58

H.5 Lemma 21 and its proof

• Lemma 21 translates identity-operator entropy-number estimates into covering bounds for Frobenius balls by spectral balls across two scale regimes.The proof treats n ≤ j ≤ n^2 and j ≥ n^2 separately, using Hinrichs et al. (2017).Source: §H.5 · p. 59

H.6 Proof of Lemma 3

• The Lemma 3 proof combines entropy-integral estimates with Sudakov’s minorization inequality and Lemmas 20 and 21, then balances the terms over r.The proof substitutes the optimizing choice of r into the resulting bound.Source: §H.6 · pp. 59–60

I.1 Corollaries of Theorems 1 and 2

• Corollary 5 bounds recovery for matrices whose rows sample L-Lipschitz functions, using a piecewise-linear approximation to balance recovery and misspecification error.The approximating matrix has l + 1 affine pieces per row, with slopes ±L.Source: §I.1 · p. 60
• For p = 1, Corollary 5 recovers Tyagi and Efimov (2024, Corollary 4) up to constants and a J(A∗) factor.Source: §I.1 · p. 61
• Corollary 6 gives a probability-at-least-1−δ guarantee for every PGD iterate when the learning rate is γ = 1/(2p^2T J^2(A∗)).The supplied passage does not include the displayed bound on the iterates.Source: §I.1 · p. 61
• Each row projection in Lipschitz regression is a convex quadratic program with n variables and O(n) linear constraints, solvable in polynomial time by interior-point methods.Source: §I.1 · p. 61

I.2 Experiments

• The experiments construct row-wise Lipschitz transition matrices by integrating piecewise-constant random slopes bounded by L.The functions use Gaussian intercepts, and matrices are retained only when their spectral radius is at most 0.8.Source: §I.2 · p. 61
• Experiments use n = 100, T ∈ {100, 200, 400}, p ∈ {0.3, 0.5, 0.9}, L ∈ {1, 1.5}, and 200 replications per configuration.Figure 3 reports absolute Frobenius errors as medians with 25th-to-75th-quantile bands.Source: §I.2 · pp. 61–62, Figure 3 · p. 62
• Errors generally worsen as L increases and move in the same direction as T; for L = 1.5 and p ∈ {0.3, 0.5}, errors slightly increase from T = 100 to T = 200.The authors attribute this exception to PGD instability at short trajectory lengths, where the maximum iteration count was reached before convergence.Source: Figure 3 · p. 62, §I.2 · p. 62