Discovery.Linear­Disentanglement

Linear causal disentanglement: model layer

Formalization of the setup of Squires, Seigal, Bhate & Uhler, Linear Causal Disentanglement via Interventions (ICML 2023), arXiv:2211.16467.

We work over d latent variables (Fin d) and p ≥ d observed variables (Fin p). The latent DAG 𝒢 is ordered so that an edge j → i implies j > i; this makes the structural matrices upper triangular in the Fin d order.

For a fixed context, the latent SEM is Z = A Z + Ω^{1/2} ε, equivalently Z = B⁻¹ ε with B = Ω^{-1/2}(I − A). The observed vector is X = G Z with G ∈ ℝ^{p×d} full column rank, and H := G⁺ its left inverse (a full-row-rank d × p matrix with H G = I_d). The only observable content is the family of precision matrices Θ_k = Hᵀ Bₖᵀ Bₖ H ∈ ℝ^{p×p} (one per context).

We take the algebraic (matrix-level) view of the paper's Theorem 2: the data of a disentanglement model is a tuple (H, {B_k}, {i_k}, {λ_k}) satisfying the structural assumptions, and identifiability compares two such tuples that produce the same family {Θ_k}. No Moore–Penrose pseudoinverse is needed: H enters only through LinearIndependent ℝ H (full row rank) and the formula for Θ_k.

Conventions for a Solution d p K: * context 0 is observational with matrix B0; contexts 1 … K are interventional with matrices Bint k, intervention target target k, and (perfect-intervention) scaling lam k > 0; * Edge j i means the latent edge j → i (j a parent of i), forced by hAcyc to satisfy i < j; * B0 is upper triangular (B0 i j = 0 for j < i), has positive diagonal, and its off-diagonal support is exactly Edge — this is what defines 𝒢; * hInt is Assumption 1(b) specialized to perfect interventions (Assumption 2): Bₖ = B₀ + e_{iₖ} cₖᵀ with cₖ = λₖ e_{iₖ} − B₀ᵀ e_{iₖ}.

S(𝒢) is the set of node relabelings preserving edge orientation (Edge j i → σ i < σ j); permMat σ is the corresponding permutation matrix (P_σ)_{ij} = ⟦i = σ j⟧, matching the paper.

Linear causal disentanglement: graph order and the partial-order RQ decomposition

We package the graph-theoretic notions used throughout (parents, ancestors, and the partial order ≺_𝒢 with i ≺ j ↔ j ∈ an(i)), and the partial order RQ decomposition of the paper (Definition 1, Appendix B): a generalization of the reduced RQ decomposition where the upper-triangular support of R is replaced by the partial order, and orthogonality of the rows of Q is required only along the order. porq_exists / porq_unique are its existence and uniqueness (their Proposition in Appendix B), proved there by the Gram–Schmidt-style construction in Algorithm "Partial Order RQ Decomposition".

Linear causal disentanglement: identifiability up to S(𝒢) and signed scaling

Flagship Theorem 2.

The headline result of Squires, Seigal, Bhate & Uhler, Linear Causal Disentanglement via Interventions (ICML 2023), Theorem 2 (thm:main_id_non_constructive), in its algebraic (matrix-level) form.

Under Assumption 1 (linear latent model, single-node interventions, linear observations) and Assumption 2 (perfect interventions), with one intervention per latent node, the latent graph and intervention targets are identifiable up to S(𝒢), the order-preserving relabelings, while the latent directions are identifiable only up to nonzero signed diagonal scaling. The signed diagonal is unavoidable because the observable precision matrices are even in H.

The (⊆) inclusion is disentanglement_uniqueness; the (⊇) inclusion is sigma_solutions.

Linear causal disentanglement: the key rank-one identity

The algebraic backbone of the identifiability results (Squires–Seigal–Bhate–Uhler, §3.1). fact_transpose_mul is the rank-one decomposition BᵀB = Σᵢ (Bᵀeᵢ)⊗²; key_identity (their Proposition driving everything) computes the difference of precision matrices between an interventional and the observational context as a difference of two rank-one (outer-product) matrices, using that a single-node intervention changes only one row of B.

Linear causal disentanglement: the rowspan inclusion lemma (Lemma 1)

The technical heart linking the observable precision differences to the latent graph structure (their Lemma 1). By key_identity, rowspan(Θₖ − Θ₀) is spanned by the two vectors Hᵀ Bₖᵀ e_{iₖ}, Hᵀ B₀ᵀ e_{iₖ}, both lying in ⟨hᵢ : i ∈ Pa(iₖ)⟩. Full row rank of H makes this containment characterize the parent set:

* (a) rowspan(Θₖ − Θ₀) ⊆ ⟨hᵢ : i ∈ 𝓘⟩ iff Pa(iₖ) ⊆ 𝓘; * (b) rowspan(Θₖ − Θ₀) ⊆ ⟨qᵢ : i ∈ An(iₖ)⟩; * (c) if the intervention changes the precision matrix, 𝓘 is ancestor-closed, and Pa(iₖ) ⊄ 𝓘, then rowspan(Θₖ − Θ₀) ⊄ ⟨qᵢ : i ∈ 𝓘⟩.

The file also defines the three spans used in those statements: rowSpan for rows of an observable precision-difference matrix, hSpan for selected rows of the mixing pseudoinverse H, and qSpan for selected rows of a partial-order RQ factor Q.

Linear causal disentanglement: solution orbits under order-preserving permutations

This file proves the solution-orbit direction of the linear-disentanglement identifiability result. The definition Solution.permute constructs the relabelled model: it sends H to Pσ H, conjugates B₀ and every Bₖ by the permutation matrix, and sends each intervention target iₖ to σ(iₖ). The order-preservation hypothesis σ ∈ S(𝒢) is exactly what keeps the transformed observational matrix triangular in the ambient node order.

The theorem sigma_solutions then proves that this transformed solution has the same observable precision matrices Θ₀ and Θₖ. Together with disentanglement_identifiability, it gives the orbit characterization of all solutions.

Linear causal disentanglement: uniqueness (⊆ direction of Theorem 2)

This is the hard half of the flagship: any two parameter tuples producing the same family of precision matrices {Θ_k} differ by a single order-preserving relabeling σ ∈ S(𝒢). The proof follows the constructive argument of the paper:

1. recover the orthogonal factor Q of a partial order RQ decomposition of H, up to S(𝒢) and signs, from the spans rowspan(Θₖ − Θ₀) (rowspan_inclusion); 2. orthogonalize: (Q⁺)ᵀ Θₖ Q⁺ is the Cholesky factor of the latent precision, which recovers R and hence H = R Q up to S(𝒢); 3. read off {Bₖ} from H and {Θₖ} via Cholesky factorization.

The main public declarations expose these stages. exists_change_of_basis recovers the invertible matrix M with H' = M H; gram_identity and gram_diff_transport move the precision equalities down to latent d × d Gram identities; central_rank2_eq rewrites those identities in rank-two outer-product form; exists_orderPerm performs the orthogonal-correctness collapse and reads off the target relabeling; and disentanglement_uniqueness packages the final signed-monomial conclusion.

The order-preservation pinning runs the same triangular-support logic as Causalean.Mathlib.LinearAlgebra.perm_uniqueness: positive diagonals, triangularity, and nonzero support entries force the recovered relabeling to lie in S(𝒢).