如何自己搭建网站,如何制作大量网页,简单网页设计模板图,wordpress登录密码前言
本文是对On the Identifiability of Nonlinear ICA: Sparsity and Beyond (NIPS 2022)中两个结构稀疏假设的总结。原文链接在Reference中。
什么是ICA(Independent component analysis)#xff1f;
独立成分分析简单来说#xff0c;就是给定很多的样本X#xff0c;通…前言
本文是对On the Identifiability of Nonlinear ICA: Sparsity and Beyond (NIPS 2022)中两个结构稀疏假设的总结。原文链接在Reference中。
什么是ICA(Independent component analysis)
独立成分分析简单来说就是给定很多的样本X通过样本分离出组合成样本的源S。
关于ICA的详细内容可以参考Yifan Shen的博客ICA简明攻略
非线性独立成分分析
非线性独立成分分析ICA旨在从其可观测的非线性混合物中恢复潜在的独立源。非线性独立成分分析ICA是无监督学习的基础。它推广了线性ICAComon, 1994用于从观测数据中识别潜在源。这些观测数据是源的非线性混合。对于观测向量 x x x非线性ICA将其表示为 x f ( s ) x f(s) xf(s) f f f是一个未知的可逆混合函数 s s s是表示边缘上独立源的潜在随机向量。非线性ICA问题的困难点在于在没有额外假设的情况下是不可解的。即在没有额外假设或限制的情况下把观测变量分解为独立的元素存在无穷种解。同时分离后的元素仍然是源的混合。
现有的研究引入了辅助变量 u u u例如类别标签、域索引、时间索引并假设在给定 u u u的条件下源是条件独立的。关于这部分工作如果感兴趣可以去看 Hyvärinen的talk。
条件独立 P ( A , B ∣ C ) P ( A ∣ C ) ⋅ P ( B ∣ C ) P(A, B|C) P(A|C) \cdot P(B|C) P(A,B∣C)P(A∣C)⋅P(B∣C) 一个很好的例子 C指赖床A指熬夜B指迟到 P ( A , B ∣ C ) P ( A ∣ C ) ⋅ P ( B ∣ C ) P(A, B|C) P(A|C) \cdot P(B|C) P(A,B∣C)P(A∣C)⋅P(B∣C)赖床的发生使得熬夜想通过赖床来影响迟到的可能为零即没有别的可能来影响迟到了所以此时熬夜和迟到就是条件独立了。
结构稀疏(Structural Sparsity)假设
Theorem 1. Let the observed data be sampled from a nonlinear ICA model as defined in Eqs. (1) and (2). Suppose the following assumptions hold:
i. Mixing function f f f is invertible and smooth. Its inverse is also smooth.
ii. For all i ∈ { 1 , … , n } i \in \{1, \ldots, n\} i∈{1,…,n} and j ∈ F i , : j \in \mathcal{F}_{i, :} j∈Fi,:, there exist { s ( ℓ ) } ℓ 1 ∣ F i , : ∣ \{s^{(\ell)}\}_{\ell1}^{|\mathcal{F}_{i, :}|} {s(ℓ)}ℓ1∣Fi,:∣ and T T T s.t. span { J f ( s ( ℓ ) ) i , : } ℓ 1 ∣ F i , : ∣ R F i , : n \text{span}\{J_f(s^{(\ell)})_{i, :}\}_{\ell1}^{|\mathcal{F}_{i, :}|} \mathbb{R}^n_{\mathcal{F}_{i, :}} span{Jf(s(ℓ))i,:}ℓ1∣Fi,:∣RFi,:n and [ J f ( s ( ℓ ) ) T ] j , : ∈ R F ^ i , : n [J_f(s^{(\ell)})^T]_{j, :} \in \mathbb{R}^{n}_{\hat{\mathcal{F}}_{i, :}} [Jf(s(ℓ))T]j,:∈RF^i,:n.
iii. ∣ F ^ ∣ ≤ ∣ F ∣ |\hat{\mathcal{F}}| \leq |\mathcal{F}| ∣F^∣≤∣F∣.
iv. (Structural Sparsity) For all k ∈ { 1 , … , n } k \in \{1, \ldots, n\} k∈{1,…,n}, there exists C k C_k Ck such that ⋂ i ∈ C k F i , : { k } . \bigcap_{i \in C_k} \mathcal{F}_{i, :} \{k\}. i∈Ck⋂Fi,:{k}.
Then h : f ^ − 1 ∘ f h : \hat{f}^{-1} \circ f h:f^−1∘f is a composition of a component-wise invertible transformation and a permutation.
符号含义 J f ( s ) {J_f(s)} Jf(s)表示对源矩阵求偏导得到的雅可比矩阵如上图所示。KaTeX parse error: Got function \hat with no arguments as subscript at position 4: {J_\̲h̲a̲t̲{f}(\hat{s})} 表示源矩阵经过变换后得到的矩阵求偏导得到的雅可比矩阵。其实就是表示nonlinear ICA求解后得到的矩阵求偏导。因为在有解的情况下求解出的源只是真实源的排列组合因此表示称这种形式。后面会用预测值来表示带hat的量。 F \mathcal{F} F 表示雅各比矩阵 J f ( s ) {J_f(s)} Jf(s)的support也就是其不为0的点组成的集合。 F ^ \hat{\mathcal{F}} F^ 表示雅各比矩阵KaTeX parse error: Got function \hat with no arguments as subscript at position 4: {J_\̲h̲a̲t̲{f}(\hat{s})}的support也就是其不为0的点组成的集合。 i , : i,: i,: 表示的是某一行中所有不为0点的索引。也就是横坐标固定列坐标任取。 s ( l ) s^{(l)} s(l)表示的是第l个源 C k C_k Ck
理论拆解
第一条很容易理解。由观测样本X恢复出源S的过程是一个求逆的过程。在 f f f是可逆平滑的情况下才可以求逆求导。第二条表示的意思是源S可能的组合空间足够大实数。这条是为了避免ill-posed conditions。比如雅可比矩阵的某一个部分一直满足后面的假设条件使得假设虽然成立但仍无法求解。第三条表示预测雅可比矩阵support的数量小于等于真实雅可比矩阵support support的数量。第四条表示的意思是对于某一列 C k C_k Ck中的行 i i i来说从support集合 F \mathcal{F} F中取行坐标为 i i i的所有坐标点也就是取了某一行上的所有support。依次取出所有行的support在列方向上求交集。一定存在这样的列它的列坐标是k可以保证这列存在不止一个support存在交集同时这列存在这些support的对应行只在这列上有交集意思是某些观测值的共同源只有一个。概括来说就是一定至少存在一个源是某些观测变量的唯一共同源。 满足上述条件的情况下可以得到对源 s s s做变换 f f f得到实际的 x f ( s ) xf(s) xf(s)再做逆变换 f − 1 f^{-1} f−1 整个过程是分量逐一逆变换加上排列也就是component-wise invertible transformation and a permutation。
证明
问题简化
证明的目标是 h : f ^ − 1 ∘ f h : \hat{f}^{-1} \circ f h:f^−1∘f 为源s的permutation with component-wise invertible变换。也就是 f ^ f ∘ h − 1 ( s ) \hat{f} f \circ h^{-1}(s) f^f∘h−1(s). 假设 D ( s ) D(s) D(s) 表示一个对角矩阵 P P P 表示一个排列变换矩阵。通过使用链式法则, 我们可以把 f ^ f ∘ h − 1 ( s ) \hat{f} f \circ h^{-1}(s) f^f∘h−1(s) 表示为 J f ^ ( s ^ ) J f ∘ h − 1 ( h ( s ) ) J f ∘ g − 1 ∘ P − 1 ( P g ( s ) ) J f ∘ g − 1 ( P − 1 P g ( s ) ) J P − 1 ( P g ( s ) ) J f ∘ g − 1 ( g ( s ) ) J P − 1 ( P g ( s ) ) J f ( g − 1 ( g ( s ) ) ) J g − 1 ( g ( s ) ) J P − 1 ( P g ( s ) ) J f ( s ) D ( s ) P , (1) \begin{aligned} J_{\hat{f}}(\hat{s}) J_{f \circ h^{-1}}(h(s)) \\ J_{f \circ g^{-1} \circ P^{-1}}(Pg(s)) \\ J_{f \circ g^{-1}}(P^{-1}Pg(s)) J_{P^{-1}}(Pg(s)) \\ J_{f \circ g^{-1}}(g(s)) J_{P^{-1}}(Pg(s)) \\ J_{f}(g^{-1}(g(s))) J_{g^{-1}}(g(s)) J_{P^{-1}}(Pg(s)) \\ J_{f}(s)D(s)P, \end{aligned} \tag{1} Jf^(s^)Jf∘h−1(h(s))Jf∘g−1∘P−1(Pg(s))Jf∘g−1(P−1Pg(s))JP−1(Pg(s))Jf∘g−1(g(s))JP−1(Pg(s))Jf(g−1(g(s)))Jg−1(g(s))JP−1(Pg(s))Jf(s)D(s)P,(1)
其中g是一个元素可逆函数invertible element-wise function。 接着用 T ( s ) D ( s ) P T(s) D(s)P T(s)D(s)P 来表示 D ( s ) P D(s)P D(s)P T ( s ) T(s) T(s)是可逆的。由此目标可以转化为证明2成立 J f ^ ( s ^ ) J f ( s ) T ( s ) , (2) J_{\hat{f}}(\hat{s}) J_{f}(s)T(s), \tag{2} Jf^(s^)Jf(s)T(s),(2) 也就是我们希望证明预测得到的雅可比矩阵只是真实雅可比矩阵的一个排列。 如果变换 T ( s ) T(s) T(s)不是一个简单的排列变换也就是 T ( s ) ≠ D ( s ) P T(s) \neq D(s)P T(s)D(s)P那么2就不成立。如果我们能证明 T ( s ) D ( s ) P T(s) D(s)P T(s)D(s)P也就能说明2成立。 接着我们的目标就转化为证明 T ( s ) D ( s ) P , (3) T(s) D(s)P, \tag{3} T(s)D(s)P,(3)
找源雅可比矩阵预测雅可比矩阵变换矩阵T之间的关系
用 F \mathcal{F} F 表示 J f ( s ) J_f(s) Jf(s) 的支撑集 F ^ \hat{\mathcal{F}} F^ 表示 J f ^ ( s ^ ) J_{\hat{f}}(\hat{s}) Jf^(s^) 的支撑集 τ \tau τ 表示 T ( s ) T(s) T(s) 的支撑集 T T T 表示具有支撑集 τ \tau τ 的矩阵。根据假设 ii我们可以得到 span { J f ( s ( ℓ ) ) i } ℓ 1 ∣ F i , ∣ R F i , n (4) \text{span}\{J_f(s^{(\ell)})_i\}_{\ell1}^{|\mathcal{F}_{i, }|} \mathbb{R}^n_{\mathcal{F}_{i, }} \tag{4} span{Jf(s(ℓ))i}ℓ1∣Fi,∣RFi,n(4)
由于 { J f ( s ( ℓ ) ) i } ℓ 1 ∣ F i , ∣ \{J_f(s^{(\ell)})_i\}_{\ell1}^{|\mathcal{F}_{i, }|} {Jf(s(ℓ))i}ℓ1∣Fi,∣ 形成了 R F i , n \mathbb{R}^n_{\mathcal{F}_{i, }} RFi,n 的一组基对于任意 j 0 ∈ F i , j_0 \in \mathcal{F}_{i, } j0∈Fi,我们可以将热独向量 e j 0 ∈ R F i , n e_{j_0} \in \mathbb{R}^n_{\mathcal{F}_{i, }} ej0∈RFi,n 重写为 e j 0 ∑ ℓ ∈ F i , α ℓ J f ( s ( ℓ ) ) i , : , (5) e_{j_0} \sum_{\ell \in \mathcal{F}_{i, }} \alpha_{\ell} J_f(s^{(\ell)})_{i, :}, \tag{5} ej0ℓ∈Fi,∑αℓJf(s(ℓ))i,:,(5)
其中 α ℓ \alpha_{\ell} αℓ 是对应的系数。则有 T j 0 , : e j 0 T ∑ ℓ ∈ F i , : α ℓ J f ( s ( ℓ ) ) i , : ⋅ T ∈ R F ^ i , : n , (6) T_{j_0, :} e_{j_0} T \sum_{\ell \in \mathcal{F}_{i, :}} \alpha_{\ell} J_f(s^{(\ell)})_{i, :} \cdot T \in \mathbb{R}^n_{\hat{\mathcal{F}}_{i, :}}, \tag{6} Tj0,:ej0Tℓ∈Fi,:∑αℓJf(s(ℓ))i,:⋅T∈RF^i,:n,(6)
公式6的“ ∈ \in ∈”符号来自于假设 ii即6求和中的每个元素都属于 R F ^ i , n \mathbb{R}^n_{\hat{\mathcal{F}}_{i, }} RF^i,n。因此有 ∀ j ∈ F i , , T j , ∈ R F ^ i , n (7) \forall j \in \mathcal{F}_{i, }, \quad T_{j, } \in \mathbb{R}^n_{\hat{\mathcal{F}}_{i, }} \tag{7} ∀j∈Fi,,Tj,∈RF^i,n(7) 到这一步我们推出了 T j , : T_{j, :} Tj,: 是属于预测矩阵的支撑集的。
然后我们可以在支撑集之间建立如下关系 ∀ ( i , j ) ∈ F , { i } × τ j , : ⊆ F ^ . (8) \forall (i, j) \in \mathcal{F}, \{i\} \times \tau_{j, :} \subseteq \hat{\mathcal{F}}. \tag{8} ∀(i,j)∈F,{i}×τj,:⊆F^.(8)
需要注意这里的 × \times ×表示的是combine。意思是横坐标 i {i} i和 τ j , : \tau_{j, :} τj,:表示的纵坐标组合起来。
根据假设 i, T ( s ) T(s) T(s) 是一个可逆矩阵这意味着它有一个非零的行列式值。将矩阵 T ( s ) T(s) T(s) 的行列式为它的 Leibniz 公式展开 det ( T ( s ) ) ∑ σ ∈ S n { sgn ( σ ) ∏ i 1 n T ( s ) i , σ ( i ) } ≠ 0. (9) \text{det}(T(s)) \sum_{\sigma \in S_n} \{\text{sgn}(\sigma) \prod_{i1}^n T(s)_{i,\sigma(i)}\} \neq 0. \tag{9} det(T(s))σ∈Sn∑{sgn(σ)i1∏nT(s)i,σ(i)}0.(9)
其中 S n S_n Sn 是 n n n排列的集合。
由于9不为0 则存在至少一个求和元素是非零的表示为 ∃ σ ∈ S n , ∀ i ∈ { 1 , … , n } , sgn ( σ ) ∏ i 1 n T ( s ) i , σ ( i ) ≠ 0. (10) \exists \sigma \in S_n, \forall i \in \{1, \ldots, n\}, \text{sgn}(\sigma) \prod_{i1}^n T(s)_{i,\sigma(i)} \neq 0. \tag{10} ∃σ∈Sn,∀i∈{1,…,n},sgn(σ)i1∏nT(s)i,σ(i)0.(10)
10等价于 ∃ σ ∈ S n , ∀ i ∈ { 1 , … , n } , T ( s ) i , σ ( i ) ≠ 0. (11) \exists \sigma \in S_n, \forall i \in \{1, \ldots, n\}, T(s)_{i,\sigma(i)} \neq 0. \tag{11} ∃σ∈Sn,∀i∈{1,…,n},T(s)i,σ(i)0.(11)
由此我们可以得到 σ ( ⋅ ) \sigma(·) σ(⋅) 在 T ( s ) T(s) T(s) 的支持集中进而有 ∀ j ∈ { 1 , … , n } , σ ( j ) ∈ T j , (12) \forall j \in \{1, \ldots, n\}, \sigma(j) \in T_{j, } \tag{12} ∀j∈{1,…,n},σ(j)∈Tj,(12)
结合 (8)可以得到 ∀ ( i , j ) ∈ F , ( i , σ ( j ) ) ∈ { i } × T j , : ⊆ F ^ . (13) \forall (i, j) \in \mathcal{F}, (i, \sigma(j)) \in \{i\} \times T_{j, :} \subseteq \hat{\mathcal{F}}. \tag{13} ∀(i,j)∈F,(i,σ(j))∈{i}×Tj,:⊆F^.(13)
表示 σ ( F ) { ( i , σ ( j ) ) ∣ ( i , j ) ∈ F } . (14) \sigma(\mathcal{F}) \{(i, \sigma(j)) | (i, j) \in \mathcal{F}\}. \tag{14} σ(F){(i,σ(j))∣(i,j)∈F}.(14)
以上我们得到了 F \mathcal{F} F, F ^ \hat{\mathcal{F}} F^, T T T 之间的变换关系。
反证法证明 T ( s ) D ( s ) P T(s) D(s)P T(s)D(s)P成立
假设 T ( s ) ≠ D ( s ) P T(s) \neq D(s)P T(s)D(s)P那么 ∃ j 1 ≠ j 2 , τ j 1 , : ∩ τ j 2 , : ≠ ∅ . (15) \exists j_1 \neq j_2, \tau_{j_1, :} \cap \tau_{j_2, :} \neq \varnothing. \tag{15} ∃j1j2,τj1,:∩τj2,:∅.(15)
此外考虑 j 3 ∈ { 1 , … , n } j_3 \in \{1, \ldots, n\} j3∈{1,…,n} 使得 σ ( j 3 ) ∈ τ j 1 , : ∩ τ j 2 , : . (16) \sigma(j_3) \in \tau_{j_1, :} \cap \tau_{j_2, :}. \tag{16} σ(j3)∈τj1,:∩τj2,:.(16)
因为 j 1 ≠ j 2 j_1 \neq j_2 j1j2我们可以假设 j 3 ≠ j 1 j_3 \neq j_1 j3j1 而不失一般性矩阵通常很大 j 3 j 1 j_3 j_1 j3j1 只是概率非常非常小的一种情况概率小到 1 n \frac{1}{n} n1。
根据假设 iv, 存在 j 1 ∈ C j 1 j_1 \in C_{j_1} j1∈Cj1 使得 ⋂ i ∈ C j 1 F i , : { j 1 } . (17) \bigcap_{i \in C_{j_1}} \mathcal{F}_{i, :} \{j_1\}. \tag{17} i∈Cj1⋂Fi,:{j1}.(17)
由于 j 3 ∉ { j 1 } ⋂ i ∈ C j 1 F i , : , (18) j_3 \not\in \{j_1\} \bigcap_{i \in C_{j_1}} \mathcal{F}_{i, :}, \tag{18} j3∈{j1}i∈Cj1⋂Fi,:,(18)
那么一定存在 i 3 ∈ C j 1 i_3 \in C_{j_1} i3∈Cj1 使得 j 3 ∉ F i 3 , : (19) j_3 \not\in \mathcal{F}_{i_3, :} \tag{19} j3∈Fi3,:(19)
因为 j 1 ∈ F i 3 , : j_1 \in \mathcal{F}_{i_3, :} j1∈Fi3,:我们有 ( i 3 , j 1 ) ∈ F (i_3, j_1) \in \mathcal{F} (i3,j1)∈F。然后根据公式 (8)可以得到 { i 3 } × τ j 1 , : ⊆ F ^ . (20) \{i_3\} \times \tau_{j_1, :} \subseteq \hat{\mathcal{F}}. \tag{20} {i3}×τj1,:⊆F^.(20)
由 σ ( j 3 ) ∈ τ j 1 , ∩ τ j 2 , \sigma(j_3) \in \tau_{j_1, } \cap \tau_{j_2, } σ(j3)∈τj1,∩τj2, 可以得到 ( i 3 , σ ( j 3 ) ) ∈ { i 3 } × τ j 1 , . (21) (i_3, \sigma(j_3)) \in \{i_3\} \times \tau_{j_1, }. \tag{21} (i3,σ(j3))∈{i3}×τj1,.(21)
通过公式(20) 和 (21)我们可以得到 ( i 3 , σ ( j 3 ) ) ∈ F ^ , (22) (i_3, \sigma(j_3)) \in \hat{\mathcal{F}}, \tag{22} (i3,σ(j3))∈F^,(22)
结合公式 (14) 可知 ( i 3 , j 3 ) ∈ F (i_3, j_3) \in \mathcal{F} (i3,j3)∈F与等式 (19) 矛盾。
则可知假设 T ( s ) ≠ D ( s ) P T(s) \neq D(s)P T(s)D(s)P不成立。
则 T ( s ) D ( s ) P T(s) D(s)P T(s)D(s)P得证。
不完备情况下的结构稀疏假设
不完备指观测样本的数量远大于源的数量
Theorem 2. Let the observed data be sampled from a linear ICA model defined in Eqs. ( 1 ) (1) (1) and ( 3 ) (3) (3) with Gaussian sources. Differently, the number of observed variables (denoted as m m m) could be larger than that of the sources n n n, i.e., m ≥ n m \geq n m≥n. Suppose the following assumptions hold:
i. The nonzero coefficients of the mixing matrix A \mathbf{A} A are randomly drawn from a distribution that is absolutely continuous with respect to Lebesgue measure.
ii. The estimated mixing matrix A ^ \hat{A} A^ has the minimal L 0 L_0 L0 norm during estimation.
iii. (Structural Sparsity) Given C ⊆ { 1 , 2 , … , n } C \subseteq \{1,2,\ldots,n\} C⊆{1,2,…,n} where ∣ C ∣ 1 |C| 1 ∣C∣1, let A C ∈ R m × ∣ C ∣ A_C \in \mathbb{R}^{m \times |C|} AC∈Rm×∣C∣ represents a submatrix of A ∈ R m × n A \in \mathbb{R}^{m \times n} A∈Rm×n consisting of columns with indices C C C. Then, for all k ∈ C k \in C k∈C, we have ∣ ⋃ k ′ ∈ C supp ( A k ′ ) ∣ − rank ( overlap ( A C ) ) ∣ supp ( A k ) ∣ . \left| \bigcup_{k \in C} \text{supp}(A_{k}) \right| - \text{rank}(\text{overlap}(A_C)) \left| \text{supp}(A_k) \right|. k′∈C⋃supp(Ak′) −rank(overlap(AC))∣supp(Ak)∣.
Then A ^ A D P \hat{A} ADP A^ADP with probability one, where D D D is a diagonal matrix and P P P is a column permutation matrix. 理论拆解
第一条保证了混合矩阵的结构足够复杂不是特殊的单一结构。第二条L0正则化表示的是矩阵中不为0的点的数量。这条表示预测的混合矩阵越稀疏越好。第三条support的并集按行求并也就是向行投影中support的数量 - 行重叠子矩阵的秩 每一列的support support数量。假设的目的是每个source影响的观测越少越好source共同作用越小越好。图中是一个例子 k 1 k 1 k1 并且 C { 1 , 2 , 3 } C \{1,2,3\} C{1,2,3}。让 A C A_C AC 表示图中所示的子矩阵其中 ∣ ⋃ k ′ ∈ C supp ( A k ′ ) ∣ 7. \left| \bigcup_{k \in C} \text{supp}(A_{k}) \right| 7. ⋃k′∈Csupp(Ak′) 7.蓝色虚线方块表示 overlap ( A C ) \text{overlap}(A_C) overlap(AC) rank ( overlap ( A C ) ) 2 \text{rank}(\text{overlap}(A_C)) 2 rank(overlap(AC))2。因此 ∣ ⋃ k ′ ∈ C supp ( A k ′ ) ∣ − rank ( overlap ( A C ) ) 5 黑点的数量 , \left| \bigcup_{k \in C} \text{supp}(A_{k}) \right| - \text{rank}(\text{overlap}(A_C)) 5 \text{黑点的数量}, ⋃k′∈Csupp(Ak′) −rank(overlap(AC))5黑点的数量,比 ∣ supp ( A 1 ) ∣ 4 \left| \text{supp}(A_1) \right| 4 ∣supp(A1)∣4 大。
证明
根据假设ii我们考虑以下组合优化问题 U ^ : arg min U ∈ R s × s , U U T I s ∥ A U ∥ 0 , (1) \hat{U} : \arg \min_{U \in \mathbb{R}^{s \times s}, UU^TI_s} \|AU\|_0,\tag{1} U^:argU∈Rs×s,UUTIsmin∥AU∥0,(1)
其中 A A A 是真实的混合矩阵 U ^ \hat{U} U^ 表示对应于优化问题解的旋转矩阵。设 A ^ A U ^ \hat{A} A\hat{U} A^AU^。
用反证法假设 A ^ ≠ A D P \hat{A} \neq ADP A^ADP那么 U ^ ≠ D P \hat{U} \neq DP U^DP。 这意味着存在某个 j ′ ∈ { 1 , … , s } j \in \{1, \ldots, s\} j′∈{1,…,s} 和它对应的行索引集合 I j ′ \mathcal{I}_{j} Ij′ ∣ I j ′ ∣ 1 |\mathcal{I}_{j}| 1 ∣Ij′∣1使得 U ^ i , j ′ ≠ 0 \hat{U}_{i,j} \neq 0 U^i,j′0 对所有 i ∈ I j ′ i \in \mathcal{I}_{j} i∈Ij′成立并且 U ^ i , j ′ 0 \hat{U}_{i,j} 0 U^i,j′0 对所有 i ∉ I j ′ i \notin \mathcal{I}_{j} i∈/Ij′成立。 由于 U ^ \hat{U} U^ 是可逆的并且具有完整的行秩为了避免列之间的线性依赖存在唯一对应于 j ′ j j′ 的行索引 i ′ i i′。设 U ^ : [ U ^ 1 … U ^ s ] , \hat{U} : \begin{bmatrix} \hat{U}_1 \ldots \hat{U}_s \end{bmatrix}, U^:[U^1…U^s],
我们可以得到 ∥ A ^ j ′ ∥ 0 ∥ A U ^ j ′ ∥ 0 ∥ ∑ i ∈ I j ′ A i U ^ i , j ′ ∥ 0 . (2) \|\hat{A}_{j}\|_0 \|A\hat{U}_{j}\|_0 \left\| \sum_{i \in \mathcal{I}_{j}} A_{i} \hat{U}_{i,j} \right\|_0. \tag{2} ∥A^j′∥0∥AU^j′∥0 i∈Ij′∑AiU^i,j′ 0.(2)
这里的 ∥ ⋅ ∥ 0 \|\cdot\|_0 ∥⋅∥0 表示 L 0 L_0 L0 范数即矩阵中非零元素的数量。
设 A I j A_{\mathcal{I}_j} AIj 表示由 A A A 的列索引 I j \mathcal{I}_j Ij 组成的子矩阵。注意 A i A_i Ai 表示矩阵 A A A 的第 i i i 列。根据假设 (ii, iii)由于 ∣ I j ′ ∣ 1 |\mathcal{I}_{j}| 1 ∣Ij′∣1 并且 U i , j ′ ≠ 0 U_{i,j} \neq 0 Ui,j′0我们有: ∥ ∑ i ∈ I j ′ A i U ^ i , j ′ ∥ 0 ≥ ∣ ⋃ i ∈ I j ′ supp ( A i ) ∣ − rank ( overlap ( A I j ′ ) ) ∣ supp ( A i ′ ) ∣ , (3) \left\|\sum_{i \in \mathcal{I}_{j}} A_i \hat{U}_{i,j}\right\|_0 \geq \left| \bigcup_{i \in \mathcal{I}_{j}}\text{supp}(A_{i}) \right| - \text{rank}(\text{overlap}(A_{\mathcal{I}_{j}})) \left| \text{supp}(A_{i}) \right|,\tag{3} i∈Ij′∑AiU^i,j′ 0≥ i∈Ij′⋃supp(Ai) −rank(overlap(AIj′))∣supp(Ai′)∣,(3)
其中项 rank ( overlap ( A I j ′ ) ) \text{rank}(\text{overlap}(A_{\mathcal{I}_{j}})) rank(overlap(AIj′)) 表示其所有非零项可能被矩阵的线性组合 ∑ i ∈ I j ′ , A i \sum_{i \in \mathcal{I}_{j}, A_i} ∑i∈Ij′,Ai 消除的行的最大数量。假设 i 排除了违反上述公式的情况例如 A A A 的两列具有相同的值和support。进而可以保证 ∥ ∑ i ∈ I j ′ A i U ^ i , j ′ ∥ 0 ∣ supp ( A i ′ ) ∣ ∥ A i ′ ∥ 0 ∥ A i ′ U ^ i ′ , j ′ ∥ 0 . (4) \left\|\sum_{i \in \mathcal{I}_{j}} A_i \hat{U}_{i,j}\right\|_0 \left| \text{supp}(A_{i}) \right| \left\|A_{i}\right\|_0 \left\| A_{i} \hat{U}_{i,j} \right\|_0.\tag{4} i∈Ij′∑AiU^i,j′ 0∣supp(Ai′)∣∥Ai′∥0 Ai′U^i′,j′ 0.(4)
然后我们可以构造 U ~ : [ U ~ 1 … U ~ s ] \tilde{U} : \begin{bmatrix} \tilde{U}_1 \ldots \tilde{U}_s \end{bmatrix} U~:[U~1…U~s]。 首先我们将 U ~ i , j ′ \tilde{U}_{i,j} U~i,j′ 设置为列 U ~ j ′ \tilde{U}_{j} U~j′ 中的唯一非零项。为了简便起见我们可以将 U ~ i , j ′ \tilde{U}_{i,j} U~i,j′ 设为 1。对于其他 j ≠ j ′ j \neq j jj′ 并且 U ^ i , j ≠ 0 \hat{U}_{i,j} \neq 0 U^i,j0的列 U ~ j \tilde{U}_{j} U~j我们设 U ~ i , j 1 \tilde{U}_{i,j} 1 U~i,j1。因此 ∥ A U j ^ ∥ 0 ∥ A U ~ j ∥ 0 , j j ′ , ∥ A U ^ j ∥ 0 ∥ A U ~ j ∥ 0 , j ≠ j ′ . (5) \begin{align} \left\|A\hat{U_{j}}\right\|_0 \left\|A\tilde{U}_{j}\right\|_0, j j, \\ \left\|A\hat{U}_{j}\right\|_0 \left\|A\tilde{U}_{j}\right\|_0, j \neq j. \end{align} \tag{5} AUj^ 0 AU^j 0 AU~j 0, AU~j 0,jj′,jj′.(5)
由于假设 iii 涵盖了所有列公式 (4) 对于任何 j ′ ∈ { 1 , … , s } j \in \{1, \ldots, s\} j′∈{1,…,s} 都成立。如果存在多个 U ^ \hat{U} U^ 的列有多于一个非零项为每一个列计算得到公式4。将不同的目标列索引 j ′ j j′ 的集合表示为 J J J。对于 j ∈ J j \in J j∈J设 U ^ i , j 1 \hat{U}_{i,j} 1 U^i,j1其中 i j i_j ij 是列 U j U_{j} Uj 中对应的非零项的唯一索引。对于其他 j ∉ J j \not\in J j∈J 并且 U i , j ≠ 0 U_{i,j} \neq 0 Ui,j0的列 U j U_{j} Uj设 U i , j 1 U_{i,j} 1 Ui,j1。则有 { ∥ A U ^ j ∥ 0 ∥ A U ~ j ∥ 0 , j ∈ J , ∥ A U ^ j ∥ 0 ∥ A U ~ j ∥ 0 , j ∉ J . \left\{ \begin{aligned} \|A{\hat{U}_j}\|_0 \|A{\tilde{U}_j}\|_0, j \in J, \\ \|A{\hat{U}_j}\|_0 \|A{\tilde{U}_j}\|_0, j \notin J. \end{aligned} \right. {∥AU^j∥0∥AU^j∥0∥AU~j∥0,∥AU~j∥0,j∈J,j∈/J.
如前所述每个列索引 j j j 对应一个唯一的行索引。 U ~ \tilde{U} U~ 是一个置换矩阵且 U ~ U ~ T I s \tilde{U}\tilde{U}^T I_s U~U~TIs。因此有 ∥ A U ^ ∥ 0 ∥ A U ~ ∥ 0 (7) \left\|A\hat{U}\right\|_0 \left\|A\tilde{U}\right\|_0\tag{7} AU^ 0 AU~ 0(7)
根据1 U ^ \hat{U} U^应该是最小值而7说明当 U ^ ≠ D P \hat{U} \neq DP U^DP时 U ^ \hat{U} U^ 不是最小值。与定义相违背。因此证明 U ^ D P \hat{U} DP U^DP也就是 A ^ A D P \hat{A} ADP A^ADP成立。
Reference
Zheng, Yujia, Ignavier Ng, and Kun Zhang. “On the identifiability of nonlinear ica: Sparsity and beyond.” Advances in Neural Information Processing Systems 35 (2022): 16411-16422.
