On the Identifiability of Sparse ICA without Assuming Non-Gaussianity
Authors: Ignavier Ng
Yujia Zheng
Xinshuai Dong
Kun Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: independent component analysis
second-order statistics
sparsity
TL;DR: We develop an identifiability theory that relies on second-order statistics without imposing further preconditions on the distribution of sources, by introducing novel assumptions on the connective structure from sources to observed variables.

Abstract: Independent component analysis (ICA) is a fundamental statistical tool used to reveal hidden generative processes from observed data. However, traditional ICA approaches struggle with the rotational invariance inherent in Gaussian distributions, often necessitating the assumption of non-Gaussianity in the underlying sources. This may limit their applicability in broader contexts. To accommodate Gaussian sources, we develop an identifiability theory that relies on second-order statistics without imposing further preconditions on the distribution of sources, by introducing novel assumptions on the connective structure from sources to observed variables. Different from recent work that focuses on potentially restrictive connective structures, our proposed assumption of structural variability is both considerably less restrictive and provably necessary. Furthermore, we propose two estimation methods based on second-order statistics and sparsity constraint. Experimental results are provided to validate our identifiability theory and estimation methods.

On the Identifiability of Sparse ICA without Assuming Non-Gaussianity
Ignavier Ng"), Yujia Zheng"', Xinshuai Dong', Kun Zhang 1.2 1 Carnegie Mellon University
Mohamed bin Zayed University of Artificial Intelligence
fignavierng, yujiazh, dongxinshuai, kunz (cmzi) edu
Abstract
Independent component analysis (ICA) is a fundamental statistical tool used to re- veal hidden generative processes from observed data. However, traditional ICA ap- proaches struggle with the rotational invariance inherent in Gaussian distributions, often necessitating the assumption of non-Gaussianity in the underlying sources. This may limit their applicability in broader contexts. To accommodate Gaussian sources, we develop an identifiability theory that relies on recond-order statistics without imposing further preconditions on the distribution of sources, by introduc- ing novel assumptions on the connective structure from sources observed vari- ables. Different from recent work that focuses on potentially restrictive connective structures, our proposed assumption of structural variability is both considerably less restrictive and provably necessary. Furthermore, we propose two estimation methods based on second-order statistics and sparsity constraint. Experimental results are provided to validate our identifiability theory and estimation methods.
Introduction
Independent component analysis (ICA) [12] has emerged as an essential statistical tool in the scientific community, with application in various disciplines including neuroscience [27], biology [41, 9], and Earth science [32]. It aims to uncover the hidden generative processes that govern the observed data and separate mixed signals into independent sources. However, is known that the traditional ap- proaches of ICA struggle with Gaussian sources, which may limit their applicability in wide variety of contexts. For instance, several biological traits and measurements such as height, blood pressure, and measurement errors in genetics, as well as the thermal noises in electronic circuits, may often be normally distributed [29, 34]. Classical identifiability results in ICA rely on higher-order statistics (c.g.. Kurtois) [24], and cannot provide desired theoretical guarantees when there is more than one Gaussian source. Identifiability based on second-order statistic is thus essential in these scenarios.
The primary hurdle in applying ICA to Gaussian sources lies in the rotational invariance of Gaussian distribution [25]. To address this issue, earlier studies [30, 5, 35] incorporated additional information by assuming that the sources are nonstationary. However, this extra information may not always be readily available, limiting the generalizability these approaches. Thus, recent research [49, 1] has started to delve into the connective structure between the sources and the observed variables, as opposed to solely focusing on distributional assumptions (e.g., -anusasiiantty and nonstationarity). This shift of focus motivated by key observation: despite the rotational invariance in the distribu- tion Gaussian sources, the sparsity of mixing matrix undergoes noticeable changes, i.c., it may be denser after rotation [49]. Building this insight, Zheng et al. [49] introduced two assumptions the support of the mixing matrix to achieve identifiability of Gaussian sources, leading to a novel perspec- tive for tackling this long- standing challenge in the field of ICA. On the other hand, Abrahamsen and Rigollet [1] assumed that the mixing matrix is generated from sparse Bernolli-Gaussian ensemble.
"Equal contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Although the rotational invariance of Gaussian distribution can be resolved by the structural assump- tions on the mixing matrix proposed by Zheng al. [49]. they may be deemed overly restrictive. For instance, both of their structural assumptions cannot deal with the case where the set of observed variables influenced by one source is subset of those affected by another source, which may not be uncommon in practice. This may limit the applicability of ICA in complex real-world scenarios, thus underscoring the need for a weaker and more flexible structural assumption that is capable of addressing the rotational invariance in a more universally applicable manner.
To enhance the applicability with Gaussian sources, we develop an identifiability theory of ICA from second-ord order statistics under more flexible structural constraints. We introduce a novel assumption, namely structural variability, that is considerably weaker than existing ones. Notably, this assumption is proved to be among the necessary conditions for identifying Gaussian sources by focusing on the connective structure (i.e., the support of the mixing matrix). Moreover, we propose two estimation methods grounded in sparsity regularization and continuous constrained optimization. The efficacy of our proposed methods has been validated through experiments, which also reaffimm the validity of our theoretical result. Lastly, as matter of independent interest, we establish the connection between our identifiability result of ICA with causal discovery from second-order statistics; our finding further bridges the gap between these two fields and provides insights into the interpretation of our result.
2 Problem Setting
We consider the ICA setup given by Äs, where x E IK denotes the observed random vector, s E Iº is the latent random vector representing the independent components, also called sources, and A |aا] ... ān] E _= denotes the unknown mixing matrix. We assume here that A has full rank and all sources are standardized. For the estimated mixing matrix A and the ground-truth one A, we write A- A if they differ only in column permutations and sign changes of columns, and À 7 À vice versa. The goal is then to estimate À such that Å ~ A; in this case, one could identify a one-on-one mapping between the ground truth sources and the estimated ones, i.c., the unknown mixing process has been demixed during estimation. Since the support of mixing matrix A essentially represents the connective structure between sources and observed variables, we have the following definition for the ease of reference.
Definition 1 (Connective Structure). Given mixing matrix A. we define its connective structure as a directed bipartite graph GA = (VA. AA) from sources s to observed variables x, where the nodes and edges are defined as VA= = {s; 1n U (x,)²=1 and E = x;) azj # 0}, respectively.
Notations. We use bold capital letters (e.g., A), bold lowercase letters (e.g.. a), and italic letters (e.g., a) to denote matrices, vectors, and scalar quantities, respectively. For any matrix A, we denote its j-th column by a,, i-th row by ai.:, and (t, -it entry by az.-- We also denote by Ag the submatrix of A by obtaining the columns indexed by set J. For any vector a, we denote its i-th entry by a We define the support set of matrix A as supp (A) = {(..j) as., # 0}. and its support matrix as SA which is of the same size as A, where (Ex): i.j = X if as,j * and (E Ji.j = 0 otherewise. The notations of support set and support matrix
similarly defined for vector a. We denote by ||Allo the number of nonzero entries in A, and we have || llo = supp( A) = | llo- Furthermore, we denote the x n identity matrix and m zero matrix by I, and 0 m x respectively; to lighten the notation, we drop their subscripts when the context is clear. We also use [n]] to denote {1, 21, n...
3 Identifiability Result without Assuming Non-Gaussianity
By exploiting the Gaussiantyy of the sources, such as fourth-order cumulant, existing approaches are able estimate the true mixing matrix À up to signed column permutation when there is at most one Gaussian source [23, 2]. However, these approaches typically fail in the presence of more than one Gaussian source, because higher-order statisties cannot be utilized for full identifiability. The primary challenge of achieving identifiability for Gaussian sources lies in the rotational invariance of the Gaussian distribution. More specifically, the second-order statistics (or, more specifically, population-leve covariance matrix) Σ = ÄÄT remains unchanged if one replaces with ÁU for any orthogonal matrix U. Therefore, considering only second-order statistics, the true mixing matrix A is, generally speaking, only identifiable up to right orthogonal transformation without

---

further assumptions. In this section, we adopt a different perspective that departs from traditional distributional assumptions (i.e., non-Gaussianity and fourth-order cumulant), and instead introduces novel and precise assumptions on the connective structure, specifically the support of the mixing matrix. These assumptions enable identification of the true mixing matrix A up to signed column permutation using second-order statistics and sparsity constraint. Roughly speaking, with the population-level covariance matrix Σ, we consider the following formulation:
min AER
| subject to AAT ===
Σ =A=
AÄ"
Note that we start with the assumption of AAT Σ in the formulation above and identifiability result (c.g.. in Theorem 1); such an assumption can be obtained, e.g., from the equality of Gaussian selllhood-basee
likelihoods in the large sample limit. This also inspires estimation method that will be described in Section 4.2, which is more inline with, e.g., model selection approaches based
sparsity-regularized
maarity-regularizer likelihood [36, 18].
we first examine various types of constraints arising from second-order statistics. We then present the main identifiability result in Section 3.2. We show that our assumptions are strictly weaker than existing sparsity assumptions in Section 3.3, and establish the connection between our identifiability theory with causal discovery in Section 3.4. All proofs are given in Appendices C and D.
In Section 3.1,
3.1 Semialgebraic Constraints Arising from Second-Order Statistics
We first discuss various notions related to constraints arising from covariance matrices of observed variables x, which serve as a fundamental basis for introducing our assumptions and identifiability result of ICA in Section 3.2. These notions have been studied in the field of algebraic statistics [16], factor analysis [15], graphical models [19, 40], and causality [14, 20].
We begin with the following definition on the set of covariance matrices entailed by & for different values of the free parameters E. Definition 2 (Covariance Set).
The covariance set of support matrix & is defined as Σ(E) == {AA A E RR*x suup(() A) S supp(E), A non-singular).
The support & of mixing matrix A imposes certain constraints on the entries of the covariance matrix Σ = AAT, which, by Tarski-SSideenbrrg theorem (see [6]), correspond to semialgebraic constraints, i.e., equality and inequality constraints. The covariance set Σ is then said to a semialgebraic set, i.e., set that can be described with a finite number of polynomial equations and incqualities [6]. Clearly, if a covariance matrix Σ belongs to the covariance set (E)) then Σ satisfies the semialgebraic constraints imposed by
For an equality constraint, the set of values satisfying the constraint has zero Lebesgue measure over the parameter space involved. Given a support matrix &. we denote by H{)) the set of equality constraints it imposes on the corresponding covariance matrices. On the other hand, the set of values satisfying an inequality constraint has nonzero Lebesgue measure. To illustrate these constraints, we provide a three-variable example below. Note that the example only serves as illustrations of the constraints; our estimation methods (in Section 4) do not require deriving them in practice.
Example 1 (Semialgebraic Constraints). Consider support matrices
X
0
x
and The equality constraints imposed by E, include
1
x
E2
X
0
X
x
Σ1, 22.3 Σ1, =0,
while the inequality constraints imposed by &, include
Ee, - -
E2 E2,), -E, 2 0.
The detailed derivation can be found in Appendix D.I and provides insights into how such constraints arise from the corresponding support matrices. In the example above, the covariance matrix Σ generated by any mixing matrix A with support & must satisfy the corresponding equality constraint; similarly, the covariance matrix Σ generated by any mixing matrix A with support E, must satisfy the above inequality constraint. These constraints serve as footprints of the mixing matrix on the covariance matrix, and can be exploited for its identifiability, which we explain in the next section.
3

---

3.2 Identifiability Result from Second-Order Statistics
In this section, we present our identifiability result of ICA from second-order statisties. The core idea is to introduce precise and mild assumptions on the connective structure from sources to observed variables. These assumptions facilitate the identification of the mixing matrix through the application of a sparsity constraint, formulated in Problem (1). To begin, we describe our primary assumption concerning the connective structure as follows.
Assumption (Structural Variability). Every pair of the columns in the support matrix of A differ in more than one entry. That is, for every i,j E [m] and + j. we have supp(aa) U supp(a,)] - supp(a.) n supp(ay)) > 1.
The assumption above implies that every pair of sources should influence more than one different ob- served variable. Notably, in the field of nonlinear ICA with auxiliary variable. Hyvärinen and Morioka [22]. Hyvärinen et [26] have adopted the assumption of sufficient variability which requires that the auxiliary variable has a sufficiently diverse effect on the distributions of sources; specifically, the conditional distributions of the sources given the auxiliary variable must vary sufficiently. In contrast, our assumption of structural variability requires that every pair of sources influence sufficiently diverse sets of observed variables, facilitating the disentanglement of each source.
We provide several examples in Appendix E.1 to illustrate the broad applicability of the assumption above. Furthermore, the following proposition justifies such an assumption because it is necessary condition for identifiability via second-orde statistics and sparsity. The intuition is that if Assumption 1 is violated, there exists a rotation that maps matrix Á to another matrix Á which has equal or smaller number of nonzero entries and is not column permutation of A.
Proposition 1. If the true mixing matrix À does not satisfy Assumption I, then there exists a solution Á to Problem (1) such that A of A. Remark (Necessary Condition). Assumption is a necessary condition for identifiability of ICA via second-order statistics and under sparsity constraint.
We also adopt the following assumption on the mixing matrix for the identifiability of ICA. Assumption (Permutations to Lower Triangular Matrix). The matrix A can be permuted by independent row and column permutations to be lower triangular. That is, there exist permutation matrices P1 and P2 such that P.T.A. AP, lower triangular.
As we show in the proof of identifiability result in Theorem 1, Assumption 2, loosely speaking. ensures that the resulting covariance matrix does not contain "nontrivial" inequality constraints. In Example 1, support matrix & satisfies Assumption and leads to an equality constraint, while matrix &2 fails to meet this assumption, resulting in an inequality constraint. The Lebesgue measure of the parameters leading to such inequality constraint not zero, thus requiring additional assumptions to handle such cases. Therefore, we adopt Assumption 2 in this work and focus on equality constraints.
key ingredient of our identifiability result based on sparsity is the dimension of the covariance set E()). It may be natural to expect that the dimension of Σ{E). denoted as dim (()() equals the number of parameters used to specify the mixing matrices, i.e., ||Ello- This is not the case for general mixing matrices, but we show that such property holds under Assumption 2.
Proposition 2 (Dimension of Covariance Set). Let & be a support matrix that satisfies Assump- tion2 2. Then, its covariance set has a dimension of [|E||o. i.e., dim(E(E)) = -EEllo-
Note that Assumption 2 allows independent row and column permutations, which thus may be rather mild especially for sparse mixing matrix. Below provide example of the connective structure that satisfies this assumption. We also introduce an efficient approach to verify whether a mixing matrix satisfies Assumption 2 in Appendix E.2.
Example 2. If the connective structure 9Λ of mixing matrix A is a polytree, then matrix A satisfies Assumption 2.
Finally, the following assumption is needed to ensure that the equality constraints arising from the covariance matrix are entailed by the true mixing matrix, rather than accidental parameter cancellations. This establishes a correspondence between equality constraints in the covariance matrix and those imposed by the support of the mixing matrix. Similar assumption has been employed in various tasks such as causal discovery [39, 20], as discussed in Section 3.4.

---

Assumption (Faithfulness). For a mixing matrix A and the resulting covariance matrix Σ, E satisfies an equality constraint only if E (EA))
The following proposition justifies Assumption 3 and demonstrates that it is a generic property in the sense that it holds almost everywhere in the space of possible mixing matrices. other words, is only violated for set of mixing matrices with zero Lebesgue measure.
Proposition 3 (Generic Property). Suppose that the nonzero coefficients of matrix A randomly drawn from a distribution that is absolutely continuous with respect to Lebesgue measure. Then, matrix A satisfies Assumption 3 with probability one.
With the affrrementioned assumptions in place, we are ready to present our main identifiability result of ICA: by making use of second-order statisties and sparsity constraint, we show that the true mixing matrix can be identified up to signed column permutation. The key intuition is as follows: although in general there is rotational invariance matrix, under our assumptions above, is guaranteed to be denser than the true mixing matrix after any rotation (except permutation). Note that the proof leverages the technical tools developed by Ghassami et al. [20] which involve different types of rotations.
second-order statistics, the sparsity of the estimated mixing
Theorem (Identifiability with Sparsity). Suppose that the true mixing matrix À satisfies Assump- tions 1, 2, and 3. Let A be a solution of the following problem:
min AER
|Allo
subject
AAT
=AA and A satisfies Assumption 2.
Then, we have A A.
3.3 Related Sparsity Assumptions
As briefly discussed in Section 1, Zheng et al. [49] have also provided identifiability result of ICA without assuming non-Gausii. Their approach, similar to ours, relies assumptions related to the support of the mixing matrix, which are provided below.
Assumption 4 (Zheng et al. [49]). For every set I S [n] where [ and all i E I, we have |supp(a.)]-
U supp(ay) rank((verlap(Az))
jET
Assumption (Zheng et al. [49]). For every i E [n], there exists set I C [n]] such that supp(a,.) = {i}.
JEZ
While Assumptions and shed light on resolving the long- -tandingn challenge of the rotational indeterminacy of Gaussian sources, their general applicability remains unclear. One notable restriction that they require each column of the support matrix to not be a subset the other, formalized below, This may be overly restrictive in practical scenarios and is not the case for our Assumption 1. Assumption (Column Subset). Each column in the support of A is not subset of the other.
Since the true generating process of real-world data is inaccessible, evaluate the applicability of these sparsity assumptions. In light of this challenge, we demonstrate the significance and advantage of our Assumption 1 by proving that is strictly weaker than Assump- tions 4 and 5. This also strengthens the validity of our result (i.e., Proposition 1) that Assumption is a necessary condition for achieving identifiability with second-order statistics and sparsity constraint.
challenging to quantitatively
Theorem 2. For mixing matrix A, we have the following chain of chain of implications:
Assumption 4 - Assumption 6 = Assumption 1.
Furthermore, there exists a matrix satisfying Assumption that does not satisfy Assumption Theorem 3. For mixing matrix A, we have the following chain of chain of implications:
Assumption 5 = Assumption 6 = Assumption 1.
Furthermore, there exists matrix A satisfying Assumption that does not satisfy Assumption 5. Remark Assumption not only stricily weaker than both Assumption 4 and 5, but also ac- commodates cases where one column of mixing matrix A is a subset of of another (provided that their supports differ more than one entry). On the other hand, the latter two assumptions cannot accommodate such cases, further demonstrating the flexibility and broader scope of Assumption 1.
5

---

3.4 Connection with Causal Discovery
ICA has emerged as a useful tool for causal discovery over the past two decades [38]. particular, Shimizu et al. [38] demonstrated that the identifiability of ICA based on Gou-saassiy can be leveraged discover the complete structure of a linear non-Gaussian structural equation model (SEM). In this section, we establish the connection and provide an analogy between ICA and causal discovery from second-order statistics. This connection further bridges the gap between these two fields, and provides insights into the interpretation of our identifiability result.
Let x be the set of matrices whose diagonal entries are zero, and diag(E5))) be the set of positive diagonal matrices. Consider the linear SEM x B x + e, where x denotes the random vector, E oof denotes the weighted adjacency matrix representing a directed graph without self-loop, and e is the independent noise vector with covariance matrix 52 E cliag( " The graph often assumed be directed acyclic graph (DAG); in this case, two DAGs are said be Markov equivalent if they share the same skeleton and v-structures [43], resulting in the same set of conditional We
independencies. Also, the inverse covariance matrix of x is given by θ = (I B refer readers to Spirtes al. [39], Glymour et al. [21] for more details and a review of causal discovery.
Score-based method is a major class of causal discovery methods that optimizes a goodness ff--itt measure under sparsity constraint [21], e.g., BIC [36]. In essence, score- based causal discovery from second-order statistics can often be formulated in the large sample limit as the following optimization problem (the commonly used acyclicity constraint is omitted here and will be clarified subsequently):
BBl| subject to (I B) 1-- (1- B) = - (I- (4)
min BER (REding(RS...
By substituting A = (I- B) 1 into the above formulation, we obtain the ICA formulation with second- order statisties and sparsity constraint introduced Problem (I). To establish a precise connection between formulations (4) and (1), we present the following theorem which indicates that these formulations can be translated into each other.
Theorem (Equivalent Formulations). Suppose À = (I B 1. Then, we have:
(a) Let (B, $2) be a solution to Problem (4), Then, A = (I B) à is a solution to Problem (1).
(b) Let A be solution to Problem (1), Then, there exist matrices B E " and S diag(Rgo))
such that À
(I-B)s 2, and (B, εt) is a solution to Problem (4).
Thus, the formulations of causal discovery and ICA via second-order statistics and sparsity constraint share inherent similarities. The key difference lies in their respective goals-the former aims to estimate the support of B up Markov equivalence class [39], while the latter aims to estimate À up signed column permutation. The other difference is that (I B) (I B) represents the inverse covari- ance matrix θ of x in causal discovery, while ÄÄ represents the covariance matrix Σ of in ICA.
In addition to establishing the connection between formulations (4) and (I), we show that the assumptions employ for identifiability of ICA, namely Assumptions 1, 2, and 3, are inherently related to causal discovery. Notably, Assumption 3 has been used in causal discovery [39, 20] to ensure that the conditional independencies in the distribution entailed by the true directed graph. We now present a result that establishes the connection of Assumptions and with causal discovery.
Theorem 5. Suppose A ~ (I- (--) for matrices E Rax", B E u and Q E ddigg (B)) Then, A satisfies Assumptions and if and only if B represents a DAG whose Markov equivalence class is a singleton.
In causal discovery, it is rather common to assume that the true directed graph is acyclic and accordingly incorporate an acyclicity constraint to formulation (4). As indicated in Theorem 5 (and Proposition 10 in Appendix D.8), this acyclicity assumption corresponds to Assumption 2 in the context of ICA. Therefore, Theorem 4 can be straightforwardly extended to show the equivalence between formulations (2) and (4) with an additional acyclicity constraint on matrix B. Furthermore, worth noting that the mapping from mixing matrix A satisfying Assumption unique, which is straightforwardly implied by Shimizu et al. [38, Appendix A].
DAG

---

Proposition 4 (Shimizu et al. [38]). Suppose matrix A is non-singular and satisfies Assumption 2. Then, there exist unique matrices B E oft and 5 diag((R")) such that A (I -B Furthermore, matrix B represents a DAG.
Moreover, as indicated in Theorem (and Proposition 11 in Appendix D.8), Assumption 1 implies that the Markov equivalence class of B is singleton; in this case, the true DAG can be completely identified. In particular, the Markov equivalence class of DAG is singleton when all edges are either part of v-structure or required to be oriented avoid forming new v-structures or cycles [31, 4].
4 Estimation Methods with Second-Order Statistics
Building upon the identifiability result provided Section 3, we propose two estimation methods that leverage second-order statistics and sparsity. These methods involve solving a continuous constrained optimization problem, which we diseuss in detail in this section. First, in Section 4.1, we introduce a novel approach formulate the search space in Problem (2) that enables the application of continuous optimization techniques. We then describe the proposed estimation methods Section 4.2. All proofs are provided in Appendix D.
4.1 Characterization of Search Space
The key achieving the identifiability result presented in Theorem (1) lies in the optimization
problem (2), where the search space involves the matrices A that satisfy Assumption 2. Consequently, erucial question arises: is there efficient approach for exploring the space of matrices A that satisfy Assumption 2? Inspired by Zheng et al. [48], Wei et al. [45], Zhang et al. [47], we introduce the following function characterize the search space:
(A) = tr Σ (A) @ off( where (off(A))., S0,
if
otherwise.
Here, symbol @ denotes the Hadamard product. We then provide the following lemma that establishes the relationship between function (AA) and a specific type of permutation, namely simultaneous equal row and column permutation.
Lemma 1. For any matrix A. g(A) Of and only if it can be permuted via simultaneous equal row and column permutations to be lower triangular.
Intuitively speaking. if we interpret matrix A as a weighted adjacency matrix of a directed graph, say G, then tr (r((of((A) @ off A))*) counts the number of length-k weighted closed walks in G excluding the self-loops. Therefore, g( (AA) counts the total number of weighted closed walks in G without including self-loops. 9 (A) 0 then implies that & does not contain any cycle longer than may contain self-loops). It is known that a directed graph is acyclic if and only its weighted adjacency matrix can be permuted via simultaneous equal and column permutations to be strictly lower triangular. our case, 9 may contain self-loops, and thus can be permuted to a lower triangular form. This distinction elucidates the difference between characterization and that introduced by Zheng et al. [48], Zhang et al. [47], i.e., their characterization focuses on matrices that are strictly lower triangular, while ours focuses lower triangular matrices.
(i.e.,
The following proposition sheds light on the connection between (AA) and Assumption
Proposition The matrix A satisfies Assumption 2 if and only if there a matrix A such that a column permutation of and that g (A) =
The above proposition indicates that the search for matrices A satisfying Assumption 2 can be effectively conducted by considering the constraint 9(A) 0. Accordingly, we establish an alternative formulation of the identifiability result presented in Section 3.2. In the following section, we will introduce efficient approaches for solving Problem (5).
Theorem 6 (Alternative Formulation of Identifiability). Suppose that the true mixing matrix Å satisfies Assumptions 1, 2, and 3. Let À be solution of the following problem:
min A
A llo subject to AAT ÄÄT and g(A) 0.
(5)
Then, we have À Å.

---

Algorithm Decomposition-Basce Method
Require: initial penalty coefficient Ci > 0; multiplicative factor 3 > 1; maximum number of
iterations kmax 0; tolerance EL, 62 0; initial solution Ao; empirical covariance matrix Σ
1: for k = 2...... kmax do
2: Solve A& arg miiAAR" ((A) + + IAAA Σ1 + gA)) initialized Ag-1
3: if | - E el and g(A)) 62 then break
4: Update penalty coefficient Cp+1 = Beg
5: Output solution A
Algorithm 2 Likelihood- -assed Method
Require: initial penalty coefficient e > 0; multiplicative factor 3 > 1; maximum number of
iterations xmax 0; tolerance > 0; initial solution Ao; empirical covariance matrix Σ
1: for = 1, 2, Aimx do
2: Solve A& == arg min RR""" L(A; p(A) + (A)) initialized at Ag-1
3: g(A+) < then break
4: Update penalty coefficient Ck+1 Bck
5: Output solution A₃
4.2
Estimation Methods
Based on the identifiabiltiy results Theorems and 6, we propose two estimation methods, called SparselCA, perform ICA from second-order statisties that leverage sparsity regularization and continuous constrained optimization. To proceed, we define Σ as the empirical covariance matrix of observed variables and T as the sample size.
Decomposition- method. constrained optimization problem
Given the formulation in Eq. (5), we consider the following
min AER
p(A)
subject to AAT - E 0 and g(A) = 0,
(6)
where p(A) is a suitable sparsity regularizer, often expressible as p(A) Eis p(a,z). Formula- tion (5) indicates that one should apply the to regularizer p(A) )) A Alternatively, other possible choices include the &, regularizer pl A) || that supports continuous optimization. Further details regarding our specific choice of sparsity regularizer will be elaborated later in this section. On the other hand, we simply use the empirical covariance matrix Σ as an estimate the true covariance matrix Σ, which is found work well across different sample sizes in our experiments. One may also adopt regularized estimator of the form E + 1/ with proper choice of 7), which may have notable advantage in certain cases [13, 28, 37].
Likelihood-baze method. In addition to the decomposition based method above, we introduce a likelihood- baased estimation method formulated by the following constrained optimization problem:
min L(A; Σ) + p(A) subject to g(A) = O, A
T where L(A:E) (r((AAA)) + Tlog det A|
is the negative Gaussian log-likelihood function and p(A) is sparsity regularizer. The following result establishes the theoretical guarantee of this likelihood saaihood-basedd method.
Theorem Likelihood-Basee Method). Suppose that the true mixing matrix Á satisfies Assump- tions I, 2, and 3. Let Å be solution of Problem (7) with sparsity regularizer p (A) = 0.5| A llo log T. Then, we have Å A in the large sample limit.
Implementation. Based on Theorems 6 and 7, ideally one should adopt the &u regularizer p(A) A|| l/o and develop an exact discrete search procedure over the support space of matrix A. However, such approach may pose computational challenges in practice. Since the functions L(A; Σ) and g( A) are differentiable, in this work we develop an estimation procedure that leverages efficient continuous optimization techniques. Therefore, some possible choices for p(A) are é1, smoothly

---

clipped absolute deviation (SCAD) [17], and minimax concave penalty (MCP) [46] regularizers.
The E, regularizer has been shown to exhibit bias during estimation [17, 10], especially for large coefficients. Here, we adopt the MCP regularizer that is less susceptible to such issue, given by
a.. 2a
Maasyl
if | S al, otherwise,
p(as.) =
ax²
where À and a are hyperparameters.
To solve Eqs. (6) and (7), standard constrained optimization methods can be used, such as quadratic penalty method, augmented Lagrangian method, and barrier method [7, 8, 33]. In this work, we adopt the quadratic penalty method that converts each constrained problem into sequence of unconstrained optimization problems where the constraint violations are increasingly penalized. We describe the full procedure of the decomposition- based and likelihood-bol based methods based on quadratic penalty method in Algorithms and 2, respectively. The unconstrained problem in each iteration can be solved using different continuous optimization solvers, including first-order methods such as gradient descent and steepest descent, as well as second-order methods such as quasi-Newton methods. In our experiments presented in the subsequent section, we employ L-BFGS [11], a quasi-Newter method, to solve the unconstrained optimization problem.
is worth noting that the formulations in Eqs. (6) and (7) involve solving nonconvex optimization problems; in practice, the optimization procedure may return stationary points that correspond to suboptimal local solutions. Therefore, we run the method for a number of times and choose the final mixing matrix via model selection. Further details regarding the optimization procedure and implementation are provided Appendix
Experiments
To empirically validate our proposed identifiability results, we carry out experiments under various settings. We also conduct ablation studies to verify the necessity of the proposed assumptions and include FastCA [23] as representative baseline. Specifically, we consider the following methods:
SCa Decomposition-basee (Eq. (6) or likelihood-based (Eq. (7)) method on data where both Assumptions and 2 hold;
Vanilla: Decomposition-based (Eq. (6)) or likelihood-based (Eq. (7)) method without the constraint ({A) 0, data where neither Assumption 1 nor Assumption holds;
FastICA-D: FastICA on data where both Assumptions and 2 hold;
FastICA: FastICA on data where neither Assumption nor Assumption 2 holds.
For all experiments, we simulate 10 sources, and generate the supports of the true mixing matrices Á according to the assumptions required by each method above. The nonzero entries Å are sampled uniformly at random from [-0.8, -0.2] U [0.2, 0.8]. We use mean correlation coefficient (MCC) and Amari distance [3] as evaluation metrics, where all results are reported for 10 random trials.
Different sample sizes. We first consider entirely Gaussian sources and different sample sizes. The empirical results of MCC are shown in Figure 1, while those of Amari distance are given in Figure 4 in Appendix G. By comparing Sparse/CA with Vanilla and Fast/CA, it is evident that the identification performance much better across different sample sizes when the required assumptions on the connective structure are satisfied, as validated by Wilcoxon signed-rank test at 5% significance level. Furthermore, the unsatisfactory results FastICA-D indicate that our estimation methods also essential for ensuring the quality of the identification, which further validates the proposed identifiability theory. Since FastICA-D performs similarly to FastCCA, it suggests that the data- generating process, while meeting our assumption, may not be inherently simpler to recover without considering specific procedure to handle Gaussian sources. addition, as expected, the performance of SparseICA improves in terms of both MCC and Amari distance as the sample size increases.
Different ratios of Gaussian sources. We now conduct empirical study to investigate the perfor- mance in the presence of Gaussian and non- Con-Gaussian sources. Here, the non-Gaussian sources follow exponential distributions. We consider different ratios of Gaussian sources, which are specifically 0, 0.2, 0.4, 0.6, 0.8, and 1. For instance, ratio of 0.6 indicates that there are 6 Gaussian sources

---

SparseICA
Vanilla
FastCCA-D
FastCCA
0.80
0.8
0.75
MCC
0.70
0.6
0.5
0.60
0.55
0.4
30
100
300
1000
3000
10000
30
100
300
1000
3000
10000
Sample Size
Sample Size
(a) Likelihood-based method.
(b) Decomposition-basce method.
Figure 1: Empirical results of MCC across different sample sizes. Error bars indicate the standard errors calculated based 10 random trials.
SparseICAA
Vanilla
FastICA-D
FastICA
1.0
1.0
0.9
0.8
0.8
MCC
0.6
0.4
0.0
0.4
0.6
0.8
1.0
0.2
0.4
1.0
Ratio of Gaussian Sources
Ratio of Gaussian Sources
(a)
Likelihood-based method.
(b) Decomposition- bassd method.
Figure 2: Empirical results MCC across different ratios of Gaussian sources. Error bars indicate the standard errors calculated based on 10 random trials.
and 4 non- non-Gaussian sources. The empirical results of MCC based on 1000 samples depicted in Figure while those of Amari distance are provided in Figure 4 in Appendix G. One observes that the identification performance Sparse/CA is rather stable across different ratios of Gaussian sources, which may not be surprising as leverages only second-order statistics. On the other hand, the performance of FastICA-D and FastICA deteriorates the ratio of Gaussian sources increases, because it relies on non Non-Gaussiantty Gaussian sources, Fast/CA-D and Fast/CA may perform well, provided that the ratio (or number) of Gaussian sources is not large. This suggests a potential future direction to integrate our method based on second-order statistics with existing methods that rely non-Gaussianity, which may better handle both Gaussian and non non-Gaussian sources.
the sources. It is also observed that, the presence of
6 Conclusion
We develop an identifiability theory of ICA from second-order statistics without relying on non- Gaussianity, Specifically, introduce novel and precise assumptions on the connective structure from sources and observed variables, and show that our proposed assumption of structural variability strictly weaker than the previous ones. Importantly, we prove that this assumption is one of the necessary conditions for achieving identifiability in the investigated setting. We further propose two estimation methods based on second-order statistics that leverage sparsity regularization. Moreover, we establish precise connection between our identifiability result of ICA and causal discovery from second-order statistics, which may open up avenues for exploring the interplay between ICA and causal discovery with linear Gaussian SEM. Our theoretical claims have also been empirically validated across different settings. The limitations include the lack of finite sample analysis and broader application of our theory in more real-world tasks, which are worth exploring in future work.
10

---

Acknowledgments
The authors would like to thank the anonymous reviewers for helpful comments and suggestions. This project is partially supported by NSF Grant 2229881, the National Institutes of Health (NIH) under Contract R01HL159805, grant from Apple Inc., grant from KDDI Research Inc., and generous gifts from Salesforce Inc., Microsoft Research, and Amazon Research.
References
[1] N. Abrahamsen and P. Rigollet. Sparse gaussian ICA. arXiv preprint arXiv: 2018.
[2] L. Albera, A. Ferreol, P. Chevalier, and P. Comon. ICAR: tool for blind source separation using fourth-order statistics only. IEEE Transactions on Signal Processing, 53(10)33633-3644 2005.
[3] S.-i. Amari, Cichocki, and H. Yang. A new learning algorithm for blind signal separation. In Advances in Neural Information Processing Systems, 1995.
[4] S. A. Andersson, D. Madigan, and M. D. Perlman. A characterization of Markov equivalence classes for acyclic digraphs. The Annals of Statistics, 25(2):505-541, 1997.
[5] A. Belouchrani, K. Abed-Meraim, J.-F. Cardoso, and E. Moulines. A blind source separation technique using second-order statisties. IEEE Transactions on signal processing, 45(2):434-444 1997.
[6] R. Benedetti and J.-J. Risler. Real algebraic and semi-algebraic sets. Actualités mathématiques. Hermann, Paris, 1990.
[7] D. P. Bertsekas. Constrained Optimization and Lagrange Multiplier Methods, Academic Press, 1982.
[8] D. Bertsekas. Nonlinear Programming. Athena Scientific, 2nd edition, 1999.
[9] A. Biton, I. BBrnard-PPerrot, Y. Lou, C. Krucker, F. Chapeaublane, C. Rubio-Pééezz N. López- Bigas, A. Kamoun, Y. Neuzillet, P. Gestraud, L.. Grieco, S. Rebouissou, A. de Reyniès, S. Ben- hamou, T. Lebret, J. Southgate, E. Barillot, Y. Allory, A. Zinovyev, and Radvanyi. Independent component analysis uncovers the landscape of the bladder tumor transcriptome and reveals insights into luminal and basal subtypes. Cell Reports, 13). Nov 2014.
[10] P. Breheny and J. Huang. Coordinate descent algorithms for nonconvex penalized regression, with applications to biological feature selection. The Annals of Applied Statistics, 5(1):232-253, 2011.
[11] R. H. Byrd, P. Lu, J. Nocedal, and C. Zhu. A limited memory algorithm for bound constrained optimization. SIAM Journal on Scientific Computing, 16(5): 190-1108, 1995.
[12] P. Comon. Independent component analysis, new concept? Signal processing, 36(3):287-314, 1994.
[13] M. J. Daniels and R. E. Kass. Shrinkage estimators for covariance matrices. Biometrics, 57(4): 1173-1184, 2001.
[14] M. Drton. Algebraic problems in structural equation modeling. Advanced Studies in Pure Mathematics, 77, 2018.
[15] M. Drton, B. Sturmfels, and S. Sullivant. Algebraic factor analysis: Tetrads, pentads and beyond. Probability Theory and Related Fields, 138, 09 2005.
[16] M. Drton, B. Sturmfels, and S. Sullivant. Lectures on Algebraic Statistics, volume 39 of Oberwolfach Seminars. Springer, 2009.
[17] Fan and R. Li. Variable selection via nonconeave penalized likelihood and its oracle properties. Journal of the American statistical Association, 1345566))334-13366 2001.

---

[18] J. Friedman, T. Hastie, and R. Tibshirani. Sparse inverse covariance estimation with the graphical Lasso, Biostatisties, 9:432-41, 2008.
[19] D. Geiger, D. Heckerman, H. King, and C. Meek. Stratified exponential families: Graphical models and model selection. The Annals of Statistics, 29(2):005-529, 2001.
[20] A. Ghassami, Yang, N. Kiyavash, and K. Zhang. Characterizing distribution equivalence and structure learning for cyclic and acyclic directed graphs. In International Conference Machine Learning, 2020.
[21] C. Glymour, K. Zhang, and P. Spirtes. Review of causal discovery methods based on graphical models. Frontiers Genetics, 10, 2019.
[22] A. Hyvärinen and H. Morioka. Unsupervised feature extraction by time-contrastive learning and nonlinear ICA. Advances in Neural Information Processing Systems, 2016.
[23] A. Hyvärinen and E. Oja. A fast Exee-poiit algorithm for independent component analysis. Neural Computation, 148:-1483,,,,, 1997.
[24] A. Hyvärinen and E. Oja. Independent component analysis: algorithms and applications. Neural networks, 13(4-5)441--330 2000.
[25] A. Hyvärinen, J. Karhunen, and E. Oja. Independent Component Analysis. John Wiley & Sons, Inc, 2001.
[26] A. Hyvärinen, H. Sasaki, and R. Turner Nonlinear ICA using auxiliary variables and generalized contrastive learning. In International Conference Artificial Intelligence and Staristics, 2019.
[27] T.-P. Jung, Makeig, M. McKeown, Bell, T.-W. Lee, and T. Sejnowski. Imaging brain dynamics using independent component analysis. Proceedings of the IEEE, 89(7):1007-112) 2001.
[28] O. Ledoit and M. Wolf. A well-conditioned estimator for large-dimensional covariance matrices. Journal of Multivariate Analysis, 88(2):365-411, 2004.
[29] M. Lynch, B. Walsh, et al. Genetics and analysis of quantitative traits, volume Sinauer Sunderland, MA, 1998.
[30] K. Matsuoka, M. Ohoya, and M. Kawamoto. A neural net for blind separation of nonstationary signals. Neural Networks, 8:411 1995.
[31] C. Meck. Causal inference and causal explanation with background knowledge. In Conference on Uncertainty in Artificial Intelligence, 1995.
[32] N. Moulin, F. Gresselin, B. Dardaillon, and Z. Thomas. River temperature analysis with a new way of using independant component analysis. Frontiers Earth Science, 10, 12 2022.
[33] J. Nocedal and S. J. Wright. Numerical optimization. Springer series in operations research and financial engineering. Springer, 2nd edition, 2006.
[34] H. W. Ott. Noise Reduction Techniques in Electronic Systems. New York Wiley, 1988.
[35] D.-T. Pham and J.-F. Cardoso. Blind separation of instantaneous mixtures of nonstationary sources. IEEE Transactions signal processing, 49(9): 2001.
[36] G. Schwarz. Estimating the dimension of model. The Annals of Statistics, 6(2):461-466
1978.
[37] J. Schäfer and K. Strimmer. A shrinkage approach large-scale covariance matrix estimation and implications for functional genomics. Statistical applications in genetics and molecular biology, 4, 02 2005.
[38] Shimizu, P. O. Hoyer, A. Hyvärinen, and A. Kerminen. linear non- Gaussian acyclic model for causal discovery. Journal of Machine Learning Research, (003)))2003-20333 2006.
12

---

[39] P. Spirtes, C. Glymour, and R. Scheines. Causation, Prediction, and Search. MIT press, 2nd edition, 2001.
[40] Sullivant. Algebraic geometry of gaussian Bayesian networks. Advances in Applied Mathe- maticy, 40(4))482-513, 2008. ISSN 0196-8858.
[41] A. E. Teschendorff, M. Journee, P. A. Absil, R. Sepulchre, and C. Caldas. Elucidating the altered transcriptional programs in breast cancer using independent component analysis. PLoS Comput. Biol., 3(8):1539-1555 1554, 2007.
[42] L. N. Trefethen and D. Bau. Numerical linear algebra, volume 50, SIAM, 1997.
[43] Verma and Pearl. Equivalence and synthesis of causal models. Conference on Uncertainty in Artificial Intelligence, 1990.
[44] P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, Peterson, W. Weckesser, J. Bright, S. J. van der Walt, Brett, J. Wilson, K. Jarrod Millman, N. Mayorov, A. R. J. Nelson, E. Jones, R. Kern, E. Larson, C. Carey, I. Polat, Y. Feng, E. W. Moore, Vand erPlas, D. Laxalde, J. Perktold, R. Cimrman, Hemriksen,
A. Quintero, C. R. Harris, A. M. Archibald, A. H. Ribeiro, F. Pedregosa, P. van Mulbregt, and S... Contributors. SciPy 1.0: Fundamental algorithms for scientific computing in Python. Nature Methods, 17: 261-277 2020.
[45] D. Wei, T. Gao, and Y. Yu. DAGS with fears: A closer look continuous optimization for learning Bayesian networks. Advances in Neural Information Processing Systems, 2020.
[46] C.-H. Zhang. Nearly unbiased variable selection under minimax concave penalty. The Annals of Statisties, 38(2):894 -92, 2010.
[47] Z. Zhang, Ng. D. Gong. Y. Liu, E. M. Abbasnejad, M. Gong, K. Zhang, and J. Q. Shi. Truncated matrix power iteration for differentiable DAG learning. In Advances in Neural Information Processing Systems, 2022.
[48] X. Zheng, B. Aragam, P. Ravikumar, and E. P. Xing. DAGs with NO TEARS: Continuous optimization for structure learning. In Advances in Neural Information Processing Systems, 2018.
[49] Y. Zheng, I. Ng. and K. Zhang. On the identifiability of nonlinear ICA: Sparsity and beyond. In Advances Neural Information Processing Systems, 2022.
13

---

Appendices
Table of Contents
A Preliminaries Support Rotation
14
B Proofs of Useful Lemmas
15
B.1 Proof of Lemma 2
15
B.2 Proof of Lemma 3
15
B.3 Proof of Lemma
16
B.4 Proof of Lemma
................................
16
B.5 Proof of Lemma
16
Proof Theorem 1
17
C.I. Dimension of Covariance Set
17
C.2 Covariance Equivalence and Column Permutation of Support
suppot..........................
19
Equality Constraints and Covariance Equivalence
C.4 Identifiability of Parameters from Support
20
D Proofs Other Results
21
D.1 Proof of Example
21
D.2 Proof of Proposition
22
D.3 Proof of Example 2
22
D.4 Proof of Proposition 3
22
D.5 Proof of Theorem 2
23
D.6 Proof of Theorem 3
24
D.7 Proof of Theorem 4
24
D.8 Proof of Theorem 5
25
D.9 Proof of Lemma
28
D.10 Proof of Proposition 5
28
D.11 Proof Theorem
29
D.12 Proof of Theorem
29
Supplementary Discussion on Structural Assumptions
Examples Satisfying Structural Variability Assumption Assumption......................
"ssupptoo.......................
29
Efficient Approach Verifying Assumption 2
29
F Supplementary Estimation Details
G Supplementary Experimental Results
30
A Preliminaries on Support Rotation
Before presenting the proofs of the theoretical results, review the definition of support rotation and its potential effects on a support matrix, given by Ghassami et al. [20]. Note that the definition and remark below quoted from Ghassami et al. [20, Section 3.1], with only minor modifications.
Definition 3 (Support Rotation [20]). The support rotation, denoted R(i,j,) j,k), is a transforma- tion that modifies a support matrix & by applying a Givens rotation in the (j,k) plane, setting the element Ex,j to zero. The outcome of the support matrix of QG (j, k, tan (-qu.//9.a) k/.k))) where such that the support matrix of Q' E.
Q E arg maxq |supp (Q'G (j.k, Lan (-dis/
14

---

Note that G (j. tan (-4g//((xx)) is the Givens rotation in the (j.k) plane that makes the do.
entry zero.
Remark 3 (Ghassami et al. [20]). The effects of applying support rotation R(i.j, k) can be cate- gorized into the following four cases:
Reduction: EL - and Et. for all [p][ then only Euj becomes zero.
Reversible acute rotation: Er.j Ei x and there exists i' such that the j-th and k-th columns differ only in that row, then Ei.5 becomes zero and both Ev. and Ev.k become x.
Irreversible acute rotation: St, S., x and the j-th and k-th columns differ in at least two rows, then Exg becomes zero and all entries on the j-th and k-th columns become on the rows which they differed.
Column swap: Ef and Ei,k O, then columns j and k are swapped.
B Proofs of Useful Lemmas
We provide several lemmas that will be useful for subsequent proofs.
B.1 Proof of Lemma
Lemma (Nonzero Diagonal Entries). For any non-singular matrix A, there exists a permutation matrix P such that the diagonal entries of AP are nonzero.
Proof. We prove it by contradiction. Suppose that there always exists diagonal entry in every column permutation.
We first represent the determinant of the matrix A as its Leibniz formula:
det(A) Σ sgn(() II [s,o(s))
where S, is the set of n-permutations. Because for every permutation, there always exists a diagonal entry with value zero, we have
12 II (1,0(0 0, Vo Sn.
Thus, it follows that det(A) 0. This indicates that the matrix A is singular, which leads to contradiction.
B.2 Proof of Lemma 3
Lemma (Non-Singular Solution). Let À be a non-singular matrix. Suppose À is matrix such that ÁÄT T ÄÄT. Then, Å non-singular.
Proof. A matrix is non- nin-singular (or invertible) if and only if its determinant is nonzero. Therefore, we need to show that det( Å) + 0. From the given, we have ÁÄT = ÄÄT, Taking determinants on both sides, we get
det(AAT) = det (et(AA))
Since À and À are square matrices, we can simplify both sides:
det(A) AA de)(
Since Á is non-singular, we know that det(A) A) * O. Therefore, det(A)² * 0. This implies that det(A) * 0. Thus, A is nin-singular.
15

---

B.3 Proof of Lemma 5
Lemma 4. Let A be matrix with all diagonal entries being nonzero. Then, there exists matrix B E 1axn and E diag(R such that A () +D, where D is a diagonal matrix with diagonal entries being +1.
Proof. Since the diagonal entries of A are nonzero, can construct diagonal matrix D such that the diagonal entries AD are positive, by defining d = if as,; > and d, = - if aN < Let 5 be diagonal matrix of the same size as matrix A. where (S2).:
1/D Also, let
B = I ADD Since the diagonal entries of matrix ADΩ are ones, the diagonal entries of matrix B zeros. Therefore, have B p I E diag (Bog) and A -) D. where is a diagonal matrix with entries being =1.
Lemma 5, Let A be a non-singular matrix. Then, there exists matrix B E T and 52 E diag((RS))
such that A ~ (I-Be BB))-
Proof. Since matrix A is non-singular, by Lemma 2, there exists permutation matrix P such that the diagonal entries of AP are nonzero. By Lemma 4, there exists matrix B Ruff and S E diag(IR5o) such that AP (I [I-B) ?D, where D is a diagonal matrix with diagonal entries being +1. Clearly, we have A [I B)
B.4 Proof of Lemma
Lemma 6. Suppose A ~ (I - B)Q for matrices A E R2x" B E Rof and Q E diag (B5..). Then, we have | | + n.
Proof. First notice that the diagonal entries of B are zeros, which implies
B l0 = [|oo + B loo B + +..
Since - is diagonal matrix, right multiplication of Ω amounts rescaling the columns of I- B, and does not affect its support. Therefore, we have
( B) 1/o | Bla |B||
Since A (I B)Ω 1 matrices and (I B) differ only in signed column permutations. Therefore, their number of nonzero entries are the same, i.e.,
| l ||||| m.
B,5 Proof of Lemma
We first provide the following lemma that will be used prove Lemma 8.
Lemma 7. Lei P1 and P2 be two permutation matrices. Then, PTP., P, is lower triangular if and only if P P22
Proof. The "if part" clear because permutation matrices are orthogonal matrices, and thus P.P.P P1 I is lower triangular. It remains prove the "only if part". Since P P2 is also permutation matrix, this matrix being lower triangular implies that it is an identity matrix, because identity matrix is the only permutation matrix that is lower triangular. We then have P, P2 which implies
P = P =2
We now provide the proof of Lemma 8.
Lemma 8. Given matrix B E Rux" ifl B satisfies Assumption 2, then I B is non-singular.
Proof. Since I - B satisfies Assumption 2, there exist permutation matrices P and P2 such that
PT ( B)P2 P.P.2 P.BP2
is lower triangular. For all i,j E [n] such that (P] + 0. we have (P. BP222, 0, which implies that P. P2 must be lower triangular, because otherwise, P. P2 P BP2 cannot be lower
16

---

triangular. By Lemma 7, we then have P1 = P2. This indicates that I - P BP1 is lower triangular, with diagonal entries equal to one. Therefore, we have
det(I - BP1) =1
which implies
det([ B) det((P B)P = det BP
Since the determinant of I B is nonzero, is non-singular.
C Proof of Theorem
We first describe the notion of covariance equivalence that needed for the proof of Theorem 1. Specifically, if two support matrices & and &2 entail the same set of covariance matrices, i.c., E(E) 2L2)) they are said be covariance equivalent. This means that for any combination of parameter values in E1, there exists a corresponding set of parameter values in E2 that leads to the same covariance matrix, and vice versa. Furthermore, two support matrices are covariance equivalent if and only if they lead to the same set of semialgebraic constraints on the covariance matrices.
We now give the proof of Theorem 1. The proof makes use of Proposition 2, Proposition 6, Proposi- tion 7, and Corollary 1, which are provided in Appendices C.I, C.2, C.3, and C.4, respectively. Note that the proof is partly inspired by that of Ghassami et al. [20, Theorem 3].
Theorem (Identifiaiility with Sparsity). Suppose that the true mixing matrix À satisfies Assump- tions 1, 2, and 3. Let Å be a solution of the the following problem:
min AgRexa
|Allo
subject to AAT = =ÄÄ and A satisfies Assumption 2.
Then, we have A ~ Å.
Proof. Let À be solution of Problem (2). This implies ÅÄT = == ÄÄÄ and that Å satisfies
Assumption 2. Since À is non-singular, by Lemma 3, matrix Å is non-singular.
Since Å can entail the covariance matrix E, we have Σ E(EA) )) which indicates that Σ contains all semialgebraic constraints of A.A. Under Assumption we have
H(EA) S ((Ex).
(8)
The sparsity term in the objective function implics
| lo < |ol
(9)
because otherwise À will never be a solution of Problem (2).
We now show by contradiction that (( &f (EA)) Suppose H(E)) H(Ex), which indi-
cates dim(E(E,)) x) > dim (E( Since the support matrices & and & satisfy Assumption 2,
Proposition 2 implies lllllo Exllo, which is contradictory with Inequality (9). This implies
H(EA) & H(EA).
(10)
By Eqs. (8) and (10), we obtain H(SA) ( ). which, by Proposition 7, implies that the support matrices A and A are covariance equivalent, because they satisfy Assumption 2. By Proposition we conclude that the columns of & are permutation of those of E
Recall that matrices À and À are non-singular, and entail the same covariance matrix Σ. Since the columns of A a permutation of those of E by Corollary have À Á.
C.1 Dimension of Covariance Set
We first define the Jacobian matrix of Σ AAT w.r.t the free parameters of A as DA n² x ||Allo matrix, where the rows indexed by (i, [n] x [n]. and columns are indexed by
W
which is
17

---

(k, E supp(A), That is, for (é.j) E [m]] x [n]] and (k: 1) E supp(A) we have
1
if and k i, if = j and k # i, if * j and k = i,
+Σ
(11)
0A (..9).(.)))
dak
if o j and & = j. if and k {i.j}.
Given a matrix M, we denote by off and on(M) the off-diagonal and diagonal entries of M, respectively. With slight abuse of notation, we rewrite the above Jacobian matrix as the following form that consists four submatrices, by permuting the corresponding columns and rows:
offf (2)
of a A don A
ΦΣ
doff
(12)
8on
(Af
Each submatrix above represents the Jacobian matrix for different parts (i.e., off-diagonal and diagonal entries) of matrix taken w.r.t. different free parameters (i.e., off-diagonal and diagonal free parameters) in matrix A. Note that column and row permutations do not affect the rank of the matrix. Since we are primarily interested in the rank of the above Jacobian matrix and its submatrices, we use the same notation refer to different column and/or row permutations of the corresponding Jacobian matrix, depending on the context.
Lemma 9. Let A be a lower triangular matrix. Then, we have
σΣ
rank
A|
0A
A-I,
Proof. Let d be the number of diagonal free parameters in matrix A. This indicates that (A) and (n(A) contain |||lo and free parameters, respectively.
By specializing
= In and using Eq. (11), we have
off Σ
don(2) i (ff
8 on =0, and
Σ)
=0,
2I
(13)
i on A) A=1,
on A
A=1.
A=1.
where the last equality is obtained after row permutations of the corresponding matrix. Also, since matrix A is lower triangular, each nonzero entry of Jol[(A]
dof((E)
A-I, corresponds to either
σΣk1 =1 or Dag,
HEi for some k > L.
Oag.
(f A=I. contains precisely two nonzero entries, while each row either contains precisely one nonzero entry, or does not contain any nonzero entry. Therefore,
In this case, each column of doll 2
off A=1, can be rewritten after row permutations as
offf( E)
I | lo
off( 3 Aff
|| la do
A=I.
which yields
dof(
rank
||A d.
(14)
off
A-T.,
Substituting Eq. (13) into Eq. (12), we have
0
0off(A)
A=I.
0A
21
A=I
which, with Eq. (14), implies
iΣ
dfff(E) Σ)
rank
rank
+ rank
aA
doff A
A=I.
A=I.
||
|
18

---

Proposition 2 (Dimension of Covariance Set). Let & be a support matrix that satisfies Assump- tion 2. Then, its covariance set has a dimension of [|Ello. i.e. dim EEllo-
Proof. Since & satisfies Assumption 2, it can be permuted by column and permutations to be lower triangular; in this case, the resulting covariance matrix and the original covariance matrix differ in equal row and column permutations. Note that the dimension of the covariance set remains the same after simultancous equal row and column permutations of the covariance matrices. Therefore, it suffices to consider the case where lower triangular, and show that it has dimension of ||Ello.
As indicated by Geiger et al. [19. Theorem 10), the dimension of dim (EE) equals the maximum rank of the corresponding Jacobian matrix. In this case, it suffices to consider the columns of the Jacobian matrix that correspond to the nonzero entries of support matrix &. i.e. the free parameters of 0Σ has full
matrix A, which we denote by 0A column rank that is equal to ||Ello. Therefore, the dimension of the covariance set is |
02 By Lemma 9, when A L,, the Jacobian matrix 0A D
C.2 Covariance Equivalence and Column Permutation of Support
We now state a result that is adapted from Ghassami et al. [20, Proposition 5] to the context of ICA. In our proof of Theorem 1, only the "only if part" of the following result is used.
Proposition 6 (Ghassami al. [20, Proposition 5D. Consider two support matrices & and E If every pair of columns of & differ in more than one entry, then Ê and &2 are covariance equivalent if and only if the columns of E, are a permutation of columns of E
C.3 Equality Constraints and Covariance Equivalence
In this section, we show how Assumption 2 allows one to go from two support matrices & and & having the same equality constraints covariance equivalence.
Following Ghassami et al. [20], we first denote the covariance set of a directed graph G by
(G) -I- B) (I-B) BB Bax" Ω diagg(RS)) supp(B) C supp(Bg)),
where Bg the adjacency matrix G. With a slight abuse of notation, we denote by (9)) the set of the equality constraints imposed by on the resulting matrix 1-B) '(I -B)
Lemma 10. Let& & be non-singular support matrix that satisfies Assumption 2.2 Then, there exists DAG such that Σ(E) = O(g).
Proof. Since & is non-singular, by Lemma 2, it can be mapped via column permutations another support matrix é' with diagonal entries being nonzero. Since & satisfies Assumption 2, Proposition 10 implies that E' represents a DAG, say G. where the support of its adjacency matrix supp(Bg) supp(off(<") Since column permutations of support matrices do not affect the resulting covariance matrices, we have Σ(E) E(''). Therefore, suffices to prove Σ(E') = (g)).
Since g' is support matrix with diagonal entries being nonzero, we have supp(g') = (T) U supp(off((E))
(15)
We consider both parts of the statements.
Proof of (g) C Σ + (E'):
Suppose M (G)) By definition of (G)) there exist B E _ and Ω diag (R" such that
supp(B) S supp(olT(g')) and M = (I
(I-
(16)
Let A = (I- B)n 2 which, with Eq. (16), implies AA T = M. Recall that G is DAG, which indicates also represents a DAG, Therefore, I B, and thus A, are non-singular. Since right multiplication of - does not affect the support of B, by Eqs. (15) and (16), we have
supp(A) = supp(I B) = supp(I) Usupp(BB) S supp(I) U supp(off(g')) = supp(g').
Therefore, we have supp(A) A) C supp(g'), which, with the non-singularity of matrix A, implies M AAT E (E'))
We say that support matrix & is non-singular if there exists non non singulr matrix A such that supp(A) S supp(E).
19

---

Proof of E(5') S (g))
Suppose M )- By definition of E(")), there exists non-singular matrix A Roxn such that
supp(A) S supp(E') and M AA
(17)
Since matrix A is non-singular, all of its diagonal entries must be nonzero, because otherwise the corresponding determinant will be zero, which contradicts its non-singularity. By Lemma 4, there exists matrix B E = and $2 diag(R%)) such that A (I B) à D, where D a diagonal
matrix with diagonal entries being #1 By Eq. (17), we have (I B2 1-22-1(12 'II B) T M. Since right multiplication of 2 does not affect the support of I B, by Eqs. (15) and (17), we have (I) U Suupp(B) supp(I - B) supp(A) S supp(E) supp(I) U suppp(of((")).
Note that (I) and (B are disjoint. Furthermore, supp(I) and supp(off(E') are disjoint. Therefore, we have supp(B) S supp(off(E)) and thus M = - 'I- B) (g)) O
Proposition 7. Let &1 and E₂ be non-singular support matrices that satisfy Assumption 2. If they have the same set of equality constraints, i.e., H{{2) = H(2)), then they are covariance equivalent.
Proof. Since matrices &1 and & are non-singular and satisfy Assumption 2, by Lemma 10, there exist DAGs 91 and G2 such that
E(E) (G)) and E(E2) = @(2)).
(18)
which imply
H(S)) = (9)) and H(E2) = H(2)).
(19)
We now provide a proof by contrapositive. Suppose that E, and E, are not covariance equivalent, i.e., E(E,) * E(E2). By Eq. (18), we have (G1) # (G2)), i... DAGs 91 and G2 not covariance equivalent. By Ghassami et al. [20, Proposition 1]. DAGs 91 and G2 are not Markov equivalent, which indicates that they do not have the same skeleton and v-structures [43]. This implies that they lead to different sets of conditional independence constraints, which in this case correspond to different sets of polynomial equality constraints [39], i.e., (91) o (G2).. By Eq. (19), we have H(E)) * (E2))
C.4 Identifiability of Parameters from Support
In the following, we provide a result that establish the identifiability of the parameters in mixing matrix from its support.
Proposition 8. Consider two non-singular matrices A1 and A₂ that satisfy Assumption 2 and that entail the same covariance matrix, i.e., Σ = AIAT A2A2. If matrices A₁ and A2 have the same support, then they differ only in sign changes of columns.
Proof. Since matrix A₁ satisfies Assumption there exist permutation matrices P1 and P2 such that PT P2 is lower triangular. Clearly, PT A,P2 2 is also lower triangular, because matrices A and Ag have the same support. Since matrices P.T. A,P: and P. AgP2 are non nonnsingular, all diagonal entries of these two matrices must be nonzero, because otherwise the corresponding determinant will be zero, which contradict their non-singularity. Let D₁ and D2 be diagonal matrices with diagonal entries being +1 such that the diagonal entries of P A D2 P2 and P, A2D2P2 are positive. (Thh procedure for constructing such diagonal matrices D and D2 is straightforward and omitted here.)
Furthermore, we have
(20) Since matrix A₁ is non-singular, matrices Σ, and thus P EP,, are symmetric positive definite. Here, Eq. (20) can be viewed the Cholesky decomposition of P, ΣP,, where P, A,D,P, and P. A₂D2P2 are the Cholesky factors. Recall that they are lower triangular matrices with all diagonal entries being positive; in this case, it is known that such Cholesky factor unique [42]. Therefore, we have
(P]A.D;P;) A₂D2P2) EP.
= PT
which implics
A A A,D,D,. Since D₂D, is diagonal matrix with diagonal entries being 11, we conclude that matrices A and Ag differ only in sign changes of columns.
D
20

---

Corollary (Identifiability of Parameters from Support), Consider two non-singular matrices A and A2 that satisfy Assumption 2 and that entail the same covariance matrix, i.e., = A
A2Ag. If the columns CA, are permutation of those of E.., then we have A A2- Proof. Suppose by contradiction that 1 of Ag. This implies that, for every permutation matrix P such that ÉA, = EA, matrices A₁ and ApP differ in more than sign changes columns. By Proposition 8, this cannot happen.
D Proofs of Other Results
D.1 Proof of Example 1
Example 1 (Semialgebraic Constraints). Consider support matrices
0
x
0
1
x
and
= E2-
x
x
Rox
x
x
The equality constraints imposed by E1 include
E,,1 - 11,2 = 0,
while the inequality constraints imposed by &2 include
(E1,1 E2, E2
- E
1 E - - 2 0.
Proof. We first consider matrix A with the support E,- That is, matrix A is of the form
[1,,
0
A1
02
02,2
0
43,1
0
03,33
The entries of the resulting covariance matrix Σ
A are then given by
11 = di,1'
Σ = 02,142,1:
Σn, = a² + 22
E1 = 01,103,1,
Σg,3 03 03.3:
Σ23 02,103,1
which imply
E23
Σ E1, = O.
We now consider matrix A2 with the support &..
That is, matrix A2 is of the form
11,1
0
1,3
A2
22,1
02,2
03,2
03,3
The entries of the resulting covariance matrix Σ
A are then given by
Σ11 oi. ai.3:
Σ 01,1002,1,
Σg, 0 02
Σ 01,303,33
Σ3, 03.2 + 43.3
Σg = 02,203,2-
Suppose we fix the value of 03,2. This leads to
1
2²22 = E3,3
Σ1
05.2
which can be rewritten
(Σi,1 Σ Σ )a E1, ",, (2, 0.
Since the value of 03,2 is a real number, have
+ Σ1, E2g - E2 Eg, 4(E,, E2. 2
-
1 20 0.
21

---

D.2 Proof of Proposition 1
Proposition 1. If the true mixing matrix A does not satisfy Assumption 1, then there exists a solution À to Problem (1) such that A of A.
Proof. Since the true mixing matrix A does not satisfy Assumption there exist i,j E [m], i such that
()) U supp(ā,) (a)) supp(ā,) (upp((ā)) 1.
This leads to the following two cases:
Case 1: supp(ā,) U supp(ā,)) ssppp(ā:) supp(ā,)] In this case, since the mixing matrix of full column rank, there must exist a le E [n] such that (Ea)k. k.i = (EA) k. = x. Thus, we can always apply reversible acute rotation (see Remark 3) to the i-th and j-th columns of matrix A. This operation leads to another matrix with ||o = ||llo and AÁ = -ÄÄ In the reversible acute rotation, we can set either (EA).. k. or (Ex).. to 0. This implies ||ã < | and therefore Á of Å. Now, suppose that the true mixing matrix A is not solution to Problem (1). Clearly, there must exist a solution Å to Problem (1) such that | llu < ||A which indicates A o A. It remains to consider the case where matrix A is solution to Problem (I). In this case, since ||A || matrix Á is also solution to Problem (1), and we have shown that A 7 A.
Case 2: (u)pp(;:) U [u)p(ā;)] (upp((.) supp(ā,)) ) In this case, we can always apply reduction (see Remark to the i-th and j-th columns of matrix A. This operation leads to another matrix Á with || < |||loo and AÄ AÄ T. Therefore, there must exist solution to Problem (1) such that |A||o S ||o < ||A which indicates + A.
In either case, there exists solution to Problem (1) whose columns are not signed permutations of the columns of Å.
D.3 Proof of Example 2
Example 2. If the connective structure GA of mixing matrix A is a polytree, then matrix A satisfies Assumption 2.
Proof. Suppose that the matrix A does not satisfy Assumption 2. This means that there does not exist permutation matrices P1 and P2 such that P, AP₂ is lower triangular, which implies that, in the connective structure GA, there exists path that alternates between source and observed variable nodes, i.e., a sequence of nodes {si (fi Sig; "in 8ig Tja 86, } where each pair (si, zit) corresponds to nonzero entry ajc, in A, for t= I,... k. Thus, by replacing the directed edges on this path with undirected edges, we obtain cycle. Therefore, GA cannot be polytree.
D.4 Proof of Proposition 3
The proof of the following proposition is adapted from that of Ghassami et al. [20, Proposition 8). Proposition 3 (Generic Property). Suppose that the nonzero coefficients of matrix A randomly drawn from a distribution that is absolutely continuous with respect to Lebesgue measure. Then, matrix A satisfies Assumption 3 with probability one.
Proof. Let & be the set of possible equality constraints of any covariance matrix with the same size Σ, which is a finite set because the number of variables is finite. Consider a matrix Á with the same support as A (i.e..& A = &A) that violates Assumption 3, where the corresponding covariance matrix is Σ. To violate Assumption 3, E has to satisfy equality constraint o \ (({A). Thus, the set of possible matrices with the same support as A that violate Assumption 3 is a subset of
U
{ {A EA and Σ satisfies equality constraint x)
(EE)
By the definition of equality constraint, each set in the union above has zero Lebesgue measure, and thus the finite union above also has zero Lebesgue measure. This implies that the set of possible
22

---

matrices with the same support as A that violate Assumption 3 has zero Lebesgue measure. Therefore, Assumption is satisfied with probability one.
D.5 Proof of Theorem 2
We first prove the following proposition that will be used to prove both Theorems 2 and 3. Proposition 9. If mixing matrix A satisfies Assumption 6, then satisfies Assumption 1.
Proof. We provide proof by contrapositive. Suppose A does not satisfy Assumption 1. This means that there exist some i.j E [n] with * j such that
supp(a:) U supp(a,)] - supp(a.) (ssup((a)) -
The difference can be either 0 or 1.
supp(a;) U supp(a;)] -suppa) O supp(a,)) = 0. This implies supp(a;) supp(aj), i.e., the supports of a; and a, are identical. In this case, Assumption 6 is clearly violated, as supp(a:) is a subset supp(a,) and vice versa.
Case 1:
supp(a.) U supp(a,) }| supp(a,) n supp(a,) columns is proper subset of the other, meaning either supp(a,) C supp(a,) supp(a,) c supp(a;). Again, this violates Assumption 6.
Case 2:
= This implies that one of the
Hence, in either case, if A does not satisfy Assumption 1, then it does not satisfy Assumption 6. L
We now prove the following theorem.
Theorem 2. For mixing matrix A, we have the following chain chain of implications: Assumption 4
Assumption 6 = Assumption 1.
Furthermore, there exists a matrix satisfying Assumption that does not satisfy Assumption Proof. We first prove Assumption 4
Assumption 6.
In Assumption 4, Eq. (3) assumed to be satsified for all I S [n] where [ > 1. Thus, in order to prove that Assumption implics Assumption 6, it is sufficient to only consider the case where [ 2. That is, for every j E [n]] and + j. we have
supp(a;) U supp(a,)] > rank(overlap(A (Arapp(AAAa (k,))) + (supp(a;)]
where we set as the target index without loss of generality.
Because rank(overlap( A (i,))) )) 2 have
supp a.) U supp(a;)) > 1 + |supp(a.))
(21)
Suppose ssupp(a;) > supp(aa) )- Eq. (21) implies that supp(a,) is not subset of sapp(a.).
Similarly, (suppppa)) 2 ssupp(a)) (a,),, we could also show that supp(a,) (a.) is not subset of supp(a,) a,). Thus. Assumption 6 is satisfied.
According to Proposition of the first part, i.e., Assumption 4 = Assumption - Assumption 1.
have Assumption 6
Assumption which completes the proof
We now provide example of mixing matrix satisfying the Assumption 1 that does not satisfy Assumption 4. Suppose the mixing matrix Á has support as follows:
07
= x
x
x
Clearly, Assumption is satisfied since every pair of columns differ on more than one entry. However, for & = 1 and I = {1, 2}. we have
U kkez
supp(aw:)
rann((oerlap(Az))
U supp(aw)) = 3. KKEz
3, it is not possible Eq. (3) to hold for À when and I 21. Thus, Assumption is violated. The proof of part (b) is finished.
Since (supp(ax)) (supp(ai) )
D
23

---

D.6 Proof of Theorem 3
Theorem 3. For mixing matrix A, we have the following chain of chain of implications:
Assumption 5
Assumption 6 = Assumption 1.
Furthermore, there exists matrix satisfying Assumption that does not satisfy Assumption
Proof. We first prove the contrapositive of Assumption = Assumption 6 does not hold. This means that there exist distinct indices i, [ni], such that supp(a.) a subset of supp(ay).
Assumption Suppose that
Now, for any set of row indices I C [n], consider the intersection over the supports of all rows j E I, denoted by NJEZ supp(ay.)) Because mapp(a;) ) subset of supp(ay). it is clear that cannot be the only element this intersection. Therefore, is impossible to satisfy Njez supp(a,,) {i] for any choice of Z, which indicates that Assumption 5 violated.
According to Proposition 9, we have Assumption 6 - Assumption 1, which completes the proof of the first part, i.e., Assumption 5 = Assumption
Assumption 1.
We now provide am example of mixing matrix satisfying the Assumption that does not satisfy Assumption 5. Suppose the mixing matrix Å has a support as follows:
0
07
=
X
X
0
X
Clearly, Assumption 1 is satisfied since the supports of each pair of columns differ on more than one entry. However, Assumption 5 is violated since there does exist any set of rows such that the intersection of their nonzero indices or 3.
D.7 Proof of Theorem
Theorem (Equivalent Formulations). Suppose A B) à Then, have:
(a) Let (2) be solution Problem (4), Then, À (I B) is a solution Problem (1).
(b) Let Å be a solution to Problem (1), Then, there exist matrices E R and $2 E diag(125.)
such that À -I- B) $, and (B, 22) is solution Problem (4).
Proof. We consider both parts of the statements.
Part (a):
We provide a proof by contrapositive. For matrices B and S2, suppose À == (I-B) solution to Problem (1). That is, there exists matrix A such that
2 is not
| ||
(22)
and
ÄÄT ÅAT.
(23)
By Lemma 3, matrix À is non-singular, and thus, by Lemma 5, there exist matrices B maxx and
á E Aliag(RR, (n)) such that
À
Lemma 6 implies
BBlo and || | n,
which, with Inequality (22), indicate |B|| | Furthermore, using Eq. (23) and the assumption
À (I B) 2, we have
(I BI- B) = (I- (I-
Therefore, (B, . satisfies the constraint of Problem (4) and leads to a smaller zero norm for the objective function, and thus (B, 52) will never be solution of Problem (4).

---

Part (b):
Let Å be a solution to Problem (1). By Lemma 3, matrix A non-singular, and thus, by Lemma
there exist matrices E Rf and f E (R)) such that
À ~ -
It then remains to prove that (B, (2) is solution to Problem (4), which we do by contradiction.
Suppose that (B, S2) is not solution to Problem (4). That there exists solution (B, (2) such that
B D < [Bloo
(24)
and
(I 1I-
B (I- (I-B).
(25)
Define A = (I B) 3. Lemma 6 implies || = | lo + and || = | + n. which, Furthermore, using Eq. (25) and the assumption
with Inequality (24), indicates || ||A||oo
À = (I B)52 _ we have
ÄÄ A
Therefore, À satisfies the constraint of Problem (1) and leads to smaller zero norm for the objective function, and thus Á will never be solution of Problem (I), which is contradiction.
D.8 Proof of Theorem
In this section, we first provide the proofs of Propositions 10 and 11, which together straightforwardly imply Theorem 5. Before proving Proposition 10, we state the following lemma from Shimizu et al. [38] that is useful for the proof.
Lemma 11 (Shimizu et al. [38, Lemma ID.. Let A be a lower Iriangular matrix with all diagonal entries being nonzero. Let P1 and P2 be two permutation matrices. Then, a permutation of rows and columns of A, i.e., P. AP,, has only nonzero entries in the diagonal if and only if the row and column permutations are equal, i.e., P1 P2
We now provide the proof of Proposition 10.
Proposition 10. Suppose A (I - B) 1 for matrices A E Rux", B E R and Z E (Ra.) Then, A satisfies Assumption 2 and only if matrix B represents a DAG.
Proof. Without loss of generality, we consider the case which A and (I B) à differ only in column permutations, instead of signed column permutations. This is because, for the latter case, there exists a diagonal matrix D with diagonal entries being 11 such that AD and (I- B) differ only column permutations, and furthermore, AD satisfies Assumption 2 if and only if A satisfies Assumption? 2.
Therefore, suppose there exists a permutation matrix P1 such that
A = (I (I-B)
(26)
We now consider both parts of the statements.
If part:
Suppose that matrix B represents DAG. Then, there exists permutation matrix P2 such that P BP strictly lower triangular. Therefore, P__ (I B)P,2 I P BP2 is lower triangular. This implies that P. B PP is lower triangular because
is diagonal matrix and does not affect the support. By substituting Eq. (26), P.T AP, 'P2 lower triangular. Clearly, P P is also permutation matrix. Therefore, matrix A can be permuted by row and column permutations to be lower triangular, and thus satisfies Assumption
Only if part:
Suppose matrix A satisfies Assumption 2. Then, there exist permutation matrices Ps and P3 such that P.. AP3 is lower triangular. Substituting Eq. (26), P. (I B)Ω PP is lower triangular.
25

---

Since P,P3 is also permutation matrix, this indicates that (I - B)2 i, and thus I - B, satisfy
Assumption 2. By Lemma B is non-singular, which indicates that
det(I (IBB))F +
Note that
del( -)>00 and det(Pi)
With Eq. (26), we have
det(A) & 0,
and therefore
det(P, AP3) + O.
It is known that the determinant of a lower triangular matrix is the product of its diagonal entries.
Since P22 33 is lower triangular and det A 33) j O, diagonal entries of P AP3 must be nonzero. Now define
P1=PP P- and Ps P
(27)
both of which are permutation matrices. By some algebraic manipulations of Eq. (26) and further substituting the above definitions, we have
PP
B)-
where all diagonal entries are nonzeros. Applying Lemma w.r.. matrix P.J AP3, we have
P = Ps.
which, by plugging into Eq. (27), implies
P2 = P,P3.
Since we have shown that P (I B) $ P,Pa is lower triangular, further substitution of P2
P2P3 indicates that P (I B)Ω tP is lower triangular. Since right multiplication of S does
not affect the support of I B, we see that
P - = I- P. BP
also lower triangular. This indicates that PT BP2 is lower triangular, which, with the assumption that the diagonal entries of B are zeros, imply that P.J BP2 is strictly lower triangular. Therefore. matrix B represents DAG.
After proving Proposition 10, now consider Proposition 11. Before that, provide result by Ghassami et al. [20] that is useful for the proof. We first describe the notion of parent exchange by Ghassami et al. [20]. Let A be the symmetric difference operator that identifies the elements present in either of the sets but not in the intersection. For DAG & with weighted adjacency matrix B, its vertices 2; and 2, are said to be parent exchangeable (-)B:
supp B) supp B)²) = i.e., there exists & E [n] such that (I B):) A supp((I - B),) [k). In such case, support rotation can be performed on columns (EI-B)s and (EIB)); that sets nonzero entry on those columns, except (fI-B)i,i and (Si-n)is- to zero. In other words. the parent of x; and æj that corresponds the zeroed entry is removed. Furthermore, the entry (5-B))R, or (LI-B)ss B).. is set to x, which corresponds to adding the missing edge - I; or Iy T... Ghassami et al. [20] defined such an operation to a parent exchange. We then provide the following corollary that straightforwardly derived from Ghassami et al. [20, Corollary & Proposition 1].
Corollary (Ghassami et al. [20, Corollary 2l). DAGs G1 and G2 are Markov equivalent if and only if there exists sequence of parent exchanges that maps G1 to Gz. and one that maps G2 to G
We now provide the proof of Proposition 11.
Proposition 11. Let G be DAG with weighted adjacency matrix B. Then, matrix I B satisfies Assumption I if and only if the Markov equivalence class of G is singleton.
Proof. We consider both parts of the statements.
26

---

If part:
We provide proof by contrapositive. Suppose that matrix I B does satisfy Assumption 2. That is, there exist i, E [x] and * such that
Isup (I B).) supp -B))) <.
Clearly, we have supp (I B)) * supp((I B)j), because otherwise there will be cycle with length of two over variables 2; and z. which contradicts the assumption that G is acyelic. This
implies
(28) By definition, I; and z; are parent exchangeable, and therefore there exists a parent exchange that maps DAG G to another directed graph g" where G G. We now show by contradiction that G' is DAG. Suppose that G' is not DAG. By Eq. (28), there exists variable 24 such that
supp (ip B)
supp (I 4 supp((1 B),) {k).
Here, we must have = i k = j. because otherwise we have
(f1 (SI-B)ss (f1-B).s (51 Bi, = which leads to cycle over variables r; and zj. Without loss of generality, we consider the case of j. which implies
supp((I-
- {o}
(29)
and ($I-B)j. = O. This indicates that the entry (ÉI-B)5, is set to x (i.e., the edge zy + is added) after the parent exchange DAG g', which subsequently leads to a cycle in g" In this Iin Ij in DAG G, where
case, there must exist path 2; It, 7
2 and
4m [n] \ {i, j.. to which adding the edge Iÿ + 2; leads to cycle DAG g'. By Eq. (29), Ti,, is also a parent of ri, indicating that there exists cycle x; Zt,
+ 21 + z; in DAG G. which contradicts the assumption that G is acyclic. Therefore, g' must be a DAG.
Since there exists a parent exchange that maps DAG G to another DAG g', clearly there also exists (reversed) parent exchange that maps DAG G' back to DAG G. By Corollary 2, DAGs G and G' are Markov equivalent. Therefore, the Markov equivalence class of G contains at least two DAGs and is not a singleton.
Only if part:
Suppose that matrix I B satisfies Assumption 2. That is, for all i,j E [n]] and i + j.we have
|supp((1 B),) supp((1 BB,)) 1.
parent exchangeable, and thus parent exchange cannot be applied for any pair of vertices in DAG G. Therefore, for any DAG g' * G. there exists no sequence of parent exchanges that maps & to G', implying that they are not Markov equivalent. This indicates that all DAGs are not Markov equivalent to DAG G, except itself, and thus the Markov equivalence class of G is singleton.
In this case, every pair of vertices
With Propositions 10 and in place, we provide the proof of Theorem 5.
Theorem 5. Suppose ~ (I- B) for matrices E Raxn, B TR and Q E diag (R%)) Then, A satisfies Assumptions and if and only if B represents a DAG whose Markov equivalence class is singleton.
Proof. We consider both parts of the statements. If part:
Suppose matrix B represents a DAG whose Markov equivalence class is a singleton. By Propo- sition 10, matrix A satisfies Assumption 2. Furthermore, Proposition 11 implies that I - B, and thus (I B) ž, satisfy Assumption 1. Since A and (I B)Ω- differ only in signed column permutations, and Assumption involves only pairwise comparison of the support matrix, A must also satisfy Assumption
Only if part:
Suppose A satisfies Assumptions 1 and 2. By Proposition 10, matrix B represents a DAG. Since A and (I B) 1 differ only in signed column permutations, and Assumption 1 involves only pairwise comparison of the support matrix, B also satisfies Assumption 1. By Proposition 11, the Markov equivalence class of the DAG represented by B is a singleton.
O
27

---

D.9 Proof of Lemma
Before proving Lemma first provide another result that useful for the proof. To ease further reasoning, we define the function
f(A) = tr [(AOA))
and clearly we have
(30)
Zheng et al. [48], Zhang al. [47] have shown that, for any matrix A, f(A) = 0 if and only if A represents the weighted adjacency matrix of a DAG. Also, it is known that the weighted adjacency matrix of directed graph can be permuted via simultaneous equal row and column permutations be strictly lower triangular if and only if the graph is a DAG. Therefore, we provide the following corollary that is straightforwardyy implied by the results by Zheng al. [48], Wei al. [45].
Lemma 12 (Wei et al. [45, Theorem 1J). For any matrix A, f(A) 0 if and only if it can be permuted via simultaneous equal row and column permutations to be strictly lower triangular.
We now provide the proof for Lemma 1.
Lemma 1. For any matrix A. g(A) = if and only if can be permuted via simultaneous equal row and column permutations to be lower triangular.
Proof. We first define D diagonal matrix of the same size matrix A, where its diagonal entries are equal to those A and its non-diagonal entries are zero. Clearly, we have A = off(A) + DA- For any matrix P, This implies
APAP= P +
(31)
If part:
Suppose that there exists permutation matrix P such that AP is lower triangular. By Eq. (31), we have P ol[(A) = P AP DAP. Clearly, the diagonal entries of P AP are exactly DAP, which cancel out each other. Therefore, the diagonal entries of
the same as those P off (A)) are zeros, indicating that it is strictly lower triangular. By Lemma 12, this implies (off(AA) = O, and thus g(A) = 0 by Eq. (30).
Only if part:
Suppose ((A) ((ff((A)) 0. By Lemma 12, there exists permutation matrix P such that
P off (A) is strictly lower triangular. Clearly, P DAP is diagonal matrix. By Eq. (31), P AP lower triangular, i.c., A can be permuted via simultancous equal row and column permutations to be lower triangular.
D.10 Proof of Proposition 5
Proposition 5. The matrix A satisfies Assumption 2 if and only if there is matrix A such that it is column permulation of A and that y 9(A) 0.
Proof. We consider both parts of the statements. If part:
Suppose that there exists matrix Á such that it is a column permutation of A and that g(A) By definition, there exists permutation matrix P2 such that AP2. Also, by Lemma 1, there exists permutation matrix P, such that P.T ÁP, lower triangular, which implies that P AP,P, is lower triangular. Clearly, P,P; is also permutation matrix. Therefore, matrix A can be permuted by row and column permutations to lower triangular, indicating that it satisfies Assumption 2.
Only if part:
Suppose that matrix A satisfies Assumption 2, i.e., there exist permutation matrices P1 and Pa such that P. AP2 is lower triangular. Defining P3 = P which is also permutation matrix,
28

---

and substituting it into the previous statement, we see that Pj AP3P1 is lower triangular. Further substitution of A == AP3 implies that PIAP AP is lower triangular, which, by Lemma 1, indicates ((A) 0. Clearly, Å is column permutation of A.
D.11 Proof of Theorem 6
Theorem (Alternative Formulation of Identifiability). Suppose that the true mixing matrix A satisfies Assumptions 1, 2, and 3. Let A be a solution of the the following problem:
min A
|o subject to AA -ÄT and g(A) = 0.
(5)
Then, we have A A.
Proof. Let Å be solution to Problem (5). Suppose by contradiction that it is not solution to Problem (2). That is, there exists matrix A satisfying Assumption 2 such that
|| | and ÄÄ ÂÄT.
(32)
By Proposition 5, there exists permutation matrix P such that ((P) = O. Furthermore, by Eq. (32), we have
| < || and (AP) = AAT
Therefore, AP satisfies the constraint of Problem (5) and leads to a smaller zero norm for the objective function, and thus Á will never be a solution of Problem (5), which is a contradiction. Therefore, must be a solution to Problem (2). Since matrix Å also satisfies Assumptions 1, 2, and 3, applying Theorem completes the proof.
D.12 Proof of Theorem 7
Theorem (Likelihood- Method). Suppose that the true mixing matrix À satisfies Assump- tions 2, and 3. Let A be a solution of Problem (7) with sparsity regularizer pl )- = 0.5| A llo log T. Then, we have Å A in the large sample limit.
Proof. First, we have (AA 0 and, in the large sample limit, Σ = Σ. Similar to BIC [36], the likelihood term dominates in the large sample limit as the weight of the likelihood function increases much faster than that of the sparsity regularizer. Therefore, in the large sample limit, we have ÁÁ Σ = ÁÁ. Also, for any matrix A that satisfies AA ÁÁ and 9 0, the sparsity regularizer indicates ||A I ||||oo. because otherwise Å will never be solution of Problem (7). This implies that Á is also solution Problem (5). Since matrix Å also satisfies Assumptions and 3, applying Theorem completes the proof.
E
Supplementary Discussion on Structural Assumptions
E.1 Examples Satisfying Structural Variability Assumption
To illustrate the intuition of the proposed assumption of structural variability (i.c., Assumption 1), provide several examples the connective structure from sources observed variables (which corresponds to the support of mixing matrix) satisfying that assumption, as illustrated in Figure 3.
E.2 Efficient Approach for Verifying Assumption
Assumption 2 involves finding a certain combination of row and column permutations for mixing matrix A, which may first appear inefficient to verify. We provide a more efficient way to do so, by leveraging the interpretation of our assumptions in the context of causal discovery (see Section 3.4 for detailed discussion). Specifically, we provide the following corollary that is straightforward consequence of Lemma 2 and Proposition 10, whose proof is omitted.
Corollary (Verification of Assumption 2). Lel A be a non-singular matrix and P be a permuta- tion matrix such that the diagonal entries of AP are nonzero. Lei G = E) be directed graph where = {w), ... Un and È {v; - U; : (AP) # 0, + j}. Then, directed graph G is acyclic and only if matrix A satisfies Assumption 2.
29

---

81
T1
$1
21
81
21
22
22
82
82
83
J33
83
233
83
273
84
24
(c)
Figure 3: Graphical representations of examples that satisfy Assumption 1.
Specifically, Corollary 3 implies that suffices to find a column permutation such that the diagonal entries of the permuted matrix nonzero. Note that such column permutation is guaranteed to exist as indicated by Lemma 2. We then construct a directed graph G based on such permuted matrix and check if G contains cycle, e.g., via depth-first search. Instead of searching for certain combination of row and column permutations, this procedure may be more efficient because it involves only finding specific column permutations.
F
Supplementary Estimation Details
We provide the estimation details for the methods described in Section 4.2, In our experiments, we use the average log-likelihen likelihood ,, [A; Σ) as the objective (instead of L(A: Σ) Eq. (7)) for likelihood- based method. For the sparsity term p(A), we use MCP with hyperparameters À == 1, 40 and
0.1, a 10 for decomposition based and likelihood-basse methods, respectively.
Furthermore, for both methods, we use the L-BFGS algorithm [11] implemented in SciPy [44] to solve each unconstrained optimization problem of quadartic penalty method. Since the formulations involve solving nonconvex optimization problems, we run L-BFGS with 30 random initializations, where each entry of the initial solution Ao sampled uniformly at random from [-0.1, 0.1]. In this case, the final solution is chosen via model selection. For quadratic penalty method, we use C1 10 and cj 10 for decomposition- based and likelihood-baar methods, respectively, and use B = 1.5 for both methods.
Lastly, also run each of the experiments on 12 CPUs and GBs of memory.
threshold of 0.01 to remove small weights in the estimated mixing matrix. We
Computational complexity. To compute the constraint term g(A). straightforward approach is to compute each matrix power g(A) and then sum their traces up, which requires O matrix multiplications. In our implementation, we adopt more efficient approach with computational complexity (log n) matrix multiplications, inspired by Zhang et al. (2020). The rough idea is to perform exponentiation by squaring (i.c., procedure similar binary search) and recursively compute the term (A))
Furthermore, each L-BFGS run has computational complexity of Om22n² + m² + mn²t), where m < n² the memory size and the number of inner iterations of the L-BFGS run. Typically, we have | 250 for each L-BFGS run, and 125 iterations for the quadratic penalty method.
G Supplementary Experimental Results
In addition to the MCC reported Section 5, we report the Amari distance to evaluate the identifica- tion performance in Figures 4 and 5, respectively.
30

---

SparseICA
Vanilla
FastCCA-D
FastICA
2.0
2.0
Amari Distance
Amari Distance
1.5
1.5
1.0
1.0
0.5
30
100
300
1000
3000
10000
30
100
300
1000
3000
10000
Sample Size
Sample Size
(a)
Likelihood-baag based method.
(b) Decomposition based method.
Figure 4: Empirical results Amari distance across different sample sizes. Error bars indicate the
standard errors calculated based on 10 random trials.
SparseICAA
Vanilla
FastICA-D
FastICA
2.0
Amari Distance
1.5
Amari Distance
0.5
0.5
0.0
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Ratio of Gaussian Sources
Ratio of Gaussian Sources
(a) Likelihood-based method.
(b) Decomposition--uuse method.
Figure 5: Empirical results of Amari distance across different ratios Gaussian sources. Error bars indicate the standard errors calculated based on 10 random trials.
31


Reviews:
[{"review_id": "jGTORpGNaM", "reviewer": "Reviewer_zk7j", "summary": "In this paper, the authors develop new identifiability conditions for ICA, based on sparsity constraints. These assumptions, in particular, do not require the sources to be non-Gaussian, as is usually the case in ICA.\nMostly, the authors take inspiration in previous work by Zheng et al, and weaken their main condition. Some assumption are shown to be necessary.\nAs is usual with sparsity-based analyses, the resulting optimization problem is quite non-trivial, here the main difficulty is to explore the space of directed adjacency matrices whose corresponding graph is a DAG. The authors provide some discussion and implementation procedures about this.\nThe proposed method is evaluated against FastICA on synthetic data. A (quick) ablation study is realized to examine the effect of the assumptions not being satisfied.", "questions": "See \"weaknesses\" above\n\nMinor questions/typos:\n\n- l22 : \"Kurtois\"\n- l 95 : \"statitsic\"\n- Assumption 3 is a bit unclear at first read (it seems like a definition), only one sense of the \"if and only if\" is important, perhaps it is possible to reformulate\n- what is the exact sense of \"asymptotically\" in theorem 7 ? (see also question/comment about sample size, which is not discussed in the paper)", "limitations": "The authors have discussed some aspects extensively, eg Assumption 1 with respect to previous work, other are a bit scarce, eg Assumption 2. Also, the computational complexity is not discussed, and there is no experiments on real data.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- the contribution is interesting for the long-standing problem of non-Gaussian ICA. The authors make a commendable effort to discuss previous results, their main inspiration, and the strengthening of the results/weakening of assumptions\n\n- the paper is well-written and pedagogical, with examples and discussion scattered throughout about the assumptions and the results\n\n- some aspects of the paper are quite developed (relation with causal discovery, implementation, necessity of the assumptions...) without sacrificing the clarity of the writing despite the space constraints", "weaknesses": "- the only assumption that less discussed than the other ones, in relation with previous work or its \"realistic aspect\" with respect to real data, seems to also be the \"main\" one, Assumption 2. The focus on hard constraints is theoretically understandable, but how realistic is it ? Also, the triple-presentation of the optimization problem is a bit redundant, the end problem being \"just\" optimizing among the space of DAGs\n\n- the paper focuses on exact identifiability, when the true covariance matrix is \"available\". This can be confusing for people not expert on ICA, can the effect of sample size and covariance estimation be discussed ? Does the resulting noise has an effect on \"admissible\" sparsity level (empirically, let's say), and for now the sparsity level $\\| A\\|_0$ does not seem to be constrained in any way (beyond assumption 1 and 2)\n\n- there is no discussion on computational complexity, it seems that the constraint $h(A)=0$ is very costly as it involves computing the $n$th power of an $n \\times n$ matrix, at each iteration. Is there any simplification over brute force ?\n\n- no evaluation on real data. When the assumptions are only approximately satisfied, and there is strong noise on the covariance, it is not clear what is the performance of the proposed method", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the time devoted and the thoughtful comments. Please find the response to your comments and questions below.\n\n**Q1: Lack of discussion about Assumption 2 and how realistic it is.**\n\nA1: We sincerely appreciate this very helpful point. Since Assumption 2 allows independent column and row permutations, we believe that it is rather mild, especially for sparse mixing matrices. In other words, if the influences from sources to observed variables are sparse, then it is likely for Assumption 2 to hold. Such notion of sparse influences tend to apply when the observations are influenced by the sources in a \"simple\" manner, e.g., in several biological (Busiello et al., 2017) and physical (Einstein, 1905) systems. Furthermore, sparse influences also serve as the fundamental principle for various works in ICA (Zheng et al., 2022; Lachapelle et al., 2022), as well as other fields like causality (Spirtes et al., 2001; Raskutti et al., 2018). See also our response to Q5 for Reviewer ouDH. We will provide this discussion with further elaboration in the revision.\n\n**Q2: \"the triple-presentation of the optimization problem is a bit redundant\".**\n\nA2: Thanks for this suggestion. We will update the presentation of the optimization problem in the revision to make it concise.\n\n**Q3: \"Can the effect of sample size and covariance estimation be discussed?\"**\n\nA3: See our response to Q1 in the general response.\n\n**Q4: \"Does the resulting noise has an effect on 'admissible' sparsity level\".**\n\nA4: We sincerely appreciate this insightful question. In the current theoretical results, the resulting noise does not have an effect on \"admissible\" sparsity level. That is, as the reviewer nicely noted, the sparsity level $\\|\\mathbf{A}\\|_0$ is not constrained in any way beyond Assumptions 1 and 2. See also our reply to Q1 in the general response.\n\n**Q5: Computational complexity and \"is there any simplification over brute force\".**\n\nA5: Thanks for raising this excellent question which helps improve the clarity of the method. As the reviewer nicely mentioned, a straightforward and brute-force approach to compute the constraint term $h(\\mathbf{A})=\\operatorname{tr}\\left(\\sum_{k=2}^n (\\operatorname{off}(\\mathbf{A})\\odot \\operatorname{off}(\\mathbf{A}))^k\\right)$ is to compute each matrix power in $h(\\mathbf{A})$ and then sum their traces up; this approach requires $O(n)$ matrix multiplications. In our implementation, we adopt a more efficient approach with computational complexity of $O(\\log n)$ matrix multiplications, inspired by Zhang et al. (2020). The rough idea is to perform exponentiation by squaring (i.e., a general procedure similar to binary search) and recursively compute the term $h(\\mathbf{A})$. We will provide a detailed description of this procedure and its computational complexity in the final version.\n\n**Q6: \"no evaluation on real data\".**\n\nA6: See our response to Q2 in the general response.\n\n**Q7: Typos.**\n\nA7: Thanks for your careful reading. We will carefully proofread the paper to fix the typos in the revised version.\n\n**Q8: \"Assumption 3 is a bit unclear at first read\" and \"only one sense of the 'if and only if' is important\".**\n\nA8: Thanks for your constructive suggestion which helps improve the clarity of the assumption. We completely agree with the reviewer that only one sense of the \"if and only if\" is important. In light of your comment, we will reformulate Assumption 3 as follows:\n> **Assumption 3 (Faithfulness).** The resulting covariance matrix $\\mathbf{\\Sigma}=\\mathbf{A}\\mathbf{A}^\\top$ of mixing matrix $\\mathbf{A}$ satisfies a hard constraint $\\kappa$ only if $\\kappa\\in H(\\boldsymbol{\\xi}_\\mathbf{A})$.\n\n**Q9: \"What is the exact sense of 'asymptotically' in theorem 7?\"**\n\nA9: Thanks for asking this question. By \"asymptotically\", we intend to mean \"in the large sample limit\". That is, an infinite number of samples are given so that we have access to the true covariance matrix. We will update the term \"asymptotically\" to \"in the large sample limit\" in the revision to avoid possible confusion.\n\n**References:**\n\nD. M. Busiello, S. Suweis, J. Hidalgo, and A. Maritan. Explorability and the origin of network sparsity in living systems. Scientific reports, 7(1):1–8, 2017.\n\nA. Einstein. Does the inertia of a body depend upon its energy-content. Annalen der Physik, 18(13): 639–641, 1905.\n\nY. Zheng, I. Ng, and K. Zhang. On the identifiability of nonlinear ICA: Sparsity and beyond. In Advances in Neural Information Processing Systems, 2022.\n\nS. Lachapelle, P. R. López, Y. Sharma, K. Everett, R. L. Priol, A. Lacoste, and S. Lacoste-Julien. Disentanglement via mechanism sparsity regularization: A new principle for nonlinear ICA. Conference on Causal Learning and Reasoning, 2022.\n\nP. Spirtes, C. Glymour, and R. Scheines. Causation, Prediction, and Search. MIT press, 2nd edition, 2001.\n\nG. Raskutti and C. Uhler. Learning directed acyclic graph models based on sparsest permutations. Stat, 7(1):e183, 2018.\n\nZ. Zhang, I. Ng, D. Gong, Y. Liu, E. M. Abbasnejad, M. Gong, K. Zhang, and J. Q. Shi. Truncated matrix power iteration for differentiable DAG learning. In Advances in Neural Information Processing Systems, 2022."}, {"review_id": "8osYYQxa61", "reviewer": "Reviewer_vUDk", "summary": "This paper considers the problem of estimating a mixing matrix $A^*$, given measuremnts $x = A^* s$. The authors show that under Gaussian $s$, some assumptions on $A$, and using infinite $x$, the sparsest $A$ that satisfies $AA^{T} = A^* A^{* T}$ recovers $A^*$ upto permutation and sign of the columns.\n\nThe authors also show connections to causal discovery in the case of structural equation models.\n\nSince the sparse norm is non-convex, the authors propose a convex relaxation using the $\\ell_1$-norm that can be run in practice. \n\nThe sparsity assumptions on $A$ induce polynomial constraints $H(A)$ on the elements of the matrix $\\Sigma = AA^T$. These constraints are typically hard to compute, but the authors define an auxilliary function $h(A) = \\text{tr} ( \\sum_{k=2}^{n} off(A) \\odot off(A) )$, where $off(A)$ is the off-diagonal version of $A$, and $\\odot$ is the Hadamard product. The constaint set now becomes $h(A) = 0$, and the authors show that convex solvers can work in this setting.\n\n\nMinor:\nUsing $H$ for the set of hard constraints and $h$ for the trace of the defined matrix is slightly confusing, please change it.", "questions": "- I'm not an expert on causal discovery. Are the connections between ICA and identifiability of structural equations established results? Relatedly, can you explain your contributions over existing work.\n\n- The authors should spend more time commenting on the technical quality of the results. In some sense, the extension from the non-convex program to the convex relaxation is ``expected''. What new technical tools were required over traditional sparsity? Without commenting on this, it would seem that choosing the right assumptions (1-3) are the key for this paper. ", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The authors show that their assumptions on the matrix are strictly weaker than existing approaches (Section 3.3)\n- The authors show connections to causal discovery, which I thought were interesting.\n- Existing approaches cannot handle Gaussian sources $s$, as this induces rotational symmetry on $AA^T$, and hence we can only recover $A$ upto rotation. In contrast, the current work can recover it upto permutation and sign of the matrix.\n- The authors are able to show that the convex relaxation in Section 4 recovers $A$ in the asymptotic limit of infinite samples of $x$.\n- Experimental results are nice.\n", "weaknesses": "- The identifiability results are for infinite samples of $x$.\n\n- No runtime guarantees\n\n- The authors should spend more time commenting on the technical quality of the results. In some sense, the extension from the non-convex program to the convex relaxation is ``expected''. What new technical tools were required over traditional sparsity?\n\n- Experiments are a little simplistic, but that's fine for a theory paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback and time devoted to our work. Below we give a point-by-point response to the comments.\n\n**Q1: \"Using $H$ for the set of hard constraints and $h$ for the trace of the defined matrix is slightly confusing, please change it\".**\n\nA1: Thanks for this suggestion which helps improve the notations. We will change $h(\\mathbf{A})$ to other notation such as $g(\\mathbf{A})$ in the revision.\n\n**Q2: \"The identifiability results are for infinite samples\".**\n\nA2: See our response to Q1 in the general response.\n\n**Q3: \"No runtime guarantees\".**\n\nA3: Thanks for pointing this out. This is an excellent point. Here, we briefly discuss the overall runtime/complexity of the estimation method. For instance, considering the likelihood-based method  (i.e., Algorithm 2) with L-BFGS, each inner iteration of the quadratic penalty method (corresponding to the L-BFGS run) has a computational complexity of $O(m^2 n^2 + m^3 + m n^2 t )$, where $m\\ll n^2$ is the memory size of L-BFGS and $t$ is the number of iterations of L-BFGS. Typically, we have $t=250$ for each L-BFGS run, and $125$ iterations for the quadratic penalty method. In practice, for the experiments in Figure 1, the average runtime of the likelihood-based method is roughly $2$ minutes on CPUs. (It is worth noting that the runtime can be significantly shortened with GPU acceleration.) We will provide this discussion with further explanation in the revision.\n\n**Q4: \"Are the connections between ICA and identifiability of structural equations established results? Relatedly, can you explain your contributions over existing work.\"**\n\nA4: Thanks for this insightful question, which helps make our contributions clearer. As acknowledged by Reviewer ouDH and discussed in Lines 201-206, the connection between ICA and identifiability of structural equations has been established based on non-Gaussianity. One of our contributions is to extend the connection between ICA and structural equations to the case of Gaussianity (i.e., second-order statistics), which further bridges the gap between these two fields. Specifically, we provide an analogy of score-based causal discovery method (based on sparsity and second-order statistics) in ICA, which is rather different from the known connection based on non-Gaussianity. We will provide a detailed discussion to make our contributions for this part clearer in the revision.\n\n**Q5: \"What new technical tools were required over traditional sparsity?\"**\n\nA5: We sincerely appreciate this thoughtful question. Apart from traditional sparsity, we completely agree with the reviewer that choosing the right assumptions 1 to 3 are important for the identifiability/identification. Furthermore, the characterization (i.e., Proposition 4) of matrices $\\mathbf{A}$ satisfying Assumption 2 (see Eq. (3)) is also a key technical tool of the proposed identification method, because it allows us to formulate the problem as a continuous constrained optimization problem. We will include this discussion with further explanation in the final version.\n\n**Q6: \"Experiments are a little simplistic\".**\n\nA6: See our response to Q2 in the general response."}, {"review_id": "kt43Xy8ERJ", "reviewer": "Reviewer_ouDH", "summary": "This paper provides theorems under which the mixing matrix of linear ICA with Gaussian sources can be identified. While Gaussian sources are known to be unidentifiable in the classical ica theory, identifiability is possible if certain sparse structure is assumed for the mixing matrix as was initailly shown in Zheng. The assumptions in Zheng were restrictive however. This work expands the work of Zheng to provide more general conditions, namely:\n- assumption of structural provided is much less restrictive on the sparsity pattern\n- necessity of this assumption is proven (under the problem considered here)\n- connection of this approach to causal discovery is shown\n- the theorems lead to new estimation methods based on second-order statistics that allow ICA to be applied on Gaussian sources\n", "questions": "More concerns and things I'd expect revised for me to improve my score:\n\nline 16-17: the examples+reference here are pretty much straight form Hyvärinen (Independent Component Analysis: Algorithms and Applications, section 7). Perhaps with a bit more originality and effort some more varied, newer, examples or at least references could be provided?\n\n\"distribution of Gaussian sources, the sparsity of the mixing matrix undergoes noticeable changes.\" Could you clarify what is meant here?\n\nPlease include \"links\" to relevant proofs in the text. At the moment one has to wonder in the appendix to see whether the proofs exist. \n\n329: \"...based method (Eq. (8) or Eq. (9)) on data where both Assumptions 1 and 2 do not hold\" The grammar could be polished as now it could mean \"where assumption 1 and 2 do not hold at the same time\"  or that \"neither assumptions 1 and 2 hold\"", "limitations": "Authors do indeed point out the limited applications to real world data. Authors also admit that \" Since the true generating process of real-world data is inaccessible, it is challenging to quantitatively  evaluate the applicability of these sparsity assumptions.\" \n\nhowever there is no discussion on why the experimental results are not as good as one would expect, this would be welcome. \n", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Strengths:\n- the paper is in general well written and of good quality\n- the assumptions on sparsity are more much more reasonable than in previous works and should allow for future works in this area. To this end theorems 2 and 3 provide relevant and useful comparison\n- theoretical assumptions are also often nicely illustrated with examples\n- some nice approach of transforming the theorems into algorithms in a justified manner (e.g. framing the search space of A; theorem 6)\n- connection between ica and causal discovery is well known and this paper further contributes to that similarity\n- addition of a necessary condition is a nice result and helps to understand the limits of this approach \n\n\n", "weaknesses": "Weaknesses:\n\nThe biggest conceptual problem I have is that the identifiability here is framed in terms of an optimization problem where the ground-truth covariance matrix is assumed. I find this idea hard to follow since identifiability should be a property of the data model. Typically the process is to assume that we have $\\log p(x; \\theta) = \\log p(x; \\hat{\\theta})$ and then show that this implies $\\theta \\sim \\hat{\\theta}$ -- this approach makes sense as the starting point, equality of likelihoods, can be justified on the basis of MLE and its guarantees (at least in theory). Here instead one seems to start with the assumption that $AA' = \\hat{A}\\hat{A}'$. But the justification for this starting point is missing -- you should write it out fully. Also, in practice the empirical covariance matrix is used (eq. 8) but what are the guarantees here? I'm quite happy to revise my score upwards once this, and below, are discussed. \n\nI think the practical motivations for this paper are lacking and weak, perhaps partly due to a bit of unclear writing. For example, the authors write that \"many biological traits ... are often normally distributed\" to justify the importance of doing ica on Gaussian latents. But those listed biological signals are *not* typically latent, but often observed (after noise) and can usually be handled by standard ICA as there is no problem of Gaussian observations. Of course, it is possible to have latent biological signals too but that should be explained more carefully. It should be stressed however that the work still has important contribution in terms of fundamental research -- practical appeal does not always need to be obvious, so this is not necessarily a big problem. Authors also write that one possible situation in which their theorems are more useful than previous works, is when \"an observed variable serves as a root cause\". This may be possible but goes against the typical idea of ICA where observations are all assumed mixtures of independent latents. I feel this is however more easily understood in causal framwork. This leads to my next point...\n\nI find in general that ideologically this work is in some sense difficult to place as it feels like the ideas are more relevant to causal discovery yet it's framed as an ICA paper. But the assumptions on sparsity can still be quite restrictive and a substantially sparse mixing matrix, again, goes against the whole concept of ICA in some sense -- we are not really solving the mixing matrix problem if the mixing that happens is quite limited. Despite the examples given, it is still hard to understand exactly how restrictive sparsity assumptions are *in practice*.\n\nI find the estimation algorithm of the decomposition-based method in general a bit difficult to justify; optimally you would use an $l_o$ regularizer as this would agree with theory but that seems difficult to optimize. The likelihood-based method seems much more principled and I wonder if this paper could have been better framed around likelihood-based methodology in general.\n\nI'm surprised by the poor experimental results -- typically linear ICA achieves 0.99 correlation to the ground-truths eg. with FastICA so I would have expected similar results here. There are also no experiments on real data (not necessarily a big problem due to the breadth of theory here).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the reviewer's constructive comments, many of which will help improve the clarity of our paper. We have tried to address all the concerns in the following.\n\n**Q1: Justification to start with $AA'=\\tilde{A}\\tilde{A}'$ is missing.**\n\nA1: We sincerely appreciate this insightful comment, which helps improve the clarity of our theoretical results. We agree that the typical starting point of identifiability proof is \"equality of likelihoods\". In fact, this is exactly the tool used in our proof of likelihood method. In the large sample limit (as is the case for typical justification of MLE), one can show that $L(\\mathbf{A};\\bar{\\mathbf{\\Sigma}})=L(\\tilde{\\mathbf{A}};\\bar{\\mathbf{\\Sigma}})$ implies $\\mathbf{A}\\mathbf{A}^\\top=\\tilde{\\mathbf{A}}\\tilde{\\mathbf{A}}^\\top$ (see Eq (9) for exact form of likelihood $L(\\cdot)$).\n\nIn Theorems 1 and 6, we start with $\\mathbf{A}\\mathbf{A}^\\top=\\tilde{\\mathbf{A}}\\tilde{\\mathbf{A}}^\\top$ because this is the essential assumption used by the proof. This leaves the door open for different ways to achieve $\\mathbf{A}\\mathbf{A}^\\top=\\tilde{\\mathbf{A}}\\tilde{\\mathbf{A}}^\\top$, i.e., via decomposition or likelihood method, both of which are correct in the large sample limit. We will discuss this further in the revision.\n\n**Q2: Guarantees for empirical covariance matrix.**\n\nA2: See our response to Q1 in the general response.\n\n**Q3: lack of practical motivations and \"it is possible to have latent biological signals too but that should be explained more carefully\".**\n\nA3: Thanks for the suggestion. In light of it, we will modify the sentence \nto emphasize that the real-world usage scenarios center on potential latent Gaussian sources. We will also include additional examples besides biology. For instance, the thermal noises in electronic circuits typically adhere to Gaussian distributions (Ott, 1988), of which their mixtures posing challenges to traditional separation techniques.\n\n**Q4: \"an observed variable serves as a root cause\" and \"goes against the typical idea of ICA\".**\n\nA4: Thank you for pointing this out. In light of your comment, we will remove that related part to avoid possible misunderstanding.\n\n**Q5: \"assumptions on sparsity can still be quite restrictive\" and \"it is still hard to understand exactly how restrictive sparsity assumptions are\".** \n\nA5: Thanks a lot for this thoughtful comment. We completely agree with you that our assumption may be violated in certain situations, and we do not expect our theory to apply to all scenarios. However, given that the problem has clear practical implications and that the sparsity assumptions are expected to hold true for certain mixing matrices, it seems essential to start this line of research, and to weaken the sparsity assumptions as much as possible. This extends the applicability of these approaches to cover more general mixing matrices. We also hope that this work will inspire alternative results to make gaussian sources identifiable.\n\nIt is worth noting that sparsity assumptions are particularly relevant when observations are influenced by sources in a \"simple\" manner, as also discussed in [33]. For instance, ecological, gene-regulatory, and metabolic systems in biology often exhibit sparse interactions (Busiello et al., 2017). Similarly, in physics, complex observed phenomena may often be governed by a relatively small set of fundamental laws, exemplified by Einstein's theory of special relativity (Einstein, 1905). In our revised paper, we will delve into these aspects further, providing a more comprehensive perspective on the practical implications of our theory.\n\n**Q6: Frame the paper around likelihood-based methodology.**\n\nA6: Thanks for this constructive suggestion. We agree that optimally we would use an $\\ell_0$ regularizer for decomposition-based method. This partly explains why likelihood method performs slightly better than decomposition method. Following your suggestion, we will restructure Section 4.2 to place more emphasis on the likelihood method.\n\n**Q7: \"no experiments on real data\".**\n\nA7: See our response to Q2 in the general response.\n\n**Q8: Provide more original, varied, newer examples/references.**\n\nA8: Beside examples in Lines 16-17, we will include biology (Teschendorff et al., 2007; Biton et al., 2014), astronomy (Nuzillard et al., 2000; Akutsu et al., 2020), and earth science (Kaplan, 2003; Moulin et al., 2022) in the revision.\n\n**Q9: Clarify \"sparsity of the mixing matrix undergoes noticeable changes\".**\n\nA9: This means that, after rotation of the mixing matrix, the support of the mixing matrix may be changed, leading to a denser mixing matrix, although the resulting distribution of the observed variables remains unchanged. Similar intuition is explained in Lines 172-174. We will clarify this further in the revision.\n\n**Q10: Include links to proofs.**\n\nA10: We will include the links in main texts to guide readers to the relevant proofs in the Appendix sections.\n\n**Q11: Polish the grammar of \"329: ...based method ... do not hold\".**\n\nA11: We will modify the phrase to \"where neither Assumption 1 nor Assumption 2 holds\".\n\n**Q12: \"typically linear ICA achieves 0.99 correlation\" and \"no discussion on why the experimental results are not as good as one would expect\".**\n\nA12: Thanks for bringing up this question and your insightful observation. Since the experiments involve Gaussian sources, FastICA does not perform well because it is based on non-Gaussianity. For our method that can handle Gaussian sources, the optimization may return suboptimal local solutions, so the experimental results are not as good as one would expect (despite still outperforming FastICA). This further demonstrates the difficulties posed by Gaussian sources due to rotational invariance, and indicates that further research could enhance the performance. We will discuss this in the revision."}, {"review_id": "HWN9l5SjEy", "reviewer": "Reviewer_6AWD", "summary": "Aiming to address rotational invariance of Gaussian sources, this work first proposed an ICA identifiability theory based on Structural Variability. It then proposed two methods based on sparsity regularization and continuous constrained optimization to estimate the mixing matrix. It also made connections between ICA and causal discovery. It finally showed preliminary results to validate the proposed theory and estimation methods.", "questions": "1. Example 1: I understand the derivation in this example but I wonder how to identify such constraints. Do we have to derive these hard or non-hard constraints for each matrix? Are there any general principles to derive such constraints? If so, please briefly explain the principles. If not, it doesn't seem to be computationally efficient to derive these constraints as the dimension of A increases.\n\n2. Line 130: Please elaborate what \"sufficiently diverse effect\" means exactly.\n\n3. Do you have any explanations about the performance difference from two estimation methods in Figure 1? For example, decomposition method seems worse than likelihood method in vanilla case.", "limitations": "See Weaknesses.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The proposed method could be potentially useful as it claims to identify linear Gaussian sources with a weaker assumption compared to structural sparsity. \n\n2. The notations, theorems and proofs are clear in general. \n\n3. The proofs or explanations in the Appendix are very detailed and helpful. \n\n4. The author(s) conducted experiments to validate their theory and showed the effectiveness of the proposed SparseICA method in two simulated datasets.", "weaknesses": "1. As the author(s) pointed out, my main concern is that there is no sufficient empirical evaluation to demonstrate the effectiveness and generalizability of the proposed theory. Current experiments only used simulated data in two settings. How does the proposed theory work on real-world datasets? This work would be more convincing if there were experiments on real-world datasets.\n\n2. Additionally, the author(s) argued that the theory proposed by Zheng et al. 2022 couldn't capture hierarchical structures (lines 39 - 41), but it doesn't seem that the authors performed experiments to identify Gaussian sources which are organized in a hierarchical manner.\n\n3. I don't feel all theorems/assumptions/examples were explained very clearly, but I also note that the author(s) provided detailed proofs or explanations for each proposed theorem/assumption/example in the Appendix. So I would suggest that the author(s) try to organize the manuscript more logically and guide readers to the corresponding Appendix section in the main text. \n\n4. There are a lot of typos in the present manuscript. For example, line 71: $j$-th column by $a_{:, j}$; line 104: Section 3.2; line 248: there exists; line 254: repeated \"with\". Please proof-read the manuscript prior to submission.\n\n5. There is no statistical test to compare results. \n\n6. There is no code provided to replicate the results. Please consider making the code publicly available.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the time dedicated to reviewing our paper and the constructive suggestions. Our responses to these comments are given below.\n\n**Q1: \"no sufficient empirical evaluation\" and \"how does the proposed theory work on real-world datasets?\"**\n\nA1: See our response to Q2 in the general response.\n\n**Q2: \"it doesn't seem that the authors performed experiments to identify Gaussian sources which are organized in a hierarchical manner\".**\n\nA2: Thank you for pointing this out. Given your comment, we will remove that part in Lines 39-41 to avoid possible misunderstanding. This is because we are focusing on the ICA task that is not directly related to hierarchical structures (though indirect connection may exist). \n\nAs indicated by Theorems 2 and 3, the structural conditions by Zheng et al. (2020) are somewhat restrictive because they cannot handle cases where the set of observed variables influenced by one source is a superset of those affected by another source. Our proposed approach, on the other hand, is considerably less restrictive and introduces more flexibility, thereby enhancing the applicability with Gaussian sources. We will further clarify these points in the revised version to improve the clarity of our work.\n\n**Q3: \"organize the manuscript more logically and guide readers to the corresponding Appendix section in the main text\".**\n\nA3: Thanks for the helpful suggestion which helps improve the presentation of the paper. In the revision, we will include the 'links' in the main text to guide readers to the relevant Appendix section, especially for the proofs. Furthermore, we will organize the manuscript, such as the appendices, more logically to improve the presentation.\n\n**Q4: Typos.**\n\nA4: Thank you for your careful reading. We will carefully proofread the manuscript to fix the typos in the revision.\n\n**Q5: \"There is no statistical test to compare results.\"**\n\nA5: Thanks for pointing this out. In light of your comment, we have additionally applied Wilcoxon signed-rank test (at $5$% significance level), and found that the improvements of the proposed method, e.g., in Figure 1, are statistically significant. We will include these statistical tests in the final version of the paper.\n\n**Q6: \"There is no code provided to replicate the results. Please consider making the code publicly available.\"**\n\nA6: Thanks for this comment. The link to the code has been provided in Lines 862-863 in Appendix D. In light of your comment, we will move the link to Section 5 in the revised paper.\n\n**Q7: \"Do we have to derive these hard or non-hard constraints for each matrix? Are there any general principles to derive such constraints?\"**\n\nA7: We sincerely appreciate this insightful question. The examples of hard and non-hard constraints (Example 1) serve as illustration purposes for different types of constraints. In practice, during estimation (i.e., Algorithms 1 and 2), we do not have to derive any of these hard and non-hard constraints. The only place involving these constraints is Assumption 3, which requires that the hard constraints (if exist) of the covariance matrix arise from the support of the mixing matrix; even in this case, we do not have to derive these hard constraints. In the revision, we will include a discussion in Section 3 to make this clear.\n\n**Q8: \"Please elaborate what 'sufficiently diverse effect' means exactly.\"**\n\nA8: Thanks for this suggestion. \"Sufficiently diverse effect\" means that the conditional distribution of sources given the auxiliary variable must vary sufficiently with the auxiliary variable and thus is more complex. This is often expressed in terms of the first-order and second-order derivatives of the conditional distribution; see the precise definition in Hyvärinen et al., (2019, Theorem 1). We will provide a detailed explanation in the revision.\n\n**Q9: \"Do you have any explanations about the performance difference from two estimation methods in Figure 1?\"**\n\nA9: Thanks for the thoughtful question. A possible reason is that the decomposition-based method involves additional constraint (Eq. (8)) as compared to likelihood-based method (Eq. (9)). Therefore, the resulting optimization problem of  decomposition-based method might be harder to solve and contain suboptimal local solutions. We will include this explanation in Section 5 of the revision.\n\n**References:**\n\nA. Hyvärinen, H. Sasaki, and R. Turner. Nonlinear ICA using auxiliary variables and generalized contrastive learning. In International Conference on Artificial Intelligence and Statistics, 2019."}]

Author rebuttal:
We thank all of the reviewers for the valuable feedback and time devoted to reviewing our work. We are encouraged that they found our work to be interesting (zk7j, vUDk), developed (zk7j), and useful (6AWD). We are grateful that the reviewers appreciate our theoretical (zk7j, vUDk, ouDH, 6AWD) and methodological (vUDk, ouDH, 6AWD) contributions; specifically, Reviewer ouDH believes that our "assumptions on sparsity are more much more reasonable than in previous works and should allow for future works in this area". Reviewers zk7j, ouDH, and 6AWD also appreciate that the theoretical assumptions/results are presented in a clear way, often illustrated with explanations and examples.

We take the opportunity to clarify below common questions raised by the reviewers. We also provide individual responses to address the comments of each reviewer.

**Q1: Identifiability for finite samples.**

A1: We greatly appreciate this insightful comment. It is worth noting that ICA with Gaussian sources is a challenging ill-posed problem due to the rotational invariance of the Gaussian distribution. Therefore, establishing identifiability results for infinite samples is itself a fundamental problem, and this type of "possibility" identifiability results are needed before one is able to establish guarantees on finite samples.

Given our identifiability result on infinite samples, it will become clear that the problem is solvable under appropriate assumptions. The next step is then to extend this result for finite samples. The empirical studies in Appendix E demonstrate the effectiveness of our method for finite samples, thereby showcasing the potential to extend our identifiability result from infinite to finite samples. We will provide this discussion in the revision.

**Q2: Experiments on real data.**

A2: As acknowledged by Reviewers vUDk and ouDH, the lack of experiments on real data is not necessarily an issue "due to the breadth of theory here". At the same time, in light of the comment, we will incorporate an additional experiment on a real dataset with fMRI data. Due to the time constraint, we are conducting preliminary experiments using the dataset considered by Richard et al. (2021), by adapting the multi-subject data to suit our specific context. We find that the preliminary results align with the observations reported in Section 5. We will include experimental details and final results in the revision.

**References**

H. Richard, P. Ablin, B. Thirion, A. Gramfort, and A. Hyvarinen. Shared independent component analysis for multi-subject neuroimaging. In Advances in Neural Information Processing Systems, 2021.

Meta-review: This paper proposes a new theory for the identifiability of linear ICA when the sources are Gaussian. It presents new assumptions on the mixing matrix that allows recovery.

The proposed theory is sound, and the assumptions are weaker than those of previous works. The preliminary experiments were quite toy but this is not a problem from a theory paper, and it does not raise concerns regarding the soundness of this work.

All reviewers except reviewer ouDH advocate for acceptance. Initial concerns raised by rev. ouDH were addressed by the authors; then rev. ouDH pointed out the lack of real-world experiments, which the authors addressed in their last experiment.
Decision: Accept (poster)