Generalizing Nonlinear ICA Beyond Structural Sparsity
Authors: Yujia Zheng
Kun Zhang
Venue: NeurIPS 2023 oral (2023)
Keywords: Latent variable models
nonlinear independent component analysis
TL;DR: We establish a set of new identifiability results of nonlinear ICA in the general settings of undercompleteness, partial sparsity and source dependence, and flexible grouping structures.

Abstract: Nonlinear independent component analysis (ICA) aims to uncover the true latent sources from their observable nonlinear mixtures. Despite its significance, the identifiability of nonlinear ICA is known to be impossible without additional assumptions. Recent advances have proposed conditions on the connective structure from sources to observed variables, known as Structural Sparsity, to achieve identifiability in an unsupervised manner. However, the sparsity constraint may not hold universally for all sources in practice. Furthermore, the assumptions of bijectivity of the mixing process and independence among all sources, which arise from the setting of ICA, may also be violated in many real-world scenarios. To address these limitations and generalize nonlinear ICA, we propose a set of new identifiability results in the general settings of undercompleteness, partial sparsity and source dependence, and flexible grouping structures. Specifically, we prove identifiability when there are more observed variables than sources (undercomplete), and when certain sparsity and/or source independence assumptions are not met for some changing sources. Moreover, we show that even in cases with flexible grouping structures (e.g., part of the sources can be divided into irreducible independent groups with various sizes), appropriate identifiability results can also be established. Theoretical claims are supported empirically on both synthetic and real-world datasets.

Generalizing Nonlinear ICA Beyond Structural Sparsity
Yujia Zheng', Kun Zhang
Carnegie Mellon University
Mohamed bin Zayed University of Artificial Intelligence {yujiazhy kunzi]@cmu.. edu
Abstract
Nonlinear independent component analysis (ICA) aims to uncover the true latent sources from their observable nonlinear mixtures. Despite its significance, the identifiability of nonlinear ICA is known be impossible without additional as- sumptions. Recent advances have proposed conditions on the connective structure from sources observed variables, known as Structural Sparsity, to achieve identi- fiability in unsupervised manner. However, the sparsity constraint may not hold universally for all sources in practice. Furthermore, the assumptions of bijectivity of the mixing process and independence among all sources, which arise from the setting ICA, may also be violated in many real-world scenarios. To address these limitations and generalize nonlinear ICA, we propose set of new identifiability sults in the general settings of undercompletennss,, partial sparsity and source depen- dence, and flexible grouping structures. Specifically, prove identifiability when there are more observed variables than sources (undercomplete), and when certain sparsity and/or source independence assumptions are not for changing sources. Moreover, we show that even in cases with flexible grouping structures (e.g., part of the sources be divided into irreducible independent groups with various sizes), appropriate identifiability results can also be established. Thcoretical claims are supported empirically both synthetic and real-world datasets.
Introduction
The unveiling of the true generating process of observations is fundamental to scientific discovery. Nonlinear independent component analysis (ICA) provides statistical framework that represents of observed variables as nonlinear mixture of independent latent sources 8, i.e., fs)). Unlike linear ICA (Comon, 1994), the mixing function can be an unknown nonlinear function, thus generalizing the theory more real-world tasks. However, the identifiability nonlinear ICA has been a long-standing problem for decades. The main obstacle is that, without additional assumptions, there exist infinite spurious solutions returning independent variables that are mixtures of the true sources (Hyvärinen and Pajunen, 1999). In the context of machine learning, this makes the theoretical analysis of unsupervised learning of disentangled representations difficult (Locatello et al., 2019).
To overcome this challenge, recent work has introduced the auxiliary variable u, and assumed that all sources are conditionally independent given Most of these methods require auxiliary variables to be observable, such as class labels and domain indices (Hyvärinen and Morioka, 2016; Hyvärinen al., 2019; Khemakhem et al., 2020a; Sorrenson al., 2020; Lachapelle et al., 2022; Lachapelle and Lacoste-Julien, 2022), with the exceptions being those for time series (Hyvärinen and Morioka, 2017: Hälvä et al., 2021; Yao al., 2021, 2022). While the use of the auxiliary variable allows for the identifiability of nonlinear ICA with mild restrictions on the mixing process, it also necessitates a large number of distinct values of u, which can be difficult obtain tasks with insufficient side informa-
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

tion. Moreover, since these results assume that all sources are dependent on u, they cannot accommo- date a subset of sources with invariant distributions (e.g., content may not change with different styles).
Another possible direction is to impose appropriate conditions on the mixing process, but limited results are available in the literature. For example, it has been shown that conformal maps are identifiable up to specific indeterminacies (Hyvärinen and Pajunen, 1999; Buchholz et al., 2022). Moreover, Taleb and Jutten (1999) identify the latent sources when the mixing process is a component-wise nonlinear function added to a linear mixture. These methods do not rely on conditional independence given the auxiliary variable and thus achieve the identifiability in a fully unsupervised setting. At the same time, the requirement of above mentione classes of the mixing function, such as conformal maps and post-nonlinear models, restricts the applicability of the results in another way. For instance, according to Liouville's 's theorem (Monge, 1850), conformal maps in Euclidean spaces of dimensions higher than two are Möhius transformations, which appear to be overly restrictive for most data-generating processes. As an alternative, Zheng et al. (2022) prove that, under the assumption of Structural Sparsity, the true sources can be identified up to trivial indeterminacies. Since the proposed condition is on the connective structure from sources to observed variables, i.e., the support of the Jacobian matrix of the mixing function, it does not require the mixing function to be of any specific algebraic form. Thus, Structural Sparsity may serve one of the first general principles for the identifiability of nonlinear ICA in a fully unsupervised setting.
While being potential solution to the identifiability of nonlinear ICA without side information, the assumption of Structural Sparsity has its limitations from a pragmatic viewpoint. The most obvious one arises from the fact that it may fail in number of situations where the generating processes are heavily entangled. Although the principle of simplicity may be general rule in nature, it is intuitively possible that Structural Sparsity does not apply to at least a subset of sources, such as one or a few speakers in a crowded room. Unfortunately, Zheng et al. (2022) require Structural Sparsity to hold for all sources in order to provide any identifiability guarantee. Therefore, it would be desirable in practice to provide weaker notions of identifiability, such as the ability to identify a subset of sources to trivial degree of uncertainty, in cases of partial sparsity.
In addition to partial sparsity, identifiability with Structural Sparsity also fails with the undercomplete- ness (more observed variables than sources) and/or partial source dependence (potential dependence among some hidden sources). These limitations are not unique to the sparsity assumption, but rather a result of the traditional setting of ICA, where the numbers of the sources and observed variables must be equal and dependencies among sources are not allowed. However, both situations are quite common in practice. One may easily have millions of pixels (observed variables) but only dozens of hidden concepts (sources) in a picture, constituting an undercomplete case that cannot be handled by previous results. Meanwhile, dependencies among some variables are also prevalent in tasks such as computational biology (Cardoso, 1998; Theis, 2006). The alternative assumption of conditional independence given auxiliary variables may still be overly restrictive if applied universally to all sources. For the identifiability of nonlinear ICA to truly benefit scientific discovery in a wider range of scenarios, these methodological limitations should be properly addressed.
Aiming to generalize nonlinear ICA with Structural Sparsity, we first present a set of new identifiabil- ity results to address these fundamental challenges of undercompleteness, partial sparsity, and source dependence. We show that, under the assumption of Structural Sparsity and without auxiliary vari- ables, latent sources can be identified from their nonlinear mixtures up to component transformation and a permutation, even when there are more observed variables than sources (Thm. 3.1). Moreover, if the assumption of sparsity and/or source independence does not hold for some changing sources, we provide partial identifiability results, showing that the remaining sources can still be identified up to the same trivial indeterminacy (Thm. 4.1, Thm. 4.2). Furthermore, in the cases with ficxible grouping structures (c.g., part of the sources can be grouped into irreducible independent subgroupings with various sizes, such as mixtures of signals with various dimensions). certain types of identifiability are also guaranteed with auxiliary variables (Thm. 4.3, Thm. 4.4). Therefore, we establish, to the best of our knowledge, one of the first general frameworks for uncovering latent variables with appropriate identifiability guarantees in a principled manner. The theoretical claims are validated empirically through our experiments and many previous works involving disentanglement.
invertible
2

---

2 Preliminaries
The -ata-generatinn process of nonlinear ICA is follows:
Ps (s II Ps. (8.),
(1)
i=1 x= x=f(s),
(2)
where s = (S)....,55,) E S I" is a latent vector representing the independent sources, and (X1y...y (.m) X RT denotes the observed random vector. The mixing function is assumed to be smooth in the sense that its second-order derivatives exist. The primary objective of ICA is to establish identifialee models, i.e., the sources
identifiable (recoverable) up certain indeterminacies by learning an estimated mixing function S X with assumptions identical to the generating process (Comon, 1994). Different from most ICA results where m = and f: S + X must be linear, we allow m > n (i.e., undercompleteness) and be a general nonlinear function, therefore extending the previous setting. Thus, we relax the previous assumption the invertibility of f, only necessitating to be injective and its Jacobian to be of full column rank. Furthermore, we denote Ps; as the marginal probability density function (PDF) of the i-th source s; and ps as the joint PDF the random vector s. Moreover, we introduce some additional technical notations as follows:
Definition 2.1. Given subset A {L..... n). the subspace RA is defined as
R (= R & = 2, 0}
where is the i-th element of the vector
That is. RA denotes the subspace of R" specified by an index set A. Furthermore, we define the support of a matrix as follows:
Definition 2.2. The support of a matrix M E Rmxx is defined as
sMpp(M) = ((1,5) M.,, 03.
With a slight abuse of notation, we reuse supp(-) to denote the support of matrix-valued function: Definition 2.3. The support of a function M θ - mxx" is defined as
supp(M(()) (it.)) 30 e,M(O),, + #).
For brevity, we denote F and as the support of the Jacobian Js(s) and J ($). respectively. Ad- ditionally, T refers to set of matrices with the same support of T(s) in J₃($) (s)), where T(s) is matrix-valued function. Throughout this work, for any matrix M. we use M., to denote its i-th row, and M.,, to denote its j-th column. For any set of indices B C {1,...,, m) x {11,... (1,...,W) n},
analogously, we have B = (j (i,j) B} and B == (i (i.j) E B).
3 Identifiability with undercompleteness
We first present the result on removing one of the major assumptions in ICA, i.e., the number of observed variables must be equal to that of hidden sources n. We prove that, in the undercomplete case (m > n.), sources can be identified up to a trivial indeterminacy under Structural Sparsity.
Theorem 3.1. Let the observed data be a large enough sample generated by an undercomplete nonlinear ICA model as defined in Eqs. (1) and (2). Suppose the following assumptions hold:
For each E (I,...,,)) n). there exist ) and a matrix T E T s.A. [F span(Jr(s(())..)) (i R7, and [Jr(s(tyT),, E R
it. (Structural Sparsity) For each E (I,...,m),, there exists C2 s.t. Niec, Fi,: (k.) Then s is identifiable up to an element-wise invertible transformation and a permutation.
The proof included in Appx. A.1, of which part of the conditions and techniques are based on (Zheng et al., 2022). It is noteworthy that, same as previous work, also need to add sparsity

---

regularization on the learned Jacobian during the estimation so that | < [FF,, which is required for all sparsity-based identifications throughout the paper and we only emphasize here for brevity.
Assumption i avoids some pathological conditions (e.g., samples are from very limited sub- populations that only span a degenerate subspace) and is typically satisfied asymptotically. The first part implies that there are at least FF.. observed samples spanning the support space, which is almost always satisfied asymptotically. The second part is also relatively mild. Note that T refers to a set of matrices with the same support of T(s) in ( (()))((s) and (S) E R Since we only
necessitate the existence of one matrix T T in the entire space, even in rare cases where these two matrices do not share the same non-zero coordinates due to non-generic canceling between specific values of elements, there is almost always an existence of a matrix T E T fulfilling the assumption.
Assumption ii, i.e., Structural Sparsity, originates from (Zheng et al., 2022). Intriguingly, compared to the original bijective setting considered by (Zheng al., 2022). this assumption is much more likely to be satisfied in the undercomplete case. The key reason is that only necessitates the existence of subset of observed variables whose intersection uniquely identifies the target source variable. For instance, regarding S in Fig. 1, there exist X and X4 S.L. the intersection of their parents is only 81. In principle, the size of this set can be quite small (e.g., one or two). Hence, it is very likely to be satisfied when there is sufficient number of observed variables (c.g., millions of pixels for images), which has also been verified empirically in our experiments (e.g.. Fig. 4 in Sec. 5). Additionally, in some tasks, we might even construct or select observations in data-centric manner to satisfy this assumption. Without the previous constraint of bijectivity, structural sparsity can truly be applied in much broader range of practical scenarios.
S2 Sg
X2
X3
X5
X
Figure I: The structural sparsity assumption in the undercomplete case, where the matrix represents (s))
By proving the identifiability in the undercomplete case, we remove the previous assumption of bijectivity the mixing function f and thus generalizing the theory to more application scenarios. It worth noting that, while some work has provided results without assuming bijectivity (Khemakhem et al., 2020a), they rely on extra information from many distinct values of auxiliary variables. Dif- ferently, we do not need any auxiliary variables and follow a fully unsupervised setting; Zheng et al. (2022); Kivva et al. (2022) explore the undercompleteness without any auxiliary variable. However, Zheng et al. (2022) only remove the rotational indeterminacy in the nonlinear case and Kivva et al. (2022) assume Gaussian mixture priors, while provide the full identifiability result without distribu- tional assumptions. At the same time, as elaborated above, the assumption of Structural Sparsity has been significantly weakened in the undercomplete case considered by our theorem. Moreover, iden- tifiability with undercompleteness is also essential if assumptions are partially violated w.r.t. a subset of sources, of which the intuition is verified by theoretical results introduced in the following sections.
4 Identifiability with partial sparsity and source dependence
Under the condition of Structural Sparsity, we show the identifiability of undercomplete ICA with general nonlinear functions (Thm. 3.1). While this removes the restriction of bijectivity between sources and observed variables, it remains uncertain as to whether Structural Sparsity holds for all sources in universal way. At the same time, even in the scenarios that Structural Spursity may not be universally satisficd for all sources, it is still valuable to consider its potential to hold true for a subset of sources. This type of partial sparsity may often be the case in practical scenarios, as illustrated by our experiments (c.g., Fig. 5 in Sec. 5). However, the corresponding partial identifiability. i.c., the theoretical guarantee for the identification of the subset of sources satisfying Structural Sparsity, is not achieved by (Zheng et al., 2022). In fact, as long as one or a few sources do not meet the assumption of Structural Sparsity, the previous work is unable to provide any identifiability guarantees.
Furthermore, in addition to the universal sparsity, the statistical independence between sources is another fundamental assumption. This assumption arises from the original setting of ICA and has been adopted in most related works. However, in many real-world scenarios, requiring all sources to be mutually independent might be impractical, and there are likely to be a subset of sources that

---

even the are dependent in some way. For example, the frequency and duration of smoking, as well as the type of tobacco products used, are all interrelated factors that contribute to the development of lung cancer. Without any identifiability guarantees in the case where there exist any dependent sources, it is quite restrictive for nonlinear ICA, and even its undercomplete extension, to successfully deal with real problems in practice. Therefore, similar to the partial sparsity case, it is highly desirable that alternative theoretical results, i.e., identifiability for independent sources, can be guaranteed even with the existence of dependent sources.
To deal with these remaining challenges in the considered undercomplete case, we further relax other assumptions with additional information. To start with, we provide an identifiability result when Structural Sparsity holds true for only a subset of sources, thus alleviating the obstacle of partial sparsity. Moreover. we relax the mutual independence assumption and allow for some changing sources to be dependent on each other. To this end, we partition the sources into two parts $ = [81, Sp). where variables in Sy are mutually independent, but those in Sp do not need to be. Let and sp correspond variables in with indices (1....,n)) and (N1+1:.... 1.1+1...,,.. .n), respectively. That is, S₁ ($1, ................................ 5n)) E S C [a and SD ($n,+1,.... 9n) E SD S RRD, We denote the i-th scalar element in a vector, say s, as 8,, For sources in Sp, they do not need to be mutually independent as long as they are dependent on variable i.e.
n,)
Th
(slu(s)u) (Spnu((p|u)) Il Ps. (8:).
It is noteworthy that we allow arbitrary relations between sources in sp- These sources might be grouped into several subspaces or actually be mutually independent, but we do not need to obtain this information as prior knowledge. This is essential since the exact dependence structures, number of dependent variables, are usually unknown in practice. By keeping this type of uncertainty for both partial sparsity and/or partial source dependence, one be more confident in applying the theoretical advancements of nonlinear ICA in various tasks. We prove the identifiability for this arguably more flexible scenario as the following theorems:
Theorem 4.1. Let the observed data be large enough sample generated by an undercomplete nonlinear ICA model defined in Eqs. (2) and (3). Suppose the following assumptions hold:
i. There exist nn + 1 distinct values of u. i.e., uj with j E 10.1...., nD), s.t. the un vectors w(sD, u, with i e (nz + I,... n) are linearly independent, where vector w(sp, u, i) is defined as follows:
① (logp(sp/uu) - log(p(sp) uo))
a ((ogp(sp)on ump) log (og(p(sp)uo))
w(SD, u)
ds:
Os:
i. There exist u1, U2 E u, s.t., for any set Ag C S with non-zero probability measure and cannot be expressed as BR, SD for any Bad C St, we have
[ Paju (s un) ds f Paju (s ug) ds.
SEEA,
SEA,,
Then sp is identifiable up to an subspace-wir wise invertible transformation.
Thm. 4.1 ensures the subspace-wise identifiability of sp. i.c., the estimated subspace &n contains all and only information from sp- This implies that we can disentangle and extract the invariant part of the latents, beneficial for tasks like domain adaptation where recovering each individual source might not be necessary as long as the subspace that is invariant across domains can be disentangled. Furthermore, we also prove the component-wis identifiability as follows:
Theorem 4.2. In addition to assumptions in Thm. 4.1, suppose the following assumptions hold:
i. For each i E (l....,nIh, there exist {s(0)) FFa span(Jr(s(0))... 1
and a matrix T E T S.f.
1==1
(i |Feing Ry Hi and [Jr (s yT] i,nt
E RR Framy"
it. (Structural Sparsity) For all le n... there exists C3 s.t. NiEC. Fr,ms = (k}. Then Si is identifiable up to element-wise invertible transformation and a permutation.
5

---

The proofs are presented in Appx. A.2 and Appx. A.3. We tackle the challenge of partial sparsity and dependence by necessitating Structural Sparsity and independence only on a subset of sources in sy and prove that these sources can be identified up to trivial indeterminacies. For the remaining sources in sp, they only need to be dependent on an auxiliary variable without necessitating conditional independence among sources or distributional assumption. This extends previous models that assume all sources to be conditionally independent given u (Hyvärinen et al., 2019; Lachapelle et al., 2022) or require the conditional distribution of the sources to be of specific form (Khemakhem et al., 2020b).
The assumption on p(sp|u () in Thm. 4.1 indicates that the auxiliary variable u should have a suf- ficiently diverse impact on sources without independence assumption (i.e.. sp). It follows a similar spirit to the standard assumption of variability (Hyvärinen et al., 2019) but we further relax it. Specifi- cally, we only need n +1 1 values of u for the identifiability of sources in sy. This is intuitively reason- able since the fewer changes (smaller np) a system has, the easier (fewer required values, i.e., up + 1) that larger part of it (larger n,, i.e., 71 nD)) is identifiable. In contrast, most previous works require all sources to be dependent on an auxiliary variable u with 2n++1 distinct values of u: no identifiability for any subset of sources can be provided if there exists any degree of violations, either on the number of sources dependent on u or the number of values u. This limits the application of these results to ideal scenarios where all sources are influenced by the same auxiliary variable with sufficient changes without any type of compromise. In practice, however, it is often the case that only a subset of sources benefit from the additional information provided by auxiliary variables, different auxiliary variables may affect different sources, or auxiliary variables do not contain sufficient information. Assumption ii in Thm. 4.1 is originally from (Kong et al., 2022) and also necessitate the presence of change. Intu- itively, the chance of having a subset Ag on which all domain distributions have an equal probability measure is very slim, which has been verified empirically in (Kong al., 2022). For both theorems, we consider the more challenging undercomplete case, for which the related identifiability results lacking in the literature. Additionally, unlike previous works assuming specific distributions of sources such as exponential families, we do not have similar distributional assumptions on the sources.
4.1 Results with flexible grouping structures
If we further have access to the dependence structure among variables in sp, additional identi- fiability results for these sources may also be established. For example, consider the setting that
SD 15..,....... sn) can be decomposed to d irreducible independent subspaces {Se...... Sea of which each is a multi-dimensionall vector consisting multiple sources. We denote the j-th consecutive d-dimensional vector (j-th subspace) in s as Se, (SG-1))++1.... Sjd) (Sc, ......,......................... s.,,..,,,))) s0,00), where 8 (e and 86,00 are the first and the last sources in Sey, respectively. Then we have
(s|u = II Ps. (s:) II Pr., (n(se, ju. jmm
This is similar to Independent Subspace Analysis (ISA) (Hyvärinen and Hoyer, 2000; Theis, 2006) but we allow only a subset of sources as a composition of (conditionally) independent subspaces instead of all, which formalizes the tasks of blind source separation or uncovering latent variable models with mixtures of both high-dimensional and one-dimensional signals. The considered general setting essentially covers ICA and ISA special cases: if n. n. it is consistent with the ICA problem; if nı O, all sources can be decomposed into irreducible independent subspaces, and thus it becomes an ISA problem. The identifiability result under this setting shown in the following theorem with its proof provided in Appx. A.4:
Theorem 4.3. Let the observed data be a large enough sample generated from an undercomplete nonlinear ICA model as defined in Eqs. (2) and (4). Suppose the following assumptions hold:
i. For each i E {l....,,I1 there exist {s Mt=1 span(Jr(s (s) Ft=1
( |Friny and a matrix T E
T s.t.
|Feinr =Ry H and [Jr(s s,on
E R Feimy
ii There exist 2np + 1 values of u, i.e., u, with i E 10. 2nD], s.t. the 2nd vectors w(sn, u:) w(sn, uo) with i E (1,..., 2nn} are linearly independent, where vector w(sn. u:) is defined as follows:
w(SD, u.) (V(Se) u.), ((Se, uz), v'(Se, ui),... .., ('(a,, U:))

---

where
2 log p(s,, u,)
llggpis p(se, (1:)
v(Sey: u.)
Ds (A)
0 log p(S., (,))
o log p(s,, (u:) (w)),
v' (Bee u:) -
(Bbe,t)) )2
iii. There exist u1 U2 E u, s.t., for any set Ag S with nonzero probability measure and cannot be expressed as Bs, Sp for any Bur C S1, have
f
Pa/u (s u1) ds # {
Palu (s U2) ds.
JEA,
BEA
iv. (Structural Sparsity) For all k E (I,...,n1), there exists C₁. s.l. Niec. Fi,ms = [k].
Then 8₁ is identifiable up to an element-wise invertible transformation and a permutation, and sp is identifiable up to subspace-war invertible transformation and subspace-wist permutation.
All assumptions align with the same principles as those elaborated in the theorems proposed above and have been adapted to cater to the flexible grouping structure. Specifically, in addition to the identifia- bility of sources in Sy. we prove that we can also identify sources in sp up to an indeterminacy that, for each C; E {ci..... ). there exists an invertible transformation ha, s.t. he, (sc.) = Sc, which is anal- ogous to the previous element wise indeterminacy. Consequently, even when dealing with mixtures of high and one-dimensional sources, like in the case of multi-modal data, we can still recover the hidden generating process to some extent. Based on the aforementioned theoretical results, which consider un- dercompleteness, partial sparsity, and partial source dependence, Thm. 4.3 further generalizes the iden- tifiability of nonlinear ICA by relaxing the dimensionality constraint of the latent generating factors.
In this vein, it is natural to consider another dependence structure, i.c., sources in d are not marginally but conditionally independent given an auxiliary variable u. This is similar to the assumption made in most previous works on identifiable nonlinear ICA with surrogate information, which assume that all sources are conditionally independent of each other given the auxiliary variable. However, our setting is more flexible in the sense that we do not assume all sources to be influenced by the auxiliary variable. Specifically, sources S7 are mutually independent as in the original ICA setting, while only sources in Sp have access to the side information from the conditional independence given i.e.,
fy
Ps|u (s/u) = II Pa, (s:)
II Ps)lu(s)lu).
(5)
i=1
j=N++1
The identifiability result for all sources (8; and sp) is follows with proof in Appx. A.5: Theorem 4.4. Let the observed data be a large enough sample generated from an undercomplete nonlinear ICA model as defined in Eqs. (2) and (5), suppose the following assumptions hold:
For each i (1....,nI), n1). there exist ( span(Jr(s( ( )imy))=: FF R Ri,,,, and [Jr(s! b,mE
and matrix T
T S.I.
ER! F..m
it There exist 2np + values of u, i.e. u, with i E 1......., 2... s.t. the 2np vectors w(sp, u,) w(SD, un) with i E ......,2ppl are linearly independent, where vector w(sp. u) is defined as follows:
w(sD, = (v(SD, u.), (((s,,,)))
where
Olog (0logp(8nzz (0nz+1 (u:)
a p(sn (u:) dsn
v(sp, u;) =
0sn,t1
8 log lologgssnntte (0sm
8 log u (0sn)²
v'(sD, u.) =
ii.. There exist U1 U2 u, s.t., for any set As C S with nonzero probability measure and cannot be expressed as BR, x Sp for any Baj C St, we have
[
JEEA. Pa/u (s uz) ds
Palu (s (22) ds.
JEEA.
7

---

iv. (Structural Sparsity) For all l E ni.....,n], there exists Cj s.t. Niec. Fi,m, = {k}.
Then s is identifiable up to an element-wise invertible transformation and a permutation.
With different assumptions on different sets of sources, one could view this theorem as an expansion of both previous theoretical findings that impose distributional constraints on sources with auxiliary variables (e.g., (Hyvärinen et al., 2019) and those that constrain the mixing function with Structural Sparsity (Zheng et al., 2022). This is particularly helpful in the context of safe-supeeeiee learning (Von Kügelgen et al., 2021) or transfer learning (Kong et al., 2022), where latent representations are modeled as a changing part and an invariant part. In (Kong et al., 2022), the component-we wise iden- tifiability for variables changing across domains (i.e., Sp with multiple values of u in our setting) are provided but not those in the invariant part (i.e., 8y in our setting). With the help of Thm. 4.4, we can show identifiability up an clement-wise invertible transformation and permutation for each source, regardless of whether it changes across domains or not, which may help some related tasks where full identifiability is necessary. Furthermore, for causal reasoning or disentanglement with observational time-series data, our theorem benefits the identifiability of temporal processes involving instantaneous relations. Previous works in that area can only deal with time-delayed/change rely on the global conditional independence of all sources given the changing time index as the auxiliary variable (Hyvärinen and Morioka, 2016, 2017; Yao et al., 2022). Our theorem, on the other hand, provides the added ability to identify unconditional sources, thanks to the partially satisfied sparsity assumption, and thus aids the uncovering of latent processes with instantaneous relations.
influences, as they
5 Experiments
In order to validate the proposed identifibaility results, we conduct experiments using both simulated data and real-world images. It is noteworthy that there has been extensive research that has empirically verified that deep latent variable models are likely to be identifiable in complex scenarios, particularly in the disentanglement task (Kumar et al., 2017: 70 Klys et al., 2018; Locatello et al., 2018; 8; Rubenstein et al., 2018; Chen et al., 2018; Burgess et al., 2018; Duan et al., 2020; Falck et al., 2021; Carbonneau et al., 2022). While we are not sure of the exact inductive biases or side information that are available during the real-world application, which has been proved to be necessary (Hyvärinen and Pajunen, 1999; Locatello et al., 2019), the empirical success of these methods sheds light on the possibility of identification in the general settings considered in this work.
Setup. For settings with the auxiliary variable u, u is always available during estimation and we consider the dataset as D= = {xx!1, _()) ,.... (x(x), {. where N is the sample size and (i) the value of u (or class label) corresponding to the data point x(i), Given the estimated model f parameterized by 0, similar to (Sorrenson et al., 2020), we consider a regularized maximuum-likelihnn approach for the required sparsity regularization during estimation with the objective function as: [())= = E(x.))eD [log Pp-1 (x u) - AR). where X E [0, 1] is a regularization parameter and R is the regularization term on the Jacobian of the estimated mixing function. i.e., Jy. Based on our experimen- tal results (Fig, 8 in Appx. B.2), we adopt the minimax concave penalty (MCP) (Zhang, 2010) as the regularization term. For settings without the auxiliary variable, we remove the access of u and follow the same objective function in (Zheng et al., 2022). We train General Incompressible- (GIN) (Sorrenson et al., 2020), which is a flow-based generative model, to maximize the objective function (()). Following (Sorrenson et al., 2020), where necessary, we concatenate the latent sources with independent Gaussian noises to meet the dimensionality requirements. All results are from 20 trials with random seeds. Additional details of the experimental setup are included in Appx. B.
Network
Ablation study. We perform an ablation study to verify the necessity of the proposed assumptions. Specifically, we focus on the following models corresponding to different assumptions: (UCSS) The assumption of Structural Sparsity, as well as other assumptions in the undercomplete case (Thm. 3.1), are satisfied; (Mixed) The assumption of Structural Sparsity with undercompleteness and the required dependence structure among sources influenced by the auxiliary variable, as well as other assumptions in the partial sparsity and dependence case (Thm. 4.4), are satisfied; (Base) The vanilla baseline in the undercomplete case, where the assumption of Structural Sparsity is not satisfied compared to UCSS. The datasets are generated according to the required assumptions, the details of which are included in Appx. B. All experiments are conducted in the undercomplete case, where the number of observed variables is twice the number of sources. For datasets that contain both sources in sı and sp ixed case), we set half s and the other half as sp, and the minimum required
8

---

Model UCSS
Nodel - Base
Model - Mixed
Model Base
0.6
9.6
0.2
30
10
Figure 2: MCC of UCSS w.r.t. different num- ber of sources.
Figure MCC of Mixed w.r.t different num- ber of sources.
100%
100%
80%
80%
Percentage
40%
4.5%
0%
min
Number of sources
Figure Percentage of random structures sat- isfying Structural Sparsity w.r.t. different de- gree of undercompleteness (i.e., m/n).
Figure 5: Percentage of sources satisfying Structural Sparsity w.r.t. different numbers of sources in the bijective setting (m/n 1).
numbers of required distinet values have been assigned to the auxiliary variable u. Following previous works (Hyvärinen and Morioka, 2016; Lachapelle et al., 2022), we use the mean correlation coefficient (MCC) between the true sources and the estimated ones as the evaluation metric.
Results for each model are summarised in Fig. 2 and Fig. 3. It can be observed that when the proposed assumptions are met (UCSS and Mixed), our models achieve higher MCCs than Base, This indicates that it is indeed possible to identify sources from nonlinear mixtures to trivial indeterminacy in the general settings with undercompleteness. partial sparsity, and partial source dependence. Additionally, we conduct experiments with different numbers of sources to evaluate the stability of the identification. Our results show that both models consistently outperform Base across all values of n, further supporting the theoretical claims.
Undercomplete Structural Sparsity. As previously discussed, the assumption of Structural Sparsity (Assumption in Thm. 3.1) is far more plausible in an undercomplete setting considered in our theory (i.e., the number of observed variables m is larger than the number of sources n) than in the more restrictive bijective scenario required in (Zheng et al., 2022) (i.c., the numbers are equal, m n)). Consequently, extending the identifiability with structural sparsity from bijective to an undercomplete setting significantly broadens its applicability in real-world contexts. In order to validate the necessity of the proposed generalization empirically, we construct several experiments studying the Structural Sparsity assumption in the undercomplete case. We consider different numbers of sources with different degrees of undercompletennss (m/n, where m the number of observed variables). For each setting, we generate 50 random matrices where each entry is independently determined with an equal probability to either zero or non-zero. The results of the percentages of matrices satisfying the assumption of Structural Sparsity are presented in Fig. 4. We could observe that there exists a significant gap on the percentages between the cases where m/n = 1, ie.. the bijective setting, and the undercomplete settings where m/n 1. Thus, it is clear that the assumption is much more likely to hold true when we have more observed variables than sources. Furthermore, when the degree of undercompleteness increases, the percentage of cases satisfying structural converges to 1. This further suggests that the assumption will almost always hold with a sufficient degree of undercompleness, which is rather common in practice. For instance, photo can easily have millions of pixels (observed variables) but only a dozen of hidden concepts (sources).
Partial Structural Sparsity. Moreover, as previously noted, it is not uncommon for Structural Sparsity to be violated for a subset of sources. For instance, certain sources (such as high-decibel sound sources) may exert influence over all observed variables (microphones). Nonetheless, the

---

Figure 6: Results on Triangles. The rows may correspond rotation, height, width, and brightness, respectively.
Figure 7: Results on EMNIST. The rows may correspond line thickness, angle, upper width, and height, respectively.
prior study (Zheng et al., 2022) necessitates that the sparsity assumption holds true for all sources, providing no identifiability assurance in cases of any degree of violation. To confront this practical obstacle, we propose Thm. 4.1 and Thm. 4.2 to demonstrate that the remaining sources (i.e., nı sources) can still be identified even when the sparsity assumption does not universally hold for some sources. These results can also be motivated empirically. For instance, from Fig. 4, one may find that Structural Sparsity does not likely to hold for all sources when m/nn 1, which is the bijective setting considered in (Zheng et al., 2022). However, as discussed above, if subset of sources satisfies the assumption, at least the identifiability for these sources could be guaranteed by our proposed theorems (Thm. 4.1 and Thm. 4.2) under certain conditions. To illustrate this, we conduct experiments in the bijective setting (m/n = 1) and report the percentage of sources satisfying Structural Sparsity in Fig. 4. We consider datasets with different number of sources and generate 50 random matrices for each of these. Each entry is independently determined with an equal probability to be either zero or non-zero. Combining results from both Fig. 4 and Fig. 5, we observe that, even in scenarios where Structural Sparsity is rarely satisfied for all sources (m/n = 1 in Fig. 4), it is almost always satisfied for a significant fraction of sources (Fig. 5). Consequently, our generalization also proves helpful even within the confines of the earlier bijective setting.
Image datasets. To study how reasonable the proposed theories are w.r.t. the practical generating process of observational data in complex scenarios, we conduct experiments on "Triangles" (Yang et al., 2022) and EMNIST (Cohen et al., 2017) datasets. The "Triangles" dataset consists of 60, 000 synthetic 28 x 28 images of triangles, which are generated from 4 factors: rotation, height, width, and brightness. By fixing the number of pixels (observed variables) and generating factors (sources), generated according to undercomplete process, although the
can guarantee that the images exact generating process is still unknown (c.g., a pixel could be (indirectly) influenced by multiple factors in a complicated way). For the weal-wolld dataset, EMNIST contains 240, 000 28 x 28 images of handwritten digits and is a larger version of the classical MNIST dataset. Although we do not know the exact number of sources, it is highly possible that it is smaller than the number of pixels (784). We present the identified sources with the top four standard deviations (SDs) from both datasets in Fig. 6 and Fig. 7. In both figures, each row represents source identified by our model, with it varying from -4 to +44 SDs to illustrate its influence. The rightmost column is a heat map given by the absolute pixel difference between -1 and +1 SDs. By observing the identified sources with the top four standard deviations, one could find that it is possible to identify semantically meaningful attributes from practical image datasets, which further suggests the potential of our theory in real-world scenarios. Additional results are available in Appx. B.2.
6 Conclusion
We establish of new identifiability results of nonlinear ICA in general settings with undercom- pleteness, partial sparsity and source dependence, and flexible grouping structures, thereby extending the identifiabilty theory
wide range of real-world scenarios. Specifically, we prove the identi- fiability when there are more observed variables than underlying sources, and when sparsity and/or independence are not met for a subset of sources. Moreover, by leveraging various dependence struc- tures among sources, further identifiability guarantees can also be obtained. Theoretical results have been validated through a combination of extensive previous studies and our own experiments, which involve both synthetic and real-world datasets. Future work includes adopting the theoretical frame- work for related tasks, such as disentanglement, transfer learning, and causal discovery. Furthermore, the proposed identifiability guarantees on generalized latent variable models bolster our confidence in uncovering hidden truths across diverse real-world settings in scientific discovery. We have only ex- plored the visual disentanglement task, and the lack of other applications is a limitation of this work.
10

---

Acknowledgements
We are grateful to everyone involved in the anonymous reviewing process for their insightful feedback. This project is partially supported by NSF Grant 2229881, the National Institutes of Health (NIH) under Contract ROIHL159805, grant from Apple Inc., grant from KDDI Research Inc., and generous gifts from Salesforce Inc., Microsoft Research, and Amazon Research.
References
L. Ardizzone, T. Bungert, F. Draxler, U. Köthe, J. Kruse, R. Schmier, and P. Sorrenson. Framework for Easily Invertible Architectures (FrEIA), 2018-2022. URL https: /ttp://ggtttt/tt/// cwwccooo//i//ceee /iia/vsea FrEIA.
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.
S. Buchholz, M. Besserve, and B. Schölkopf. Function classes for identifiable nonlinear independent component analysis. arXiv preprint arXiv:2208. 06406, 2022.
C. Burgess, Higgins, A. Pal, L. Matthey, N. Watters, G. Desjardins, and A. Lerchner. Under- standing disentangling in Deta-VAE. Workshop Learning Disentangled Representations the 31st Conference on Neural Information Processing Systems, 2018.
M.-. Carbonneau, J. Zaidi, J. Boilard, and G. Gagnon. Measuring disentanglement: A review of metrics. IEEE Transactions on Neural Networks and Learning Systems, 2022.
J.-F. Cardoso. Multidimensional independent component analysis. In Proceedings the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP'98 (Cat. No. 98CH33181), volume pages 1941-1944. IEEE, 1998.
R. T. Chen, Li, B. Grosse, and D. K. Duvenaud. Isolating sources of disentanglement in variational autoencoders. Advances in neural information processing systems, 31, 2018.
G. Cohen, S. Afshar, J. Tapson, and A. Van Schaik. Emnist: Extending mnist to handwritten letters. In 2017 international joint conference on neural networks (IJCNN), pages 2921-2926. IEEE, 2017.
Comon. Independent component analysis, a new concept? Signal processing, 36(3):287-314, 1994.
S. Duan, L. Matthey, A. Saraiva, N. Watters, C. Burgess, A. Lerehner, and I. Higgins. Unsupervised model selection for variational disentangled representation learning. In ICLR, 2020.
F. Falck, H. Zhang, M. Willetts, G. Nicholson, C. Yau, and C. C. Holmes. Multi-facet clustering variational autoencoders. Advances in Neural Information Processing Systems, 34:8676-8690, 2021.
J. Fan and R. Li. Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American statistical Association, 96(456): 2001.
H. Hälvä, S. Le Corff, L. Lehéricy, So, Zhu, E. Gassiat, and A. Hyvärinen. Disentangling identifiable features from noisy data with structured nonlinear ICA. Advances in Neural Information Processing Systems, 34, 2021.
A. Hyvärinen and P. Hoyer. Emergence of and shift-invariant features by decomposition of natural images into independent feature subspaces. Neural computation, 12(7): 7000)17057700 2000.
A. Hyvärinen and H. Morioka. Unsupervised feature extraction by time-contrastive learning and nonlinear ICA. Advances in Neural Information Processing Systems, 29:3765-3773, 2016.
A. Hyvärinen and H. Morioka. Nonlinear ICA of temporally dependent stationary sources. In International Conference on Artificial Intelligence and Statistics, pages 460 469. PMLR, 2017.
A. Hyvärinen and P. Pajunen. Nonlinear independent component analysis: Existence and uniqueness results. Neural networks, 12(3))429-4333 1999.

---

A. Hyvärinen, H. Sasaki, and R. Turner. Nonlinear ICA using auxiliary variables and generalized contrastive learning. In International Conference on Artificial Intelligence and Statistics, pages 859-868. PMLR, 2019.
1. Khemakhem, D. Kingma, R. Monti, and A. Hyvärinen. Variational autoencoders and nonlinear ICA: A unifying framework. In International Conference on Artificial Intelligence and Statistics, pages 2207-2211 PMLR, 2020a.
I. Khemakhem, Monti, D. Kingma, and A. Hyvarinen. Ice-beem: Identifiable conditional energy- based deep models based on nonlinear ica. Advances in Neural Information Processing Systems, 33:12768 12778. 2020b.
D. P. Kingma and P. Dhariwal. Glow: Generative flow with invertible 1x1 convolutions. Advances in neural information processing systems, 31, 2018.
B. Kivva, G. Rajendran, P. Ravikumar, and B. Aragam. Identifiability of deep generative models without auxiliary information. Advances in Neural Information Processing Systems, 35:15687- 15701, 2022.
Klys, J. Snell, and R. Zemel. Learning latent subspaces in variational autoencoders, Advances in neural information processing systems, 31, 2018.
L. Kong. S. Xic, W. Yao, Y. Zheng, G. Chen, P. Stojanov, V. Akinwande, and K. Zhang. Partial disentanglement for domain adaptation. In International Conference on Machine Learning, pages 11455-11472 PMLR, 2022.
A. Kumar, P. Sattigeri, and A. Balakrishnan. Variational inference of disentangled latent concepts from unlabeled observations. arXiv preprint arXiv:1711.00845, 2017.
S. Lachapelle and S. Lacoste-Julien. Partial disentanglement via mechanism sparsity. In UAI 2022 Workshop on Causal Representation Learning, 2022.
S. 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.
F. Locatello, D. Vincent, I. Tolstikhin, G. Rätsch, S. Gelly, and B. Schölkopf. Competitive training of mixtures of independent deep generative models. arXiv preprint arXiv:1804.1 130, 2018.
Locatello, S. Bauer, M. Lucic, G. Raetsch, S. Gelly, B. Schölkopf, and O. Bachem. Challenging common assumptions in the unsupervised learning of disentangled representations. In international conference on machine learning, pages 41 4114-4124, PMLR, 2019.
P.-L. Loh and M. J. Wainwright. Support recovery without incoherence: A case for nonconvex regularization. The Annals of Statistics, 25())22455-2482 2017.
G. Monge. Applications de l'analyse géométrie, 1850.
Ravikumar, G. Raskutti, M. Wainwright, and B. Yu. Model selection in Gaussian graphical models: High-dimensional consistency of reegullrre MLE. In Advances in Neural Information Processing Systems, 2008.
P. Ravikumar, M. J. Wainwright, G. Raskutti, and B. Yu. High-dimensional covariance estimation by minimizing & -peealizee determiint divergence. Electronic Journal of Statistics, 5:935 -800, 2011.
P. Rubenstein, B. Schölkopf, and I. Tolstikhin. Learning disentangled representations with wasserstein auto-encoders. In 6th International Conference on Learning Representations (ICLR 2018), 2018.
P. Sorrenson, C. Rother, and U. Köthe. Disentanglement by nonlinear ICA with general incompressible-flov networks (GIN). arXiv preprint arXiv:2001.0488 2020.
A. Taleb and C. Jutten. Source separation in post-nonlinear mixtures. IEEE Transactions on signal Processing, -7(10):2877-2800 1999.
12

---

F. Theis. Towards general independent subspace analysis. Advances in Neural Information Processing Systems, 19, 2006.
Von Kügelgen, Y. Sharma, L. Gresele, W. Brendel, B. Schölkopf, M. Besserve, and F. Locatello. Self-supervised learning with data augmentations provably isolates content from style. Advances in neural information processing systems, 34:16451-16467, 2021.
M. J. Wainwright. Sharp thresholds for high-dimensional and noisy sparsity recovery using é constrained quadratic programming (Lasso). IEEE Transactions Information Theory, 55(5): 2183-2202, 2009.
X. Yang, Y. Wang. J. Sun, X. Zhang, S. Zhang, Z. Li, and J. Yan. Nonlinear ICA using volume- preserving transformations. International Conference Learning Representations, 2022.
W. Yao, Sun, A. Ho, Sun, and K. Zhang. Learning temporally causal latent processes from general temporal data. arXiv preprint arXiv:2110.054420 2021.
W. Yao. G. Chen, and K. Zhang. Temporally disentangled representation learning. In Advances in Neural Information Processing Systems, 2022.
C.-H. Zhang. Nearly unbiased variable selection under minimax concave penalty. The Annals of Statistics, 3842)899-994,, 2010.
Y. Zheng, I. Ng, and K. Zhang. On the identifiability of nonlinear ICA: Sparsity and beyond. In Advances in Neural Information Processing Systems, 2022.
13

---

Appendix
Table of Contents
A Proofs
14
A.1 Proof of Theorem 3.1
14
A.2 Proof of Theorem 4.1
16
A.3 Proof of Theorem 4.2
17
A.4 Proof of Theorem 4.3
20
A.5 Proof of Theorem 4.4
23
B Experiments
28
B.I Supplementary experimental settings
28
B.2 Supplementary experimental results
29
A Proofs
A.1 Proof of Theorem 3.1
Theorem 3.1. Let the observed data be large enough sample generated by an undercomplete
nonlinear ICA model as defined in Eqs. (1) and (2). Suppose the following assumptions hold:
For each 1 fI....,mh. there exist 1 and a matrix T
E
T s.f.
span(Jr(s()) )i: R7, and [Jr(s(0yT], ER. F.
it. (Structural Sparsity) For each E (I,...,n), there exists Cj s.t. Niecs Fs.: = [k.). Then 8 is identifiable to an element-wise invertible transformation and permutation. Proof. Let h - å denotes the transformation between the true sources and estimated sources. We can apply the chain rule repeatedly get:
Jr(s) J ioh (s) = [s)
(6)
Since J3 (s) and Js(s) both possess full column rank, (s) should have non-zero determinant. From this, we can deduce by incorporating the inverse of h:
J5($) Jr(s)
Our objective here to demonstrate that the function h is a composition of permutation and a component-wise invertible transformation. Let D(s) denote a diagonal matrix and P denote permutation matrix, our goal can be rewritten demonstrating that Jn(s)-1 D(s) This leads us demonstrate that:
J₂(5) (ss)
Further, can express:
= J((s)s)
(9)
where T(s) E Roxn is square matrix. Here, we define F as the support of Jr(s), f as the support of J and as a set matrices with the same support of T(s). Furthermore, with the same support as T(s). Based on Assumption i, we have:
matrix
spsn(Jr(s()))
R
(10)
14

---

Given that the set (Jr(s(0), )t: Feel forms basis of x we can express any vector in this space linear combination of these basis vectors. In particular, for any jo Fa.s the one-hot vector ejo E Ry, can be written as
Je:
Cjo =
Σ EEFL.
anJr(s
(11)
where oy denotes the respective coefficient.
With this in mind, we can find the transformation of 6 under T as
Jo.: Ejo T
Σ onJr(s(())..T)
(12)
EEF.
According to Assumption i, each term in the above summation belongs to the space R A. Jo. itself resides in F,,"" i... Too E R
Therefore,
Thus
Fe..
Vj VjE
Ty E
(13)
Then the connections between these supports be established according Defn. 2.3
v(i.j) E F, {i} T F.
(14)
It is noteworthy that a similar strategy to derive Eq. 14 has been applied in (Zheng et al., 2022) and part of the proof technique is inspired by that work. In contrast the proof by Zheng al. (2022), which assumes the invertibility of f, we only necessitate its injectivity. This distinction allows for the inclusion of undercomplete cases.
Since ())) and Jj ()((()) have full column rank T(s()) must have a non-zero determinant. Otherwise, it would follow that the rank of T(s(0) is less than n, which would imply contradiction that J (5(0) = Jr
has column rank less than n. Representing the determinant of the
matrix ((s(F) its Leibniz formula yields
(ct(T(s(()))
Σ sgn(o)
((s
T(s
Diots)
# 0,
(15)
rES,
where Sn, is the of n-permutations. Thus, there is at least term in the that non-zero, i.e.,
n
Eo Sn, Vi E (L....,, n), sgn(o) II (T )..(1)) # 0.
(16)
which is equivalent to Then we can conclude that this a is in the support of ((s) since s()) E s. Therefore, follows that
Eo Sn, Vi E (1,....,n), T T(s 0.
(17)
Vj E (1....,n).
n), a(j) T,.-
(18)
Together with Eq. (14), we have
V(i.j) E (i,o((() E (i) x T3 C
(19)
Denote
o(F) = ((1,0())) (i,j) E F}.
(20)
Then have
o(F) f
(21)
Because of the sparsity regularization on the estimated Jacobian, we further have
=
(22)
Combining this with Eq. (21), we derive
a(F)= =.
(23)
15

---

Suppose T(s) * D(s)P, then
3i1 # j2. Tis n T22: # 0.
(24)
Additionally, consider is [I,..., n for which
o(js) E Th 0 TT..:.
(25)
Since ji + j2, we can assume j3 + ji without loss of generality. A similar strategy has been used
previously in (Lachapelle al., 2022; Zheng al., 2022). Based on Assumption ii, there exists
Cj ? ji such that Nee,, Fi,: {i Because
js Φ {11}
M Fi. iEC;1
(26)
there must exists in Cj such that
ja E Fig.:- Since ji E Fig.: it follows that (13, E F. Therefore, according to Eq. (14), we have
(27)
{is} Tis C F.
(28)
Notice that (js) E The O Tia implies
(1s) E {is} x Th
(29)
Then by Eqs. (28) and (29), we have
(ig, 0 (js)) F.
(30)
This further implies (i3, E by Eq. (20) and (23), which contradicts Eq. (27). Therefore,
have proven by contradiction that T(s) = P. By replacing T(s) with Dss) P in Eq. (9), we obtain Eq. (8), which is the goal.
A.2 Proof of Theorem 4.1
Theorem 4.1. Let the observed data be large enough sample generated by an undercomplete nonlinear ICA model defined in Eqs. (2) and (3). Suppose the following assumptions hold:
There exist nn + 1 distinct values of u. i.e., uj with j E 1,.1...., n s.t. the un vectors w(sp, u. with (ni + I,.... n) are linearly independent, where vector w(sD, u, i) defined as follows:
w(sD, u, a (logp(sp/uu) log(p(sn)ingg (o))
a (logp(sn) ump) - log(p(sn)ung un)))
Os;
0s:
ii. There exist u1, U2 E s.t., for any set Ag C S with non-zero probability measure and cannot be expressed as Ba, sp for any Bai C S1, we have
[ Ps/u (s un) ds #
/ Patu (s u2) ds.
JEEA
A
Then sp is identifiable up to an subspace-wise invertible transformation.
Proof. Let h + å denotes the transformation between the true and estimated sources. By using chain rule repeatedly, we have
Jr(s) Jioh (s)
(31)
= Js
Since (s) and Js(s) both possess full column rank, (s) should have non-zero determinant. Thus, (s) must be invertible and have non-zero determinant. Otherwise, one of them would not be of full column rank, which leads to a contradiction.
Applying the change of variable rule, we have
(slu() det (S)) (s(u)
(32)
16

---

Taking the logarithm on both sides yields
log Psju (s) u) log ( log Paju ($)
(33)
Note that according to the model defined in Eqs. (2) and (3), the joint densities can be factorized as
(s/u) Paplu(Sp|u)
(s:),
x=1
(34)
Psju(S - (Splu( II
Ps. (8.).
1=1
Then we define the difference across domains follows
(s. u,) log Pxju Ps) log (s)n
(35)
By taking the difference on both sides of Eq. (33) corresponding to ny and ug, we obtain
( uy) ( uy),
(36)
where, for (I...., n, logps ($. and log Paju (8i |u;) have been canceled because sources Sy are not dependent on uy. That is, ( uy) i E {l....,mI}
Taking the derivatives of both sides of Eq. (36) w.r.t. & where E {l...., n2 we have
@q($p, Uz)
@g(Ss, u,) 0s:
Σ
(37)
0&k
Os; 05k
i-
Clearly, LHS of Eq. (37) equals zero. By considering each j E {1,..., np. for uj we have n. equations like Eq. (37), which constitute linear system with up n coefficient matrix.
According to the assumption, solution of Eq. (37) 85g
coefficient matrix of the linear system has full rank. Thus, the only 0s. for E {mr + ......n) and & E [I,...,n7}.
As -(-) is smooth, its Jacobian can be written as:
A
Ös
B
8s1
J i (S)
0S
08
(38)
C
dan
D
05
05
05 = 0 for E {nz + 1, 1.....,1I n} and & E {1....,,y, n. entries in the submatrix must all Since 88g be zero. Thus, the submatrix D must be invertible, otherwise (S) will not be invertible, which contradiction. Besides, based Assumption ii, can show that all entries in the submatrix B are zero according to part of the proof of Theorem 4.2 in (Kong et al., 2022) (Steps 1, 2, and 3). Therefore, &p is an invertible transformation of sp.
A.3 Proof of Theorem 4.2
Theorem 4.2. In addition to assumptions in Thm. 4.1, suppose the following assumptions hold:
For each i E A....,,I.. there exist {s(0) Fe,yl (pan(Jr(s( )t.m))))) |Funny Bay =Rey Fring and
and a matrix T E T s.f.
===1
T Framy'
i. (Structural Sparsity) For all k (l,...,n1}, there exists Cp s.t. Niec, Frany [k]. Then S1 is identifiable up element-wise invertible transformation and a permutation.
Proof. Our goal here is show that $ is composition of permutation and component-wise invertible transformation sources in 8₁. By using chain rule repeatedly, we have
J (s(
J Joh-- (8)
(h JB)) (s)
(39)
= Js ( (6).
17

---

As h (() is smooth, its Jacobian can be written as:
A == B :=
I
0s1
J ( =
Øs r
06n p
(40)
C
ds
D
08
dB
In the proof of Thm. 4.1, we have shown that all entries in the submatrix C are Then we have
(s( kong
1
(41)
JF(s) J Jh-1 (8)mn
where Eq. (+) is directly from the result that all entries in C, i.e., those Jn, (f)) are zero.
Moreover, in the proof of Thm. 4.1, we have also shown that all entries in the submatrix B are zero. Let (ss) represent diagonal matrix and P represent permutation matrix. Thus, our goal is equivalent to show that Jn, (n)s)),y
(s) or Jn (8) = Jn (6) Jn Jn( Dr(s)) Then we need prove that
Jp(S)
Dr(s) P
(42)
Additionally, we have
(s)).., = Jr(()..n; T(s),
(43)
where T(s) E Knz is a square matrix. Note that we have denoted as the support of Jr(s), F
the support of ($) and T as the support of T(s). Besides, we have also denoted T matrix with the same support of T. According to Assumption i, we have
span (i
F Ft=1
Ry R
(44)
Since (Jr(s(()) ), Fiayyl forms basis of R R for any jo Fa,my are able rewrite the ===1 ny
one-hot vector 6 E
Fiang
as
Cjo
Σ
anJr(s())snnr
(45)
EEF
where og is the corresponding coefficient. Then
Jo. = Ejo T
Σ acJr(s(
)
(46)
FEFi.ny
According to Assumption i, each term in the above summation belongs to the space Ray Ju: itself resides in Ryy Pr i..., To..:
Therefore,
By
Thus
Vj F Fieny
T3. E By Piinz
(47)
Then the connections between these supports can be established according to Defn. 2.3
V(i.j Feanyy (1) TG F.any-
(48)
J.nny have full column rank ny, T(s()) must have non-zero deter- minant. Otherwise, it would follow that the rank of (s)()) is less than ny, which would imply contradiction that J (S()) )o.my (r(s()).... ((s(9) has a column rank less than nt.
Since (F) and JØ (s() )
The determinant of the matrix (e)( be represented its Leibniz formula
n (g II
det det(T(s(()) = Σ
T(s (1,0()) ()))))) # 0.
(49)
DES,
1=1
18

---

where Say is the set of peypprmuttatons. Therefore, there is at least one term in the sum that is non-zero, i.e.,
dr
Fo Sap Vi E (I,...,,i)) nr), sgn(a) II
T ( )1,0 #0,
)1,00)
(50)
which is equivalent to
Fo E Snys Vi E (I,...,mr}
T(s(") (o())) # 0.
(51)
Then we can conclude that this a must present in the support of T(s) since s E Therefore, follows that
Vj (l.....,ulk ni) o(1) T, Together with Eq. (48), we have
(52)
(i.j) Fam (i,o(1) E {i) x Taa F
(53)
Denote
aFF,,,)) = ((i,o(()) (1,5) E F.
(54)
Then have
a(F..r)) F. Because of the sparsity regularization on the estimated Jacobian, we further have
(55)
|F S |r,mml = =lo(Fummz)l
(56)
Combined with Eq. (55), we have
(FF..ni) F.
(57)
Suppose T(s) + (P, then
3/1 + j2, THs n Tias + #.
(58)
Additionally, consider is [l.....nj for which
ajja) E Ty TTp2.
(59)
Since J1 * 12. assume ja * Ji without loss of generality. Based on Assumption ii, there
exists Cj 3 ji such that Niec, Fi,m, {. Because
js E {ii) = n Fi.nry
(60)
iECn
there must exists ia Cj such that
ja & F Fig.ay-
(61)
Since f1 E Fig,ay, follows that (1a.11) E F. Therefore, according to Eq. (48), we have
{is} x The C F
(62)
Notice that (jjs) E Typ n Taa implies
(is, (ia) E (is) x Th.
(63)
Then by Eqs. (62) and (63), we have
(is, o(a)) E F.m.-
(64)
This further implies (is. ja) Feony by Eqs. (54) and (57), which contradicts Eq. (61). Thus,
have proven by contradiction that T(s) = (y(s))1pp 'p,- -1 By replacing T(s) with Dy -pp, in Eq. (43), obtain Eq. (42), which is the goal.
19

---

A.4 Proof of Theorem 4.3
Theorem 4.3. Let the observed data be a large enough sample generated from an undercomplete
nonlinear ICA model as defined in Eqs. (2) and (4). Suppose the following assumptions hold:
For each i E {I...., n1). there exist {s! |Frmmey
)t=1
and a matrix T E TET s.l.
span)Jr(s(")). |FFammp F Fi,m, and [Jr(s! b,12
Fuamy
ii There exist 2nD + 1 values of i.e. u, with i E {O.1,.... 2nD}. the 2nD vectors w(SD, u,) - w(SD, un) with i E {I,..., 2np} are linearly independent, where vector w(sp, u,) is defined as follows:
w(SD. u:)
(v(Se) (.), TM V(Sca u,), v (Se) u:). " v ('Saa u:)),
where
v(Sey u:) - 0 log p(se, u.)
Olog lu:)
Us,,cas
8 log p(S [u)
8 pls, lu:)
v' Vseee u:)
(85e,10)
(Ds,,a,))
ii. There exist u1, U2 u, s.l., for any set As C 8 with nonzero probubility measure and cannol be expressed as Bay SD for any Baj C S1, we have
[
Ps|u (s U1) ds
Palu (s (22) ds.
JEAA.
BEAA
iv. (Structural Sparsity) For all ie (1,....n1]; there exists Cg s.t. Niec. Fi,m, {k}.
Then is identifiable up an element-vi invertible transformation and permutation, and sp is identifiable up to a subspace-wise invertible transformation and subspace-wise permutation.
Proof. Let h + & denotes the transformation between the true and estimated sources. By using chain rule repeatedly, we have
Jr(s) = J Jjch (s)
(65)
Because (S) and Js(s) have full column rank, (s) must be invertible and have non-zero determinant. Otherwise, one them would not of full column rank, which leads to a contradiction.
Applying the change of variable rule, we have
(s|u() det(( = (s(u))
(66)
Taking the logarithm both sides yields
lo (s u) + log (et = log Paju (S
(67)
Note that according to the model defined in Eqs. (2) and (3), the joint densities can be factorized as
(s|u) Ps. (8:)
II Ps, (s)lu), j=c1
1=1
(68)
cd
Pa (S
Ps. (8:) II
Pa (S)
j=c
Together with Eq. (67), we have
log Ps, (s:) +
log Ps i (sylu) + log det(Jn- (s))]
f=c1
(69)
ea
log Pa: (6:) +
log Psy (s)
20

---

Therefore, for u U....., unn- we have 2nd + 1 such equations. Subtracting each equation corresponding to u...... Unnp with the equation corresponding to u, results in p equations:
(log Ps.lu; (st u3) log Ps,/uo (s; Un))
(70)
Ps. (S: u,) - Ps:luo (8: un))
Then we take the derivatives of both sides of Eq. (70) w.r.t S3 and 6, where k; v E {I....,Ti n. and + v. Besides, both >> nı and v > ny, then they are not indices of the same subspace. clear that the RHS of Eq. (70) equals to zero. For the i-th term of the summation the LHS, we have the following equation after taking the derivatives:
88 log Psi uy (s:lu,)
8 log Ps. ( (S:|ub)
Ost ast
(dsi)²
(8si)²
08 0s,
I=
(71)
① log Ps.lu, (s Uy)
d log Ps, Im (s; uo)
8d 81
ds:
Os:
Osg
where i and én corresponds the minimum and maximum indices of elements in s; = (8i ..... 8%,)) By iterating from e1 to Cd, we are also iterating I from ns + to Thus by considering all those equations as well iterating j in u, from 0 to 2np, we have linear system with a 2np 2nD coefficient matrix.
Then, according to Assumption ii, the coefficient matrix of the linear system has full rank. Thus, the only solution Eq. (71) is dai ds
8 at dšg 83, = 0 and 0820
Note that & * v and, if both > n, and v ny, they are indices of sources in the same subspace. Besides, 0si dsc 8ät 88.
indicates that is impossible for both del and dsi be non-zero. 85..
Furthermore, because h is invertible, they cannot be both zero, indicating that it is either ds. = 0 28
d5. = 0), then k & (l...., n.). Otherwise, 51 will also be invariant, which a contradiction. Therefore, & can only be the index of estimated source from one independent subspace, which, together with an invertible subspace-wiss
or dh.
ds: 0. Then, because 8, has invariant distribution w.r.. u, if ds: + 0 (i.e., ds. J5t
the invertibility, leads to the conclusion that sp is a composition transformation and a subspace- wise permutation of sp. So it is the mapping from åp sp since the subspace-win wise transformation is invertible and the inverse of a block-wise permutation matrix is still block-wise invertible matrix.
Now we have shown the identifiability result for sp = (8 8n), then we need to show that for the remaining sources (51)
By using chain rule repeatedly, we have
J₃(S) Jr
Jr (()) (s)
(72)
= Jn
Since have shown that, for every E (nz + 1,..., m) and (I,...,,1), of J J (5) must be zero.
Bsc Dsg
0. all entries
Then we have
J₁(8) k,ny
= Jr(s)Jn (8)
(73)
Jr(s) Jn-1 (8)my,...
where Eq. (+) is directly from the result that all entries in Jn (8) tit,n are zero.
Based on the proof of Theorem 4.2 Kong al. (2022) and Assumption iii, particularly, steps 1, and 3, one can show that šy does not depend on sp. Let D(s) represents diagonal matrix and P
21

---

represent a permutation matrix. Thus, our goal is equivalent to show that (s = PyDy(s)
Jn (S) Jn- (a) (h((s) (i)
(P) Then need to prove that
( Jr(s).. Dr(s) PP
(74)
Additionally, we have
J (8) = (s())..n; T(s),
(75)
where T(s) Ru is square matrix. Note that have denoted F as the support of Jr Jr(s). F as the support of (S) and T as the support of T(s). Besides, we have also denoted T as matrix with the same support of T. According to Assumption i, we have
span (Jr(s( )t.0x
Pe M6=1
(76)
Since (Jr(s()) ) Fuanpl forms a basis of Ry Ry, for any jo Firmy, are able to rewrite the ft-1 my as
one-hot vector 6 Fiany
Ejo
E
anJr(s())imm
(77)
EEFLen
where og is the corresponding coefficient. Then
T Jo.: = =e c
acJr(s!)) )aony T Fipmy
(78)
where the final "E" follows from Assumption that each element in the summation belongs to Rd Thus
Fiiin
Vj Fiany T3
R Fesez
(79)
Then the connections between these supports can be established according to Defn. 2.3
v(i.j) F.azzy {i} Ta F F.,anz
(80)
Since Jr(s(()...n and (s(s()) )..m, have full column rank nt,, T(s(0) must have a non-zero deter- minant. Otherwise, it would follow that the rank of ((s is less than ny, which would imply contradiction that J ( = (r(s( T(s(1) has a column rank less than ny.
The determinant of the matrix T(s can be represented as its Leibniz formula as
det ())
sgn (
( )i,0()) (1.00))))))))
* 0,
(81)
DES,,
i=1
where Sny is the set of n, peremuuttaions. Thus, there is at least one non-zero term in the sum, i.e.,
3o Say Vi E (l...., nz). sgn(o) II
T(s (Ts #0,
(82)
which is equivalent
3e E Snys Vi E (I....,mr] m.). (( )o1()) # 0.
(83)
Then we can see that this must present in the support of T(s) since s(0) E It follows that
Vje (1,...,ayh. o(j) E T,.-
(84)
Together with Eq. (80), we have
V(i,j) E Fi (i,o(1) E [i) x Tas C F
(85)
Denote
oFF,.n)) (((ro(i)) (i.j) F.
(86)
22

---

Then we have
o(F..n)) F. Because of the sparsity regularization on the estimated Jacobian, we further have
(87)
|Famm S [ (o(F
(88)
Together with Eq. (87), we have
(FF.,ng) Fipmm.
(89)
Suppose T(s) * ()(s) P,- then
Ejj # 82, Tni n TTaa: 7 0. Additionally, consider js E fl,.... , for which
(90)
o(js) E Th T2..:
(91)
Since j1 # f2, we can assume js # j1 without loss of generality. Based on Assumption iv, there
exists Cj Ji such that NkEc,, Fi,m; [. Because
ja E {11} = n Fs
(92)
iECn
there must exists ig E Cj such that Since ji E Fig.ny we have (13. E F. Therefore, according to Eq. (80), we have
ja & Figiiy.
(93)
(is) x The F
(94)
Notice that (js) Th O Tja implies
(is) E {is} x T
(95)
Then by Eqs. (94) and (95), we have
(is, ((f)) E F.
(96)
which implies (ia:fa) E Fiamy by Eqs. (86) and (89), therefore contradicting Eq. (93). Thus, we have proven by contradiction that T(s) = Dy(s) - -1 By replacing T(s) with Dy(s) -',, in Eq. (75), we obtain Eq. (74), which the goal.
Therefore, 8, is identifiable up to a composition of a component-wise invertible transformation and a permutation, and sp identifiable up to composition of a subspace-wise invertible transformation and subspace-wise permutation.
A.5 Proof of Theorem 4.4
Theorem 4.4. Let the observed data be large enough sample generated from undercomplete nonlinear ICA model as defined Eqs. (2) and (5), suppose the following assumptions hold:
For each i {1....,RIk, nI}, there exist { Fainll (p 1e=1
and matrix T T S.I.
|Fr.mr Ry BTi.., and [Jr [s ioog CR. F.,m.
it. There exist 2np + 1 values of u, i.e. u, with i E w(sp, u,) w(sD, un) with i E 2n..) are linearly independent, where vector w(sp. u) is defined as follows:
2np)..ppp.... s.t. the 2n vectors
w(sD, u:) (v(sD, u:), v'Ds,
where
v(sp, u:) = @llog Pologp(snzt/uu)
a p(sn uU:) Isn
Osnft1
3 log Allog((snntalll u:)
8a log bogp(sn)) ( (Os,)²
v'(sp, u,)
(0sm)+1)²
23

---

ii. There exist U2 E u. s.t., for any set Ag S S with nonzero probability measure and cannot be expressed as Bxj DSpfor for any Bxi St. we have
f
Ps|u (s u1 ds #
Pxlu (s u2) ds.
SEA
A
iv. (Structural Sparsity) For all i (I,...,n1] there exists Cg s.t. Niec. Fi,m, {k}.
Then s is identifiable up to an element-wise invertible transformation and a permutation. Proof. Let h + š denotes the transformation between the true and estimated sources. By using chain rule repeatedly, we have
Jr(s) J foh (s)
(97)
= p (s).
Because (s) and Js(s) have full column rank, (s) must be invertible and have a non-zero determinant. Otherwise, one of them would not be of full column rank, which leads to a contradiction.
Applying the change of variable rule, we have
Ps)u (s|U) det(J,,) (6)) (s(
(98)
Taking the logarithm on both sides yields
Pxju log (et((J,-1(S)) = log Ps (n)
(99)
Note that according to the model defined in Eqs. (2) and (3), the joint densities can be factorized as
12
(s|u())u)=
Ps.
(8:)
II Pe
II Ps. ( (8
f=1 f=n++1
(100)
n2
(S]u(S|u) =
Ps. (8:)
II (B)lu(B)]u)
= II 2=1
Ps (&: (8. u).
i=1
jmny+1
Together with Eq. (99), have
Σ log DogPs./ule (s + log det(J) ( = Σ log Ps, ln (S:lu))
(101)
Then we take the derivatives of both sides of Eq. (101) w.r.t Sa and s, where k, U E {l,..., n) and k f q. For brevity, first define the following terms:
Os;
Magn) =
(102)
0&
82s
(",()..)) ==
(103)
① Olog Ps. (s: [u)
n1(84, u)
(104)
Os:
8² log Ps, i (5:lu) (0s;)² )2
7/ (si, u) =
(105)
Then have
(s), (M0))M,, Ma (ss,, u) -.....)) + 82 log det(J).- (S)) 0.
(106)
asyOs,
Therefore, for u Up ..., Usnps have 2np + 1 such equations. Subtracting each equation corresponding to u1, Ugnn with the equation corresponding to us results in 2n equations:
Σ i=
(1, 1/ (2,, uo)) (a
(107)
+ (1k(z, uz) - (a, uo)) k((ck.))) 0,
(108)
24

---

where j 1.... 2nd. Note that for i E fl...., does not depend on u. Thus, we have (2, u,) = (2, uy) and T/1 u,) (2,, uy), Vj.j'. Hence only sources dependent on (i.e., 8p) remain in Eq. (107).
By considering each j {I,...; 2np) for uj. have 2np equations like Eq. (107), which constitute linear system with a 2np x 2n coefficient matrix.
According Assumption ii, the coefficient matrix of the linear system has full rank. Thus, the only solution of Eq. (107) is R Ra,0)"
and h" (k,,) = for = ne + ly..., n and k, v
(1....,n), * Av.
As h (-) is smooth, its Jacobian be written as:
A
Ōs
B := 051
J In =
Üs
08
(109)
C
Ós n
D := d
0S
Because (1,00) (.))) 0, (1,...,n], n), k + u, for each ny + ,,..., ni, there at most one index fl.....7 n2 s.t. ((((r) * 0. Therefore, there is at most one non-zero entry in each row indexed by = np + .....; n the Jacobian matrix Jn (S). Further, the invertibility of h th1p necessitates Jn to be full-rank which implies that there is exactly one non-zero component in each row of sub-matrices and D.
Suppose that non-zero component lies in the sub-matrix C, then Sp is not dependent on u. Thus, the only non-zero component must lie in D. Because Jn, is of full-rank and C is zero sub-matrix, D must have full rank. Hence, &p must be a composition of a component-wise invertible transformation and a permutation of sp. Moreover, according part of the proof of Theorem 4.2 in Kong al. (2022) (Steps 1, 2, and 3), the submatrix B is zero if Assumption ii holds.
Now have shown that, for the matrix Jn its submatrix D is generalized permutation matrix and both submatrices B and C' are zero-matrices). Because h is smooth and invertible, the sub-matrices of the corresponding positions of Jn have the same properties. Then, need to show the identifiability for the remaining sources S, (s,,..., component-wee wiss invertible transformation of St.
Sn, ). i... $, is permutation with
Let D(s) represents diagonal matrix and P represent a permutation matrix. Thus, our goal is equiv- alent to show that (s),,,,,,,,
my,,n, = (yD)(s) or (s) = Jn- (8) = (n(s) ony =
Dy(s) P -r, By using chain rule repeatedly, we have
J₁(S) = (s)
= Jr(h ( (s)
(110)
Jn
Then we have
J₁(S), kmn
Jr(s)J,, -1) 18))
(111)
Jr(s) .. Jn :m)..
where Eq. (x) is directly from the result that all entries in C, i.c., those in Jn (8) are zero
Therefore our goal is equivalent show that
J²(S).. m Dy (P,
(112)
Additionally, we have
(s) Js(()),,,(((
(113)
where T(s) E X is square matrix. Note that we have denoted as the support of Jr(s), F
as the support of (S) and T as the support of T(s). Besides, we have also denoted T as matrix with the same support of T. According to Assumption i, we have
span [J (1) Ji ) 1=
F R F
(114)
25

---

Since (Jr(s( ), one-hot vector 6o E R as Fiiny
Franl forms a basis of R R for any jo Fi,my- we are able rewrite the
Ejo
Σ
anJr(s!))smn
(115)
where oe is the corresponding coefficient. Then
T Jo.:
Σ
oeJr(s!")i )amm E
ERY
Ray Frmms
(116)
BEFi,ny
where the final "E" follows from Assumption that each element the summation belongs to Ray J,ony
Thus
Vj Fiany T3 GR EF Ptier
(117)
Then the connections between these supports can be established according Defi. 2.3
V(i F.,yy (8) x Ta C F
(118)
Since Jr(s( ),,,, and J3 (F((( ):,om have full column rank ns, T(s(0) must have non-zero deter- minant. Otherwise, it would follow that the rank of ((s()) is less than ny, which would imply contradiction that J (S(()) )a.m +J((s()) )..n,) T(s(9) has a column rank less than ny.
The determinant of the matrix ((s( can be represented its Leibniz formula as
ar
(et(T(((()))
sgn(a) [(
# 0,
(119)
E
i=1
where Sn, is the set of pnppeuuutaiions. Thus, there is at least one term in the sum that non-zero, i.e,
ar
Fo Sap Vi E (1,...,,ul, mr), sgn(a)
II
( (1)) # 0,
(120)
which is equivalent
30 E Snys Vi E [il....,n,.. ((s( (ot() + 0.
(121)
Then we can conclude that this or is in the support of T(s) since s()) s. Therefore, follows that
Vj (1....,ny} n1), ojj T,.-
(122)
Combined with Eq. (118), we have
V(i,j) E F. (i,o(i) E (i) x Taa F.
(123)
Denote
o(F o(F,,)))= = ((ioo(j)) (i.j) F.
(124)
Then we have
o(F,,,y) C F.
(125)
Because of the sparsity regularization on the estimated Jacobian, we further have
| S F.,myl (o(
(126)
Together with Eq. (125), it follows that
oFF,,ny) Fi
(127)
Suppose T(s) + - -P.l, then
Dj1 # j2, Thi n Tsa # 0.
(128)
26

---

Additionally, consider is fi.....,y n1 for which
o(ja) E Th n ja:-
(129)
Since J1 + j2, we can assume ja + ji without loss generality. Based on Assumption iv, there exists Cj₁ Ji such that Nkecs Fi.m; {íi} Because
ja E {i1} = n Fiano
(130)
iEC,
there must exists is Cj such that
33 & F Fag.mr. Since ji E Figinyy we have (13.J1) E F, Therefore, according to Eq. (118), we have
(131)
{is} x This C Frunn.
(132)
Note that o(js) The n T2.: implies
(is, ((s)) E {is} x Th
(133)
Then by Eqs. (132) and (133), we have
( E F
(134)
This implies (i3, E Fi,oy by Eqs. (124) and (127), which contradicts Eq. (131). Therefore, we have proven by contradiction that T(s) = Dr(s) -1 ' -1 By replacing T(s) with Dy(s) 'P, in Eq. (113), we obtain Eq. (112), which the goal.
27

---

B Experiments
In this section, we describe the experimental settings as well as some additional results.
B.1 Supplementary experimental settings
To produce observational data that meets the required assumptions for different models, we simulate the sources and mixing process as follows:
UCSS. To ensure that the true nonlinear mixing process adheres to the Structural Sparsity condition (Assumption ii in Thm. 3.1). per previous work (Zheng et al., 2022), generate observed variables in a structured way: Each observed variable is only a nonlinear mixture of its direct ancestors. For instance, if the observed variable x1 has parents $1 and S2, then X; fl ($1, 82). We use Generative Flow (GLOW) (Kingma and Dhariwal, 2018) with a projection layer as the nonlinear function f,. The difference between GLOW and GIN is that GLOW does not impose constraint on the determinant of the Jacobian, thus being more suitable for the general nonlinear function since it has less inductive bias. The implementation of GLOW is part of FrEIA! (Ardizzone al., 2018-228 2018-2022).
The ground-truth sources are sampled from a multivariate Gaussian, with zero means and variances sampled from a uniform distribution on [0.5, 3]. which are of the same values as in previous works (Khemakhem et al., 2020a; Sorrenson et al., 2020; Zheng et al., 2022). It is worth noting that we sample sources from a single multivariate Gaussian so that all sources are marginally independent, unlike from most previous works assuming conditional independence given auxiliary variables.
Mixed. For the Mixed model, we partition sources into S and sp. For sources in s,, we sample them in the same way as that for UCSS. For sources in SD, we sample them from 2n + 1 multivariate Gaussian distributions
required by Assumption ii in Thm. 4.4. Similarly, these multivariate Gaussian distributions are of zero means and variances sampled from uniform distribution on [0.5,3) For sources in Sy, we generate their influences on the observed variables in a structured way described above to satisfy the partial sparsity assumption (Assumption iv in Thm. 4.4); for sources in SD. remove the constraint on the structure and permit each source to affect all observed variables.
Base. For the Base model, following (Sorrenson al., 2020), we use GLOW (Kingma and Dhariwal, 2018) as the mixing function to generate the data. The sources are from single multivariate Gaussian distribution with zero means and variances uniformly sampled from the interval [0.5, 3]. No constraints on the structure have been imposed for the Base model.
In the evaluation of our model, utilize the Mean Correlation Coefficient (MCC) as a metric for assessing the correspondence between the ground-truth and recovered latent sources. The MCC is cal- culated by first determining the pair-wise correlation coefficients between the true sources and the re- covered sources after a nonlinear component-we wise transformation learned by regression. Subsequently, an assignment problem solved match each recovered source with the corresponding ground-truth source that exhibits the highest correlation. MCC is widely accepted metric in the literature for measuring the degree of identifiability, accounting for component- wwse transformations (Hyvärines and Morioka, 2016). Our results are all based on 20 trials, each with a different random seed.
For the synthetic datasets used in our experiments, the sample size is 2000. The parameters used for training include a learning rate of 0.01 and a batch size of 200. Additionally, the number of coupling layers for both GIN and GLOW is set as 10. In regard to the "Triangles" dataset, it comprises 60. 000 32 x 32 images of drawn triangles. The statistics of the dataset are described in (Yang et al., 2022). For the experiments conducted on this dataset, the learning rate set at x 10- and the batch size 100. Concerning the EMNIST dataset, it includes 240, 000 28 x 28 images of real-world handwritten digits. The learning rate and batch size used for these experiments
3 10-4 and 240, respectively, The experiments are conducted directly using the official implementation of (Sorrensn et al., 2020) with an additional sparsity regularization term on the Jacobian of the estimated mixing function.
bhttp://gitaak.cm/iissse///e/e/ Punps//gittbb.co///LLLHHHH
28

---

B.2 Supplementary experimental results
In this section, we delve deeper into the applicability of our results by offering additional empirical studies that further illuminate the implications of the proposed theory. Specifically, we focus on the following aspects: (1) the effect of different regularization terms on the performance of identification; (2) the applicability of the theory as illustrated by additional real-world examples.
Regularization. For the regularization term, directly utilizing the lo penalty may be compu- tationally infeasible optimization problem. To overcome this issue, adopt the ε regularizer, which has been extensively studied in the literature for high- dimensional support recovery, particularly for variable selection (Wainwright, 2009) and Gaus- sian graphical model selection (Ravikumar et al., 2008). The usage of { regularizer induces spar- sity in the solution; however, it may also intro- duce bias which can negatively affect the perfor- mance (Fan and Li, 2001; Breheny and Huang, 2011). This is because the & norm penalty also penalizes both small and large entries, unlike the lo norm which remains constant for nonzero entries. To remedy this bias issue, explore alternative penalties, such as the smoothly clipped absolute deviation (SCAD) penalty (Fan and Li. 2001) and minimax concave penalty (MCP) (Zhang, 2010), which can be interpreted as hybrids of &u and & penalties. Additionally, recovery of the & penalty is based on the incoherence conditions various cases (Wainwright, 2009; Ravikumar et al., 2008, 201 1), which may be restrictive in practice, whereas the SCAD and MCP penalties do not rely on such conditions (Loh and Wainwright, 2017). Based on our experimental results (Fig. 8), we adopt the MCP penalty the regularization term.
it results in a discrete
SCAD
0.84
0.92
Number sources
Figure 8: MCC of UCSS w.r.t. different sparsity regularizations and numbers of sources.
note that the support
EMNIST.
To further demonstrate the generalizability the proposed identifiability results, we present identification results for all digits the EMNIST dataset. As previously mentioned, we show the recovered attributes with the top-4 singular values. From Fig. 9, it is clear that these attributes are highly interpretable and appear to be the underlying concepts that influence the process of writing digits by hand, This indicates the potential applicability our assumptions real-world scenarios.
29

---

0000000
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
/
1
1
1
/
2
2
2
2
2
2
2
2 3 4
2 3 4 5 6
2
2
2
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3 44 5555
3
3
3
3
4
4
4
4
4
4
4
4
4 4
4
4
4
4
5
5
5
5
5
5
5
5
5 5 5
5
5
6 6
6
6
6
6
6
6 7 8
6 6 6
6
6
6
6
66
6
7 7 7 7
7
7
7
7
7
7 7 7 7
7
7
777 8
/
8
8
8
8
8
8
8
8 9
8
8 8
8
8
8
8
8
8
9
9
9
9
9
9
9
9
9 9
9
9
9
9
9
9
9
(a) Line thickness
(b) Angle
0
0
0
0
0
0
0 1
0 1
0
0
0
0
0
0
0
0
0 1
1
1
1
1
1
/
1
1
1
1
1
/
2
2
2
2
2
2
2 3
2 3 4
2 3
2
2222
2
2
2
2
2 3 4
2 3 4
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4 4
4
4
4
4
4
4
5
5
5
5
5
5555
55
5
5
5
5
5 6
5 6
5
6
6
6
6
6
6
6
6
6
6 6
6
6
6
6
6
6
7
7
7
7
7
7
7
7 7
7 7
7
7
7
7
7
7 7 8
7
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8 9
9
9
9
9
9
9
9
9 9
9 9
9
9
9
9
9
9
(c) Upper width
(d) Height
Figure 9: Results for all digit classes within the EMNIST dataset. We present the identified sources with the top-4 standard deviations SDs. Each sub-figure represents a source identified by our model, with its value varying from -4 +4 SDs illustrate its influence. The rightmost column presents heat map given by the absolute pixel difference between the -1 and +1 SDs. The interpretation of these sources may correspond to line thickness, angle, upper width, and height, respectively.
30


Reviews:
[{"review_id": "HIIY6ohvqd", "reviewer": "Reviewer_jekt", "summary": "\nThe paper introduces more flexible ways to perform nonlinear independent component analysis (nonlinear ICA).  Nonlinear ICA involves identifying the sources s from the observed x when both s and x are related by x = f(s) and f is a nonlinear function.  Previous work has developed a method for this problem under a strict structural sparsity assumption that the s's and x's are one-to-one and onto, and all the s's are independent of each other.  Current work provides theorems that relax the assumption in various ways including: (1) undercompletness--there can be more observed variables x than sources s; (2) partial sparsity--only a subset of all the s's may map to x's; (3) source dependence--all sources s do not have to be statistically dependent on each other; and (4) flexible grouping structures--the possibility that some of the sources can be partitioned into independent subgroups of sources.  There are experiments on synthetic and real world datasets that show the effectivness of their approach.\n\n\n", "questions": "While the undercompleteness result appears to me to be unique to this paper, (Zheng et al 2022) also has an undercompletness result.  This paper is written so that it sounds like (Zheng et al 2022) has no undercompletness result.  It would be nice if this situation could be explained or clarified.\n\nIt was a bit confusing that on line 113, A is defined as a set of natural number tuples but on line 103 A is defined as a subset of natural numbers.\n\nI think on line 114 that A_{:,j} := { i | (i,j) \\in S } should really be A_{:,j} := { i | (i,j) \\in A }.\n", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "\nThis paper is original because it introduces novel approaches, as far as I know, that extend the situations where nonlinear ICA can be applied.\n\nThe paper exhibits good quality in various ways.  First, there are various theoretical results included in the paper that extend the cases where nonlinear ICA can be applied.  Second, there are also results in several experimental settings that back up the theory.\n\nThe paper is mostly clear in its explanations.\n\nIn terms of significance, extending the situations where nonlinear ICA can be applied is an accomplishment.\n", "weaknesses": "While in theory extending the cases where nonlinear ICA can be applied is a strength, because there wasn't any empirical qualitative evaluation of how this approach compares to other approaches in disentangling the sources, it is not clear how significant this work is.  It does not have to be a comparison of how well it disentangles sources; it could be comparing them on some other application, such as how well they extract features that are useful for classification, for example.  It does not even have to be comparing this paper's approach to previous approaches; it could be comparing the different extensions of nonlinear ICA presented in this paper.\n\nAlso, as pointed out by the authors, another limitation of this work is that the experimental results were only on visual datasets but not on other modalities.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer’s time on carefully reading our manuscript and providing insightful suggestions. These have undoubtedly further improved the manuscript. Please kindly find our detailed, point-by-point response below.\n\n**Q1:** Suggestions on expanding empirical comparisons.\n\n**A1:** We are very grateful for these constructive suggestions. It is worth noting that, instead of proposing a better model to disentangle the sources, we focus on providing a theoretical guarantee for uncovering generating processes under certain conditions. Our result could be one of the lacking interpretations of many previous empirical studies showing that latent variable models are likely identifiable in complex scenarios, as mentioned in L88-89 and L329-344. The various extensions proposed for nonlinear ICA focus on the assumptions regarding the ground-truth data-generating process, rather than the estimation methods. Therefore, they can only be rigorously validated through ablation studies conducted on different data-generating processes. Complementing various previous empirical studies, we believe that our ablation studies and experiments on both the synthetic and real-world datasets provide further validations.\n\nIn addition, we have also included new experimental results in the PDF attached to the global response. These results demonstrate that the quality of identification can be enhanced by increasing the sample size, further validating our theorems.\n\n**Q2:** Clarify the theorem proposed in [1] about the undercomplete case.\n\n**A2:** We appreciate the great suggestion. As mentioned in L159-160, [1] only removes the rotational indeterminacy while our theorem removes all major indeterminacies and only preserves the component-wise transformation and permutation. In other words, [1] only gets rid of specific spurious solutions due to the rotational indeterminacy (e.g., the ‘rotated-Gaussian’ MPA) while we prove the full identifiability of the undercomplete case. We have added additional detailed discussion earlier in the introduction to avoid potential confusion.\n\n**Q3:** Notations:\n\n- **(1):** It was a bit confusing that on L113, $\\mathcal{A}$ is defined as a set of natural number tuples but on L103 $\\mathcal{A}$ is defined as a subset of natural numbers;\n\n- **(2):** there is a typo on L114, i.e., $\\mathcal{S}$ should be $\\mathcal{A}$.\n\n**A3:** Thank you so much for reminding us, and sorry for any potential confusion. We have modified L113-114 as: “For any set of indices $\\mathcal{B} \\subset \\\\{1, \\ldots, m\\\\} \\times \\\\{1, \\ldots, n\\\\}$, analogously, we have $\\mathcal{B}\\_{i,:}\\coloneqq\\\\{j \\mid(i, j) \\in \\mathcal{B}\\\\}$ and $\\mathcal{B}_{:,j}\\coloneqq\\\\{i \\mid(i, j) \\in \\mathcal{B}\\\\}$.\" This modification also corrects the typo. Thanks again!\n\n\n---\n\n\n\n[1] Zheng et al. \"On the identifiability of nonlinear ICA: sparsity and beyond.\"\n"}, {"review_id": "Qdo8Ed3Kev", "reviewer": "Reviewer_gBCZ", "summary": "This paper extends a recent result from Zheng et al 2022, which introduces an assumption they call “structural sparsity” to induce identifiability in nonlinear ICA without relying on a common (but arguably unrealistic) assumption that the observed variables are conditionally independent given observed auxiliary information. Whereas Zheng et al 2022 gave identifiability results only in the setting where the structural sparsity assumption holds perfectly and there are an equal number of sources and observed variables, this paper relaxes these assumptions in several interesting ways and gives identifiability or partial identifiability results in these more general settings.\n\nThe first theoretical contribution shows identifiability under structural sparsity in the undercomplete setting, where there are more observed variables than sources. This lets them relax the usual assumption that the mixing function must be bijective, and instead only requires that the mixing function be injective.\n\nThe second theoretical contribution relaxes the structural sparsity assumption to the setting where you have partial structural sparsity (it holds for a subset of sources) or partial independence of sources and shows partial identifiability under these assumptions. Here the partial dependence of sources does not need to be known.\n\nThe third theoretical contribution assumes that the dependence between sources is known, and the fourth theoretical contribution assumes the sources with dependencies are conditionally independent given auxiliary variables (which is distinct from existing work because they don’t assume all sources are influenced by the auxiliary variable, just the dependent sources).\n\nThey use an estimation method using a sparsity regularizer (that encourages a sparse estimated mixing function) with a flow-based generative model. They perform experiments on two simple visual datasets (Triangles and EMNIST) and perform ablations where they generate data that satisfy two combinations of assumptions for their theory, compared to a base setting that does not satisfy their assumptions. Following existing work, they use MCC as their metric and their models achieve higher MCC when the assumptions are satisfied.", "questions": "- Are you aware of Lachapelle et al 2022b? See https://arxiv.org/pdf/2207.07732.pdf. Lachapelle et al 2022a uses mechanism sparsity to induce permutation identifiability, but Lachapelle et al 2022b extends this approach to the partial identifiability setting. It would be (1) worth mentioning in the Introduction section that Lachapelle et al 2022a introduced the idea to use sparsity to induce identifiability, which inspired the approach of Zheng et al. 2022 (as stated in the text of Zheng et al 2022, see Section 3.1 of that paper), and (2) to cite Lachapelle et al 2022b as prior work using sparsity for partial identifiability (though in a distinct setting from your results as it relies on conditional independence given observed auxiliary variables).", "limitations": "- Their experiments are only on visual disentanglement tasks and there are many other interesting disentanglement or other tasks that would be interesting to see in future work.\n- No concerns about negative societal impacts.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Overall, this is a very interesting paper and makes novel contributions in what I think is an interesting setting: using sparsity to induce identifiability in nonlinear ICA.\n- They clearly motivate why relaxing each assumption makes the assumptions more realistic.\n- I agree that the “conditional independence given auxiliary information” assumption that is common in the literature is not a great assumption, and I’m happy to see recent work removing or reducing this assumption.\n- They don’t require distributional assumptions.\n- It is well-written and well-structured overall. It is very clear what the prior work accomplishes and what the contributions are.", "weaknesses": "- There could be more experiments in realistic settings. (However, given the strength of the theoretical contributions in this paper, I think the paper should be accepted as is.)\n\nMinor comments on the writing (did not affect score):\n- Line 84-85: You say “part of the sources can be grouped into irreducible independent subgroups…”, but “irreducible subgroup” is a term in algebra with a specific meaning. You could avoid this “collision” by saying “irreducible independent subgroupings” or something similar.\n- Line 156: You start a sentence with the word “Differently, …” which sounds strange. You could say “In contrast, …” instead.\n- Line 167: “While this removes the restriction of bijectivity between sources and observed variables, it remains uncertain as to whether Structural Sparsity holds in general, particularly for all sources in a universal way.”\n    - This sentence is confusing - you are saying it is uncertain whether Structural Sparsity holds in general, but Structural Sparsity is one of your assumptions. Are you saying it is uncertain whether Structural Sparsity is a reasonable assumption, based on whether it is likely to be satisfied on real-world data?\n- Line 177: It’s also weird to start this sentence with “Differently”.\n- Multiple lines: You start a handful of sentences with “Besides, …” and each time that is not really the word you mean. You should rethink how each of these sentences connects to the previous sentences and find the appropriate word for each case.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are very grateful for your detailed reading and insightful suggestions. Your comments on the quality of our paper and the strength of our contributions mean a lot to us. Please kindly find our point-by-point response below.\n\n**Q1:** There are many other interesting real-world tasks that would be interesting to see in future work.\n\n**A1:** Thanks a lot for your great suggestions. Indeed, there are various tasks that could benefit from our theory, and, as you suggested, more applications would be intriguing. We have shown some positive results on the visual tasks, and perhaps natural language is also a promising field. At the same time, various empirical research have shown that latent variables are likely identifiable in complex scenarios, possibly involving undercompleteness and violations of sparsity and independence (L88-89, L329-334). Complementing previous works, our theory may interpret these empirical results, and our ablation studies and experiments on both the synthetic and real-world datasets provide further validations. Of course, validating our theory in even more tasks is exciting and will be constantly done in future works.\n\nIn addition, we have also included new experimental results in the PDF attached to the global response. These results demonstrate that the quality of identification can be enhanced by increasing the sample size, further validating our theorems.\n\n**Q2:** L84-85: “Irreducible subgroup” is a term in algebra with a specific meaning. You could avoid this “collision” by saying “irreducible independent subgroupings” or something similar.\n\n**A2:** Thank you so much for the constructive suggestion. We have replaced “subgroup” with “subgrouping” in the updated manuscript.\n\n**Q3:** L156: “Differently, …” could be replaced with “In contrast, …”\n\n**A3:** Thanks. We have updated it accordingly.\n\n**Q4:** L167: “While this removes the restriction of bijectivity between sources and observed variables, it remains uncertain as to whether Structural Sparsity holds in general, particularly for all sources in a universal way.” This sentence is confusing.\n\n**A4:** Thanks for the insightful question. In this sentence, we are trying to motivate the importance of dealing with potential partial violations of Structural Sparsity among a subset of sources. In light of your suggestion, we have revised it to “... it remains uncertain as to whether Structural Sparsity always holds for all sources in a universal way”. We hope it could help to avoid potential confusion.\n\n**Q5:** L177: It is weird to start this sentence with “Differently”.\n\n**A5:** Yes, we fully agree with you. We have removed this in the updated manuscript.\n\n**Q6:** A handful of sentences are started with “Besides, ..”, which could be replaced with more appropriate words.\n\n**A6:** We are very grateful for the great suggestion. We have carefully modified the related connecting words in the updated manuscript as follows:\n\n- **L37:** Replaced “Besides” with “Moreover”.\n\n- **L64:** Replaced “Besides” with “In addition to”.\n\n- **L100:** Replaced “Besides” with “Furthermore”.\n\n- **L110:** Replaced “Besides” with “Additionally”.\n\n- **L212:** Replaced “Besides” with “Furthermore”.\n\n- **L278:** Replaced “besides” with “in addition to”.\n\nWe hope these modifications could improve the transition between related sentences. Thanks again!\n\n**Q7:** Discuss [1] in the introduction and cite [2] as prior work.\n\n**A7:** Thanks so much for sharing these excellent works. In the updated manuscript, we have highlighted in the introduction that [1] introduced the idea of proving identifiability with sparsity, which then inspired [3]. Moreover, we have emphasized in both the introduction and theory that [2] also uses sparsity for partial identifiability.\n\n---\n\n\n[1] Sébastien, et al. \"Disentanglement via mechanism sparsity regularization: A new principle for nonlinear ICA.\"\n\n[2] Lachapelle, Sébastien, and Simon Lacoste-Julien. \"Partial disentanglement via mechanism sparsity.\"\n\n[3] Zheng et al. \"On the identifiability of nonlinear ICA: sparsity and beyond.\"\n"}, {"review_id": "IxKJKhs45E", "reviewer": "Reviewer_nmMP", "summary": "The paper extends identifiability theory of nonlinear ICA (NICA), and deep latent variable models in general, by utilizing structural sparsity. In particular, previous works have shown that NICA can be identified if there is some observed auxiliary data or latent dependencies that essentially capture the inductive biases in the data generative process. The approach of structural sparsity (Zheng, '22) instead takes an alternative approach, namely constraining the nonlinear mixing function and its Jacobian. In this paper the authors extend that work as follows i.e. assuming structural sparsity and some additional assumptions:\n\n1. the authors show identifiability for a situation in which the mixing function is injective rather than bijective i.e. undercomplete case / i.e. smaller latent dimension than observed dimension. This is important for e.g learning low dimensional, semantically meaningful, interpretable latent features\n\n2. the authors show identifiability for a situation in which the structural sparsity principle applies only to some of the independent components\n\n3. further identifiability is shown for situation where not all the latent components are independent, rather components form independent subspaces. In fact some components may be dependent, conditionally independent or have some grouping structures.", "questions": "I will use this space for further suggestions and questions:\n\n- Could you please introduce structural sparsity bit more clearly and intuitively -- if one has not read the original Zheng'22 paper then it is difficult to follow.\n\n- In estimation, please clarify: is it required that we know which groups of latent variables are independent, and which are potentially dependent? How is this exactly established in practice?\n\n- please explain in more detail how your algorithm, in practice, allows dimension reduction without assuming observation noise, and how jacobian can be computed for non-bijective transformation\n\n- What is the level of nonlinearity in the mixing functions? I dont believe this is mentioned anywhere, e.g. number of layers or similar. \n\n- \". Since the proposed condition is on the connective structure from sources to observed variables, i.e., the support of the Jacobian matrix of the mixing function, it does not require the mixing function to be of any specific algebraic form.\". Please make this sentence bit more precise or explain better what does 'specific algebraic form' mean. Because structural sparsity does still limit the form of the function -- f can not longer be any arbitrary function.\n\n-  \"Most of these methods require auxiliary variables to be observable, such as class labels and domain indices (Hyvärinen and Morioka, 2016, 2017\". H&M 2017, really only require the previous data so it's not really a big limitation and it's arguable whether this really constitutes of having auxiliary variables...I would consider moving that reference to the next sentence since it's a time-series model : \"with the exceptions being those for time series...[move H&M'17 reference here]\"\n\n- \"The most obvious  one arises from the fact that it may fail in a number of situations where the generating processes are heavily disentangled.\" Please explain in more detail why this may be?\n\n- \"We first present the result on removing one of the major assumptions in ICA, i.e., the number of observed variables m must be equal to that of hidden sources n.\" This makes it sound like it hasn't been done previously in general, which of course it has been done many times previously in linear ICA (e.g eriksson and koivunen '03) and nonlinear ICA (e.g. khemakhem '20, halva '21 etc etc). so rather than saying removing majort assumption in ICA, make it specific to sparsity\n\n- as for the title: are you really \"generalizing beyond structural sparsity\"? as I feel structural sparsity is still the fundamental building block here. I would say you are generalizing structural sparsity in nonlinear ICA.\n\n- \"This is similar to Independent Subspace Analysis (ISA) (Theis, 2006)\"  Either explain why you cite Theis, or cite an earlier ISA work (e.g. Hyvarinen & Hoyer, 2000)?", "limitations": "Authors should discuss limitations in more detail:\n\n- what are possible limitations of structural sparsity assumptions should be discussed more e.g. any scenarios where you expect it to be a poor assumption?\n\n- the point discussed in the \"Weaknesses\" section about the limitations in the identifiability theorems of 4.1 and 4.3 must be addressed and justified much more clearly or else those theorems should be removed\n\n- authors should note the heurestic approach of their estimation algorithm -- does GIN even have universal _function_ approximation capability? \n\n- related, discuss limitations of estimation algorithm in general. Is the algorithm guaranteed to find the correct sparsity for example? If not, then that should be pointed out as need for future works.\n\n- \"However, our setting is more flexible in the sense that we do not assume all sources to be influenced by the auxiliary variable. Specifically, sources in $s_I$ are mutually independent as in the original ICA setting, while only  sources in $s_D$ have access to the side information from the conditional independence given u,\". This is true and a nice result of theorem 4.4, but there is the limitation that should be discussed, namely now you are making restricting assumption on _both_ the mixing function as well as on the auxiliary variables -- in some sense this is worst of both worlds (but still a nice theoretical result with possible practical uses).", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "First, this paper is in general of good quality in that it is well organized and, in general, clearly written.\n\nMain strengths:\na.) most significantly, authors remove several strong limitations of previous works and extend identifiability of structural sparsity to undercomplete and case where not all latent components are structurally sparse (in those situations the remaining sources are shown to be identifiable). As a result these ideas are now more applicable to realistic data and scenarios.\n\nb.) These results have been reached, mostly, without too strong additional assumptions. For instance, it is shown that the necessary assumptions are more likely to hold in this new undercomplete case which is encouraging!\n\nc.) authors bridge gap between structural sparsity and the previous works that assume auxiliary variables. in particular, this work allows unconditionally independent components to follow structural sparsity and components which are conditionally independent given auxiliary variables. Whilst arguably to be expected, it is important to show this result (but see below for potential related weakness)", "weaknesses": "In general the weakness of this paper is that provides only few theoretical advances (albeit important; as mentioned above) but provides little beyond that. In particular, this is the results of:\n\n1. Contribution of the paper is not as significant as the authors describe, or at least there is limited coverage of relevant works\n2. Potential problems in some of the identifiability theorems\n3. Novelty is limited to identifiabiltiy theorems -- no new algorithms \n4. Experiments are lacking\n\nI will expand on each of these points below:\n\nMore detail for 1.):  In particular the authors state that \"Therefore, we establish, to the best of our knowledge, one of the first general frameworks for uncovering latent variables with appropriate identifiability guarantees in a principled manner\". I think this is too vague and general and fails to acknowledge the generality of some other works -- your work can be novel whilst admitting the generality of some other works too. First, Kivva '22 show a very general framework for identifiability by making, arguably, less strong assumptions on the mixing functions -- currently the work of Kivva '22 is only mentioned later on in section 3 (and even there in a problematic manner as ill point out below). Due to the generality of the results in Kivva, I would expect their result to be discussed in the introduction / early on in the text and tell the reader why yours is better or at least different. For example Kivva make different type of assumptions on the mixing function (piecewise affine) etc, while you on the sparsity. Second the work of Halva '21 (disentangling identifiable features) provides another very general framework and unlike what you claim, it is not limited to time-series but to any dependencies of arbitrary order, and also does not require condition independence on some auxiliary variables but rather also assumes unconditional independence.\n\nMore detail for 2.): In Theorems 4.1 and 4.3  $S_d$ is \"identified up to an invertible transformation\". Surely if something is identified just up to invertible (vector-valued) function then we are not doing any better than nonlinear ICA i.e. we are essentially where one started and thus we have not identified anything. To me this is misleading and not a publishable identifiability result (if I have understood correctly -- please correct me if I'm wrong and I'll adjust my score accordingly). Authors do acknowledge this point but rather than talking about it they make a vague remark that \"Thm. 4.1 may be helpful for some tasks that do not necessitate the recovery of each individual source, such as domain adaptation.\" This does not suffice in my opinion. And similarly about Thm 4.3 they say: \"there exists an invertible transformation $h_{c_i}$ which is analogous to the previous element-wise indeterminacy. Consequently, even when dealing with mixtures of high and one-dimensional sources, like in the case of multi-modal data, we can still recover the hidden generating process to some extent.\" Again I think this is bit generous and hiding the fact that $\\mathbf{s}_{c_i}$ is fully unidentifiable in the sense of nonlinear ICA. At least this limitation must be admitted more clearly -- preferably its usefulness would be shown empirically.\n\nMore detail for 3.):\nThere is a simple regularization term of the jacobian added -- but this is heurestic (vs. mle methods) from previous work. Undoubtedly there could be work done towards what is the best way to estimate a model that assumes structural sparsity but such is not done here.\n\nMore detail for 4.) \nAn important question is whether structural sparsity is a valid assumption. I think this can indeed be the case for many types of generative processes.  But the question then is then do the experiments strengthen that intuition. I feel not. It is not clear to me why e.g. EMNIST experiment there would be structural sparsity. EMNIST is also a very simple data set. I would expect the experiments to show that the learned independent components are useful in practical applications (see the brain signal experiments in Halva '21 for instance or in Khemakhem (iVAE) '20). I'm not saying specifically this type of real data experiments need to be introduced, but something to further highlight the strenght of this method would be helpful. Another example is to evaluate the method more thoroughly on some benchmarks from the disentanglement learning literature. There are also some claims in the paper that would be good to justify experimentally for instance you claim on line 311-313 that \"This is particularly helpful in the context of self-supervised learning 311 (Von Kügelgen et al., 2021) or transfer learning (Kong et al., 2022), where latent representations are 312 modeled as a changing part and an invariant part.\" If this indeed the case, why not show that on data? Indeed 311 to 324 gives nice discussion and its a great shame this has not been shown experimentally as it would really take this paper to the next level.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks so much for your time and insightful comments. We are glad that you find our results important and the paper of good quality. Please find our point-by-point response below.\n\n**Q1:** Limited coverage of some works.\n\n**A1:** Thanks for the suggestions. We have now detailed the discussion in the introduction. Specifically, in [1], there are assumptions on both source distribution and mixing functions: (1) the sources are assumed to be a Gaussian mixture, with an unobserved state $\\mathbf{u}$ (L158-161); (2) the mixing function is assumed to be piece-wise affine. These allow identifiability of sources up to an affine transformation where mixtures remain, with more assumptions needed (e.g., conditional independence given $\\mathbf{u}$) for component-wise identifiability.\n\nThus, we differ by (1) having no distributional assumptions, and (2) allowing general nonlinear functions if the assumption on connective structures is met. We do not claim that our assumption on the mixing functions is better than those in [1]. Structural sparsity allows general nonlinearity with sparse connections, while piece-wise affine functions allow dense structures.\n\nIn addition, we fully agree that [2] should be further emphasized for its highly significant contributions. We have highlighted its generalization to arbitrary dependency order (e.g., spatial dependencies) without assuming conditional independence. Meanwhile, additional information (e.g., time or spatial index) may not always be available, which is one of the motivations of our work.\n\n**Q2:** Implication of Thms. 4.1 and 4.3.\n\n**A2:** Thanks for the question. We have added more descriptions to clarify this. In Thm. 4.1, the identifiability of $\\mathbf{s}\\_D$ up to an invertible transformation means that $\\mathbf{s}\\_D$ will not be mixed with sources in $\\mathbf{s}\\_I$ after estimation. In practice, it implies that the **subspace** of the changing part (the distribution of $\\mathbf{s}\\_D$ changes w.r.t. $\\mathbf{u}$) can be disentangled from the mixture of both changing and invariant parts ($\\mathbf{s}$), which aids tasks like domain adaptation, e.g., the changing style (as a whole) can be disentangled from different images with invariant content. Similarly, in Thm. 4.3, the subspace-wise identifiability means sources in $\\mathbf{s}\\_{c\\_i}$ will not be mixed with sources outside $\\mathbf{s}\\_{c\\_i}$, which disentangles $\\mathbf{s}\\_{c\\_i}$ as an individual high-dimensional component.\n\n**Q3:** Novelty appears limited to theorems, and whether sparsity penalty and GIN are just heuristics.\n\n**A3:** According to our theory, the additional sparsity penalty on the MLE objective during estimation (L339-341), together with assumptions on the data-generating process, is needed to guarantee the correct identification (L125-128). Moreover, according to [3], coupling-based flows (e.g., GIN) are universal diffeomorphism approximators. The volume-preserving nature of GIN does not hinder it from validating our theorems, as rescaling is one of the allowed indeterminacies after identification. Of course, there exists some approximation of $\\ell_0$ norm for gradient-based optimization (MCP penalty), and more work could be done for further improvement.\n\n**Q4:** Experiments on more tasks.\n\n**A4:** Indeed, there are various tasks that benefit from our theory, and more applications would be intriguing. Meanwhile, we have emphasized in introduction (L88-89) and experiment (L329-334) with additional citations (>9) that prior research shows latent variable models are likely identifiable in complex scenarios, possibly involving undercompleteness and violations of sparsity and independence. Our theory may interpret these empirical results, and our ablation studies and experiments on both the synthetic and real-world datasets provide further validations, complementing previous works.\n\n**Q5:** Discuss structural sparsity and failure cases more.\n\n**A5:** Thanks, we have added more discussion on it. For failure, one may consider recording in a very crowded room, where every microphone records the mixture of signals from most sources at the same time.\n\n**Q6:** Is it necessary to know which latent variables are independent/dependent?\n\n**A6:** No. In practice, each data point can be assigned a class corresponding to the value of the auxiliary variable of dependent variables (L335-337). These labels do not provide extra information for independent variables since they do not need auxiliary variables.\n\n**Q7:** How to reduce dimensions and compute the Jacobian for non-bijective transformations?\n\n**A7:** As in prior works (e.g., [4]) and noted in L346-347, we concatenate latent sources with independent Gaussian noises for flow-based estimation's dimensionality needs and Jacobian computation.\n \n**Q8:** Level of nonlinearity, e.g., number of layers.\n\n**A8:** 10 layers (L881).\n\n**Q9:** What does 'specific algebraic form' mean?\n\n**A9:** Great question. We meant to refer to \"specific\" function classes like conformal mappings mentioned above but have clarified this by changing the term to 'the above-mentioned classes' to avoid confusion.\n\n**Q10:** Explain: \"The most … are heavily disentangled.\"\n\n**A10:** Apologies for the typo. It should be \"heavily **entangled**\", like a crowded room where sources heavily influence each other, resulting in a dense Jacobian.\n\n**Q11:** More suggested updates:\n\n- (1) relocate a reference;\n\n- (2) specify undercompleteness claim to sparsity;\n\n- (3) a new title;\n\n- (4) cite an earlier ISA work;\n\n- (5) further highlight a limitation of Thm. 4.4.\n\n**A11:** We are grateful for all the constructive suggestions. All points have been updated accordingly.\n \n\n---\n\n[1] Kivva et al. \"Identifiability …\"\n\n[2] Hälvä et al. \"Disentangling …\"\n\n[3] Teshima et al. \"Coupling-based invertible neural networks are universal diffeomorphism approximators.\"\n\n[4] Sorrenson et al. \"Disentanglement by nonlinear ICA with general incompressible-flow networks (gin).\"\n"}, {"review_id": "ob3IqfcYjw", "reviewer": "Reviewer_m3QW", "summary": "The article serves as an extension to the work of Zheng et al. 2022, which posited the identifiability of nonlinear ICA based on specific structural sparsity assumptions related to the mapping of sources and mixtures. This current article expands on that by addressing the undercomplete case—where the number of mixtures exceeds the number of sources—and furthermore, it relaxes both the sparsity and source independence assumptions to yield more general identifiability results.\tIn the end authors provide some numerical examples to illustrate the applications of their identifiability theorems.\t", "questions": "* Line 190: Could you clarify what is meant by \"changing\" sources?\n\n* Line 195-196: 6, the phrase \"For sources s_D, they do not need to be mutually independent as long as they are dependent on the variable u\" is somewhat confusing. Subsequent equation (3) implies that S_D and S_I are conditionally independent when conditioned on u, and that the components of s_I are independent. What is the necessity for this latent variable u? Perhaps the authors could shed some light on this.\n\n* How does Theorem 4.1’s contribution compare with those from Khemakhem et al. (2020a) and Sorenson et al. (2020)?\n\n* Lines 215-217: Could you elucidate what condition (i) in Theorem 4.2 represents? What do s_d and B_{s_I} signify? Perhaps the discussions on lines 229-247 should precede Theorem 4.2 to better contextualize its contents and results, potentially with more lucid explanations.\n\n* Regarding Figure 4 and 5, could you expound on how these examples pertain to the nonlinear ICA setup (what are the sources, which appear to be images, and what are the nonlinear mixings)? How are the interpretations in the captions of these figures derived? Could you also elucidate how these examples relate to the identifiability theorems presented in the article and the conditions stipulated in these theorems?\n", "limitations": "Yes, the authors adequately addressed the limitations.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The article tackles the foundational issue of the nonlinear inverse problem, making significant assertions regarding fundamental identifiability theorems. These are premised on assumptions of partial independence and structural sparsity.The problem under investigation is a fundamental problem and the article offers some important results for this problem.", "weaknesses": "The most significant shortcoming of the article lies in its presentation, particularly in its explanation of the core assumptions underpinning the theorems, as well as the motivation for the conditions applied in these assumptions. Absent a solid grasp of these theorems, it becomes challenging to properly evaluate the paper's contributions and ascertain its potential impact.\n\nIn terms of specific issues:\n\n* Concerning Theorem 3.1: This theorem seems to aim at generalizing Theorem 1 from Zheng et al., 2022 for a complete (m=n) case to an undercomplete (m>n) case. The identifiability results for ICA setups typically do not depend on a specific estimator choice or estimation algorithm. However, the statement of Theorem 3.1 seems rather unclear in this context. According to the article's notation, \\hat{f} refers to a specific estimate of the mixing function. Both the set of support matrices \\mathcal{T} and the support \\hat{\\mathcal{F}} depend on this particular estimate. The assumption (i) used in Theorem 3.1 is based on \\mathcal{T} and \\hat{\\mathcal{F}}, hence, this condition appears to be linked to a specific choice of the estimator for mixing. It would be beneficial if the authors could clarify whether the assumption (i) must hold on a particular \\hat{f}, a specific set of functions, etc. This clarification will likely impact the proof in the supplementary material and the explanation given between lines 129-136.\n\n\n* Line 97: Traditional or linear ICA does not necessarily require m=n.\n\n* Line 114: Should \\mathcal{S} be \\mathcal{A}?\n\n* Line 111 vs Line 536: The symbol \\mathcal{T} has two differing definitions - the set of matrices sharing the same support as T(s) and the support of T(s) itself.\n\n* Theorem 4.1: The vectors 'w' - whose independence implies identifiability - have not been sufficiently motivated or explained.\n\n* Similar comments can be made for other identifiability theorems.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the time dedicated and constructive feedback, which has greatly improved the quality of the updated manuscript. Please find the responses to all your comments below.\n\n**Q1:** More discussion on the assumption (i) in Thm. 3.1.\n\n**A1:** Thanks so much for the suggestion. The assumption (i) does not necessitate a particular $\\hat{\\mathcal{F}}$, and it is typically satisfied asymptotically as detailed in L129-136 (it only necessitates the **existence** of one $\\mathrm{T}$ in the entire space). Except for the required sparsity regularization (L125-128), there are no specific functional classes to constrain $\\hat{\\mathcal{F}}$ during estimation. We have further highlighted it in the updated manuscript.\n\n**Q2:** L97: Traditional or linear ICA does not necessarily require m=n.\n\n**A2:** Thanks a lot. We have modified it to: “Different from settings where m=n …”\n\n**Q3:** L114: Should $\\mathcal{S}$ be $\\mathcal{A}$?\n\n**A3:** Yes, you are totally right. We have corrected the typo in the updated manuscript. \n\n**Q4:** L111 vs L536: $\\mathcal{T}$ has two differing definitions.\n\n**A4:** Thanks for rasing this point. We have corrected the denotation of $\\mathcal{T}$ in L536 to a set of matrices with the same support of $\\mathbf{T}(\\mathbf{s})$, and correspondingly, $\\mathrm{T} \\in  \\mathcal{T}$ in the following sentence.\n\n**Q5:** Thm. 4.1: the linearly independent vectors '$w$'  have not been sufficiently motivated.\n\n**A5:** Thanks for the suggestion. The linear independence of $w$ requires that the conditional distribution varies sufficiently across different values of $\\mathbf{u}$ (L229-230). The motivation of it is similar to the common assumption of variability used in [1, 2, 3]. Even though the assumption of variability is almost surely fulfilled as discussed in [1, 2, 3], our assumption is still strictly weaker from various perspectives as detailed in L229-241. For example, our definition of $w$ is only the first half of Eq. 8 in [1] and we require much fewer distinct values of $\\mathbf{u}$. We have further highlighted it in the updated manuscript.\n\n**Q6:** L190: The meaning of \"changing\" sources.\n\n**A6:** Thanks for the question. The \"changing\" sources ($\\mathbf{s}\\_D$) mean that the distribution of these sources changes across different values of the auxiliary variable $\\mathbf{u}$. For instance, styles of images change across domains while their content stays invariant.\n\n**Q7:** L195-196: More clarification on \"For sources $\\mathbf{s}\\_D$, they do not need to be mutually independent as long as they are dependent on the variable $\\mathbf{u}$\".\n\n**A7:** Thank you for your suggestion. It means that sources in $\\mathbf{s}\\_D$ (i.e., those with indices $\\\\{n\\_{I+1},\\cdots,n\\\\}$) do not need to be (mutually) conditionally independent given the auxiliary variable $\\mathbf{u}$; they only need to be influenced by (dependent on) $\\mathbf{u}$. The variable $\\mathbf{u}$ only provides changes on the distributions of these sources, like a domain label or time index.\n\n**Q8:** How does Thm. 4.1’s contribution compare with those from [2, 3]?\n\n**A8:** Thanks for raising this. We only require sources in $\\mathbf{s}\\_D$​ to depend on an auxiliary variable $\\mathbf{u}$ with $n\\_D​+1$ values, intuitively fitting scenarios where fewer changes (smaller $n\\_D$) correspond to easier identifiability (fewer required values, i.e., $n\\_D+1$). In contrast, prior works like [2, 3] assume all sources to depend on $\\mathbf{u}$ with $nk+1$ values ($k$ denotes the order of the distribution), limiting identifiability to ideal situations without any degree of violations on either the number of sources dependent on $\\mathbf{u}$ or the number of values of $\\mathbf{u}$. This can restrict practical application, as often only subsets of sources are influenced by auxiliary variables, or those variables lack sufficient variability. Of course, as a trade-off, Thm. 4.1 itself does not provide component-wise identifiability. More details can be found in L224-247.\n\n**Q9:** L215-217: More explanation on the motivation and some notations ($\\mathbf{s}\\_d$ and $B\\_{\\mathbf{s}\\_I}$) of condition (i) in Thm. 4.2.\n\n**A9:** We appreciate these insightful questions and suggestions. Condition (i) in Thm. 4.2 originates from [4], which intuitively means there exist two values of the auxiliary variable such that their influences on the sources are different. $\\mathbf{s}_d$ is a typo and should be $\\mathbf{s}\\_D$, which denotes sources that dependent on $\\mathbf{u}$ (sorry for the confusion). $B\\_{\\mathbf{s}\\_I}$ is a subspace of $\\mathcal{S}\\_I$. In light of your suggestions, we have moved the discussion (L229-L247) to the paragraph directly following Thm. 4.2 and further emphasized these notations.\n\n**Q10:** More explanation on Figs. 4 and 5.\n\n**A10:** For these images (triangles in Fig. 4 and hand-written digits in Fig. 5), we assume that they are generated by hidden sources (e.g., angle, height, etc.), and try to recover these from their observed mixtures (i.e., images). Each row represents a source we identified, and we vary its value with the rightmost column showing a heatmap of the absolute pixel difference to visualize its influence. We interpret the estimated sources’ potential semantics from their influences, as listed in the captions. We only deal with single classes (e.g., zero in EMNIST), without auxiliary variables (e.g., digit labels). Thus, prior identifiability theories relying on auxiliary variables cannot support these seemingly reasonable results, but our generalized theorems could probably underpin them.\n \n\n---\n\n\n\n[1] Hyvarinen et al. \"Nonlinear ICA using auxiliary variables and generalized contrastive learning.\"\n\n[2] Khemakhem et al. \"Variational autoencoders and nonlinear ica: A unifying framework.\"\n\n[3] Sorrenson et al. \"Disentanglement by nonlinear ica with general incompressible-flow networks (gin).\"\n\n[4] Kong et al. “Partial identifiability of domain adaptation.\"\n"}, {"review_id": "sShZrH8uey", "reviewer": "Reviewer_qJ69", "summary": "This paper utilizes the structural sparsity assumption on the support of the Jacobian matrix of the mixing function to extend the identifiability of nonlinear ICA in more settings including under-completeness, partial sparsity and source dependence, flexible grouping structures. It is a technically solid paper supported by theorems, proofs and experiments.", "questions": "1. Theorem 3.1: Is $|\\mathcal{F}_{i,:}|$ the $L_0$ or $L_1$ norm of $\\mathcal{F}$? Is $\\mathcal{C}_k$ a minimal set of sample indices to uniquely identify source $k$? How does the assumption ii show Structural Sparsity? The regularization constraint $|\\hat{\\mathcal{F}}| \\leq |\\mathcal{F}|$, which induces sparsity, should be included in Theorems. Also, I note that the author(s) tried to explain the assumptions in the following paragraphs, but I would suggest to describe the Theorems, at least Theorem 3.1, in plain words so that readers can better understand the Theorems. Or at least explain the notations (e.g., $\\mathcal{C}_k$) which are not explained in Section 2 Preliminaries.\n\n2. Theorem 3.1: Zheng et al. 2022 also proposed a Theorem on the undercomplete case. Could you kindly clarify the novelty between your proposed Theorem and that proposed in Zheng et al. 2022?\n\n3. Theorem 4.1: The author(s) claimed that we do not need to know the dependence structures or the number of dependent sources, but it is not intuitive to me how Theorems 4.1 and 4.2 uncover the dependence structures and the number of dependent sources. Could you please clarify?\n\n4. Theorem 4.2: What are $u_1$ and $u_2$? Are they two different sets of auxiliary labels?\n\n5. Lines 281 - 283: The claim on multi-modal data is unclear. Could you please clarify how to identify linkage across multiple modalities?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Overall, the manuscript is well written with clear organization, comprehensive literature review, technically solid theorems, detailed proofs and promising experiment results. \n\n2. This work addressed some limitations of theorems about identifiability with Structural Sparsity in Zheng et al. 2022 and extended nonlinear ICA with Structural Sparsity to more general settings. The proposed theorems could be more practically useful in real-world datasets.\n\n3. The notations, theorems and proofs are clear in general.", "weaknesses": "1. This work is interesting, and it would be great if code is provided to replicate the results. Please consider making the code publicly available. \n\n2. The meanings of some notations are not clear. See Questions. \n\n3. Ablation study. The author(s) only evaluated MCCs w.r.t. the number of sources. In Figure 3, the MCCs for 8 or 10 sources are a bit low so I wonder if more samples can help to improve MCCs. It would be more informative and convincing if more experiment configurations are considered (e.g., number of samples, various grouping structures) to demonstrate the effectiveness of proposed Theorems.\n\n4. Ablation study. Though the result comparison seems obvious visually, the authors should consider performing statistical tests to compare results between proposed methods and baseline method. \n\n5. Minor: \"exits\" should be \"exists\" at line 236.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your detailed reading and insightful questions. All of these constructive suggestions have further improved the quality of the updated manuscript. Please find our point-by-point response below.\n\n**Q1:** Implementation availability.\n\n**A1:** Thanks for finding our work interesting. We are more than happy to make the scripts publicly available soon. For quick utilization, kindly note that all experiments are conducted using public GitHub repositories (FrEIA and GIN), detailed in Section B.1. Please feel free to let us know if you have any questions about the experiments.\n\n**Q2:** Clarification on some notations.\n\n**A2:** We are very grateful for your detailed reading, which helps improve our manuscript's clarity. We have emphasized all these points in the updated manuscripts:\n\n- **Q2(a):** Is $|\\mathcal{F}|$ the $\\ell_0$ or $\\ell_1$ norm of $\\mathcal{F}$?\n\n- **A2(a):** It is the $\\ell_0$ norm of $\\mathcal{F}$.\n\n- **Q2(b):** Is $\\mathcal{C}_{k}$ a minimal set of sample indices to uniquely identify source $k$?\n\n- **A2(b):** We do not necessitate the set $\\mathcal{C}\\_{k}$ to be minimal, only that it uniquely identifies $k$. Of course, it is equivalent to consider $\\mathcal{C\\}_{k}$ as a minimal set.\n\n- **Q2(c):** What are $\\mathbf{u}\\_1$ and $\\mathbf{u}\\_2$?\n\n- **A2(c):** These are two distinct values of the auxiliary variable $\\mathbf{u}$.  \n\n**Q3:** More experiment configurations.\n\n**A3:** Thanks for your suggestion. In light of it, we have conducted additional experiments with different sample sizes, of which the results are shown in the attached PDF in the global response. From the results, it is clear that increasing the sample size could improve MCCs and further stabilize the performance.\n\n**Q4:** Statistical tests to compare results between proposed methods and baseline methods.\n\n**A4:** Thanks a lot for the suggestion. Accordingly, we have conducted statistical tests on all comparisons, and all p-values are less than $0.01$, which are consistent with the visual differences in the violin graphs. We have emphasized this in the updated manuscript.\n\n**Q5:** Word \"exits\" should be \"exists\" at L236.\n\n**A5:** Thanks! It has been corrected.\n\n**Q6:** How does assumption ii of Thm. 3.1 show Structural Sparsity?\n\n**A6:** We are grateful for that insightful question. If the connective structure between sources and observed variables is extremely dense (e.g., no zero entry in the Jacobian matrix), assumption ii cannot be satisfied, emphasizing its role in promoting structural sparsity. However, it is worth noting that, after extending from the bijective setting in [1], where the assumption of Structural Sparsity is originally proposed, to the undercomplete case in our manuscript, this assumption can be met even with a relatively dense structure, provided there are enough observed variables and the underlying graph is not fully connected. Thus, it leans more toward a \"structural diversity\" assumption in our generalization, and the name “Structural Sparsity” is chosen primarily to acknowledge its root and maintain continuity with its original name.\n\n**Q7:** Better include the regularization constraint during estimation in theorems.\n\n**A7:** Thank you for the suggestion. We have now incorporated it into all related theorems to avoid potential misunderstanding. Initially, we had just emphasized it following the theorem since it was not an assumption about the data-generating process, but including it directly in the theorem indeed improves the clarity.\n\n**Q8:** Better explanation of theorems and some notations (e.g., using plain words) so that readers can understand them more easily.\n\n**A8:** Thanks a lot for the kind suggestion. We have added descriptions in plain words of all theorems in the updated manuscripts. For example, Thm. 3.1 states that with sufficient sample size and structural sparsity (detailed later) on the connective structure between sources and observed variables, component-wise identifiability can be achieved even under undercomplete cases with sparsity regularization. We have also highlighted some notations used in the theorems. For instance, $\\mathcal{C}_{k}$ in the assumption of Structural Sparsity denotes a set of source indices.\n\n**Q9:** Could you clarify the novelty between your proposed theorem and that proposed in [1] about the undercomplete case?\n\n**A9:** We appreciate the great question. As mentioned in L159-160, [1] only removes the rotational indeterminacy while our theorem removes all major indeterminacies and only preserves the component-wise transformation and permutation. In other words, [1] only gets rid of specific spurious solutions due to the rotational indeterminacy (e.g., the ‘rotated-Gaussian’ MPA) while we prove the full identifiability of the undercomplete case.\n\n**Q10:** How do Thms. 4.1 and 4.2 uncover the dependence structures and the number of dependent sources?\n\n**A10:** Thanks for your insightful question. For the set of dependent sources, i.e., $\\mathbf{s}\\_D$, Thms. 4.1 and 4.2 only provide the subspace-wise identifiabliity up to an invertible transformation, and thus not being able to uncover the structures and the number of dependent sources. The identifiability of $\\mathbf{s}\\_D$ up to an invertible transformation means that $\\mathbf{s}\\_D$ will not be mixed with sources in $\\mathbf{s}\\_I$ after estimation, i.e., the block-wise identifiability (e.g., Thm 4.2 in [2]), which does not mean the component-wise identifiability of sources in $\\mathbf{s}\\_D$.\n\n**Q11:** How to identify linkages across multiple modalities.\n\n**A11:** Thank you for the great question. Since we stil assume the (conditional) independence between different subspaces $\\mathbf{s}\\_{c\\_j}$ (Eq. 4), we do not allow dependencies across subspaces and thus cannot identify linkages across multiple modalities.\n\n---\n\n\n\n[1] Zheng et al. \"On the identifiability of nonlinear ICA: sparsity and beyond.\"\n\n[2] Kong et al. “Partial identifiability of domain adaptation.”\n"}]

Author rebuttal:
We extend our sincere thanks to each of the reviewers for their thoughtful insights and the time devoted to reviewing our manuscript. We are encouraged that all of the reviewers have found our paper of good quality in various ways. With appreciation, we have provided detailed, point-by-point responses to each reviewer's comments in the individual replies. In this global response, we take the opportunity to present additional experimental results, which have been summarized in the attached PDF. Specifically, the quality of the identification improves w.r.t. the increasing of the sample size.

Meta-review: This article extends the previous work on nonlinear Independent Component Analysis (ICA) identifiability, which focused on structural sparsity assumptions. This paper builds on that by handling the undercomplete scenario and relaxing sparsity and source independence assumptions. The article includes theoretical advancements and practical examples to illustrate their identifiability theorems.

Overall, the paper is intriguing, offering fresh insights into inducing identifiability in nonlinear ICA through sparsity. Theoretical advancements are well-presented, expanding the applicability of nonlinear ICA. The relaxation of assumptions is motivated logically, supported by experimental results. The paper is well-written and structured, effectively delineating prior work, contributions, and theoretical foundations.

The level of novelty and contribution to the community is deemed substantial.
Decision: Accept (oral)