Many measured systems contain two problems at once. Hidden variables influence one another causally, and the sensors that record them bend the signal: they saturate, compress, or respond nonlinearly, each channel in its own way. Current methods that recover causal structure from purely observational data, meaning data with no experiments, labels, or time ordering, need at least one of these to be simple. Either the sensors must be linear, or each observed channel must be a causal variable itself. We propose to drop both requirements when the random "shocks" driving the system are intermittent: in each sample, most variables receive no new input and simply follow their causes. The observation is short. In a linear causal system $z = Bz + e$, the matrix $I - B$ turns the hidden state into its shocks. If the shocks are sparse, every sample sits on a low-dimensional subspace, and which subspace it sits on changes from sample to sample. That is the cosparse analysis model from compressed sensing, a signal model defined by which linear measurements of the signal are exactly zero rather than by which building blocks it is assembled from. The operator doing the measuring is the causal graph itself.
The idea in two sentences is this. Sparse shocks place the undistorted signals on a union of many flat subspaces, and a per-channel sensor nonlinearity can only preserve that flatness if it is affine, so the distortion can be undone without assuming the sources are independent and without extra sensors. Once the distortion is undone, the learned analysis operator is the causal graph up to row scaling, and acyclicity fixes the ordering.
Core Claim
The generative model is
$$z = Bz + e, \qquad x = f(Az),$$
where $z \in \mathbb{R}^n$ are hidden causal variables and $B$ is strictly lower-triangular under an unknown ordering, so the graph is acyclic. The shock vector $e$ has at most $k < n$ nonzero entries in each sample. $A \in \mathbb{R}^{m \times n}$ is an unknown mixing matrix with $m \ge n$, and $f$ is an unknown invertible nonlinearity applied separately to each channel. Write $g = f^{-1}$ for the inverse of the distortion. Then
$$\Omega\, g(x) = e \quad \text{is } k\text{-sparse for every sample, with } \Omega = (I-B)A^{+},$$
where $A^{+}$ is the pseudo-inverse. In the language of analysis sparsity, $g(x)$ is cosparse under $\Omega$. Its co-support, the set of rows where $\Omega g(x)$ vanishes, is the set of variables that received no shock in that sample.
We aim to prove the following identifiability result. Suppose the supports of the shocks are rich enough, in the sense that every single-shock and every two-shock support occurs with continuously distributed amplitudes, and $A$ is generic. Then any per-channel map $\hat g$ and operator $\hat\Omega$ satisfying $\|\hat\Omega \hat g(x)\|_0 \le k$ on the data must have $\hat g$ equal to $g$ up to a per-channel scale and offset, and $\hat\Omega$ equal to $P D \Omega$ for a permutation $P$ and a diagonal scaling $D$. Requiring $\hat\Omega$ to be triangularizable, which is what acyclicity means here, removes $P$ and recovers $B$.
The argument follows the proof strategy of Provable Subspace Identification Under Post-Nonlinear Mixtures, applied once for each subspace. Samples with a single shock lie on lines through the origin. A per-channel map that keeps one line straight can still bend points along it through a shared reparameterization. Several lines that pass through the same channel with different slopes remove that freedom, which forces each per-channel map to be affine. Two-shock planes then remove any remaining ambiguity. Identifying $\Omega$ from the recovered linear signals is a sparse, acyclic linear problem, so no independence test is involved anywhere. That is the substantive departure from how post-nonlinear causal discovery is usually done.
Relation to Prior Work
Three papers motivate the gap. Provable Subspace Identification Under Post-Nonlinear Mixtures undoes per-channel distortions by requiring the inverted data to lie in a single subspace. This needs more sensors than sources ($m > n$), and it recovers only the subspace, not the sources inside it or any causal structure. Our criterion reduces to theirs when the co-support is the same in every sample. We generalize it to a co-support that varies by sample, which is exactly what allows square systems. Identifiability Guarantees for Causal Disentanglement from Purely Observational Data recovers latent causal layers from observational data, but only under linear mixing and Gaussian noise; its authors call nonlinear mixing a major open challenge. We handle a structured form of nonlinear mixing, per-channel distortion, and in exchange assume sparse rather than Gaussian shocks. Discovering Latent Causal Variables via Mechanism Sparsity and Generalizing Nonlinear ICA Beyond Structural Sparsity obtain identifiability from sparsity of graph edges or of the mixing Jacobian. They need temporal or auxiliary variables for dependent sources, and they leave causal discovery among the recovered sources explicitly open. Our sparsity lives in the analysis domain, on the shocks $\Omega z$, and is available from static i.i.d. data.
The causal-model literature constrains the design. On the Identifiability of the Post-Nonlinear Causal Model proves that post-nonlinear models of directly observed variables are generically identifiable. When $A$ is the identity our model is a special case of theirs, with linear inner mechanisms, so novelty lies only in the latent-mixing case and in the estimator. Rank-Based Causal Discovery for Post-Nonlinear Models documents that flexible estimators "cheat" residual-independence criteria and overfit. It avoids this through rank invariance, but only for observed nodes, because mixing before distortion destroys rank order. A sparsity criterion cannot be satisfied by making residuals look independent, which is our proposed answer to the overfitting problem. A Linear Non-Gaussian Acyclic Model for Causal Discovery shows that non-Gaussian independent noise identifies linear DAGs. Sparse shocks are non-Gaussian, so LiNGAM applies once $g$ is known; we reuse its ordering logic.
The cosparse literature supplies the method. Performance Guarantees of the Thresholding Algorithm for the Cosparse Analysis Model and Greedy-like algorithms for the cosparse analysis model provide co-support estimators and show that linearly dependent rows help rather than hurt. We use this when the system has extra conservation laws, which add rows to $\Omega$ beyond $n$. Projection onto the cosparse set is NP-hard rules out exact projection, so we use convex and thresholding relaxations. Supervised Learning of Analysis-Sparsity Priors With Automatic Differentiation learns $\Omega$ from clean and noisy pairs. We learn $\Omega$ without supervision, jointly with $g$.
Research Program
The theoretical work has three parts. First, prove the identifiability statement above, and state the minimal support-richness condition precisely: which families of co-supports suffice, and whether single-shock samples are needed or two-shock planes alone are enough. Second, characterize failure modes. We expect identifiability to break when $A$ has zero patterns that isolate channels, and when shocks are dense ($k$ close to $n$), where the union of subspaces fills the space. Third, derive how many samples per support pattern are needed. We expect the per-channel affinity error to scale as $O(1/\sqrt{N_\Lambda})$ in the number $N_\Lambda$ of samples per pattern, because each subspace constraint is a least-squares fit.
The estimator learns monotone per-channel networks $\hat g_i$ and an operator $\hat\Omega$. It minimizes a Minimax Concave Penalty on $\hat\Omega \hat g(x)$, a relaxation of $\ell_0$ that is less biased than $\ell_1$. To prevent collapse to trivial solutions, it adds an invertibility reconstruction term in the style of Lyu and Fu, fixes the variance of each channel of $\hat g(x)$, and constrains rows of $\hat\Omega$ to unit norm. A smooth acyclicity penalty on $\hat\Omega$ pushes it toward triangular form. After training, co-supports are read out by analysis thresholding, and $B$ is taken from the triangularized $\hat\Omega$.
Baselines
The naive reference is DirectLiNGAM from A direct method for estimating a causal ordering in a linear non-Gaussian acyclic model applied to raw $x$ after linear unmixing. It shows what ignoring the distortion costs.
The strongest competitor in the tall regime is the null-space estimator of Provable Subspace Identification Under Post-Nonlinear Mixtures, followed by LiNGAM on its linearized output. It is provably correct when $m > n$ and uses no independence assumption, so it is the method we must match there. The strongest competitor in the square regime is post-nonlinear ICA by total-correlation minimization from Deep Deterministic Nonlinear ICA via Total Correlation Minimization with Matrix-Based Entropy Functional, followed by LiNGAM ordering. Because $x = f(A(I-B)^{-1}e)$ is a post-nonlinear mixture of the shocks, this pipeline is valid whenever the shocks are independent. For the observed-node case ($A = I$) we add RankG and RankS from Rank-Based Causal Discovery for Post-Nonlinear Models, together with the independence-based post-nonlinear estimator of On the Identifiability of the Post-Nonlinear Causal Model. We also run the score-based peeling method of Identifiability Guarantees for Causal Disentanglement from Purely Observational Data on raw $x$ to measure how badly its linear-mixing assumption fails.
Two ablations isolate what matters. The first replaces the varying co-support with a fixed global one, which is exactly Lyu and Fu's criterion inside our code. The second replaces analysis sparsity on $\Omega g(x)$ with synthesis sparsity on an encoded latent.
All methods use the same monotone per-channel network architecture where applicable, the same data, and the same hyperparameter search of 50 trials selected on held-out reconstruction rather than on ground truth. The only reported number on Lacuna for this family is on the 130-channel Human Face EEG dataset: classification error of approximately 0.39 for the null-space method, against about 0.43 for PCA and about 0.46 for raw data (Provable Subspace Identification Under Post-Nonlinear Mixtures). For every synthetic suite, no reported result was found on Lacuna, so we rerun all baselines ourselves. Beating a baseline means lower structural Hamming distance, the count of wrong, missing, or reversed edges, with non-overlapping 95% intervals over 20 random graphs.
Why not just…?
Why not just run post-nonlinear ICA and then LiNGAM? When shocks are independent this pipeline is identifiable and is a real threat. We expect at most a sample-efficiency advantage there, from exact zeros rather than density estimation, and we will report it honestly if there is none. The case for our method rests on dependent shocks, such as events that co-occur or supports drawn from a correlated pattern. Independence fails there, while the co-support geometry is unchanged. The decisive experiment below sweeps shock dependence.
Why not just use Lyu and Fu's null-space method with more sensors? It requires $m > n$ and returns only a subspace (Provable Subspace Identification Under Post-Nonlinear Mixtures). Many instruments cannot be overbuilt, and in the square case the method has no constraint to work with. In the tall regime we run it head to head. If it matches us there, our contribution narrows to the square and dependent-shock regimes, and we will say so.
Why not just apply rank-based or independence-based post-nonlinear causal discovery to the channels? Both treat each channel as a causal variable. Once $A$ mixes the latents before distortion, rank order no longer tracks any single variable (Rank-Based Causal Discovery for Post-Nonlinear Models). The $A = I$ versus dense-$A$ comparison measures this directly.
Proposed Experiments
The synthetic suites extend those in the file. The first is the Erdős–Rényi DAG protocol of the rank-based paper, with 4 and 7 nodes, varying sample size and signal-to-noise ratio. We replace its noise with spike-and-slab shocks at $k/n \in \{0.15, 0.3, 0.5\}$ and run it with $A = I$, with dense square $A$, and with tall $A$. The second is the 4-node line and Y-structure graphs of Welch et al., with sigmoid, cubic-root, and saturating per-channel distortions added. The third reuses Lyu and Fu's 3-source, 5-sensor suite to check that we recover their tall case. Metrics are structural Hamming distance, the mean correlation coefficient between recovered and true shocks, and the $R^2$ of an affine fit of $\hat g \circ f$ in each channel, which directly measures whether the distortion was undone.
The decisive check is a sweep of shock dependence at fixed support richness, with $m = n$. Our theory predicts flat structural Hamming distance as dependence grows. Post-nonlinear ICA plus LiNGAM should degrade. If both degrade together, the claim that geometry replaces independence is false. The second decisive check sweeps $k/n$ toward 1. Identification should fail at a threshold predicted by the support-richness condition, and failure at a much lower threshold would falsify the theory. The fixed-co-support ablation should fail in every square setting.
On the Human Face EEG data, where there is no ground-truth graph, we treat the learned $\hat g(x)$ as features. The target is to match or improve on the 0.39 classification error reported for the null-space method. We will also report how stable the recovered graph is across bootstrap resamples. This is a sanity check that sparse neural events carry the structure, not proof of causal correctness.
References
- Provable Subspace Identification Under Post-Nonlinear Mixtures
- Identifiability Guarantees for Causal Disentanglement from Purely Observational Data
- Discovering Latent Causal Variables via Mechanism Sparsity: A New Principle for Nonlinear ICA
- Generalizing Nonlinear ICA Beyond Structural Sparsity
- On the Identifiability of the Post-Nonlinear Causal Model
- Rank-Based Causal Discovery for Post-Nonlinear Models
- A Linear Non-Gaussian Acyclic Model for Causal Discovery
- Performance Guarantees of the Thresholding Algorithm for the Cosparse Analysis Model
- Greedy-like algorithms for the cosparse analysis model
- Projection onto the cosparse set is NP-hard
- Supervised learning of analysis-sparsity priors with automatic differentiation
- A direct method for estimating a causal ordering in a linear non-Gaussian acyclic model
- Deep Deterministic Nonlinear ICA via Total Correlation Minimization with Matrix-Based Entropy Functional