【机器学习】On the Identifiability of Nonlinear ICA: Sparsity and Beyond

前言

本文是对On the Identifiability of Nonlinear ICA: Sparsity and Beyond (NIPS 2022)中两个结构稀疏假设的总结。原文链接在Reference中。

什么是ICA(Independent component analysis)?

独立成分分析简单来说,就是给定很多的样本X,通过样本分离出组合成样本的源S。

关于ICA的详细内容,可以参考Yifan Shen的博客:ICA简明攻略

非线性独立成分分析

非线性独立成分分析(ICA)旨在从其可观测的非线性混合物中恢复潜在的独立源。非线性独立成分分析(ICA)是无监督学习的基础。它推广了线性ICA(Comon, 1994),用于从观测数据中识别潜在源。这些观测数据是源的非线性混合。对于观测向量 x x x,非线性ICA将其表示为 x = f ( s ) x = f(s) x=f(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,BC)=P(AC)P(BC)
一个很好的例子:
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,BC)=P(AC)P(BC),赖床的发生使得熬夜想通过赖床来影响迟到的可能为零,即没有别的可能来影响迟到了,所以此时熬夜和迟到就是条件独立了。

结构稀疏(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, :} jFi,:, there exist { s ( ℓ ) } ℓ = 1 ∣ F i , : ∣ \{s^{(\ell)}\}_{\ell=1}^{|\mathcal{F}_{i, :}|} {s()}=1Fi,: 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, :}\}_{\ell=1}^{|\mathcal{F}_{i, :}|} = \mathbb{R}^n_{\mathcal{F}_{i, :}} span{Jf(s())i,:}=1Fi,:=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\}. iCkFi,:={k}.

Then h : = f ^ − 1 ∘ f h := \hat{f}^{-1} \circ f h:=f^1f is a composition of a component-wise invertible transformation and a permutation.
![[Pasted image 20231121180751.png]]

符号含义
  1. J f ( s ) {J_f(s)} Jf(s)表示对源矩阵求偏导得到的雅可比矩阵,如上图所示。
  2. KaTeX parse error: Got function '\hat' with no arguments as subscript at position 4: {J_\̲h̲a̲t̲{f}(\hat{s})} 表示源矩阵经过变换后得到的矩阵求偏导得到的雅可比矩阵。其实就是表示nonlinear ICA求解后得到的矩阵求偏导。因为在有解的情况下,求解出的源只是真实源的排列组合,因此表示称这种形式。后面会用预测值来表示带hat的量
  3. F \mathcal{F} F 表示雅各比矩阵 J f ( s ) {J_f(s)} Jf(s)的support,也就是其不为0的点组成的集合。
  4. 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的点组成的集合。
  5. i , : i,: i,: 表示的是某一行中所有不为0点的索引。也就是横坐标固定,列坐标任取。
  6. s ( l ) s^{(l)} s(l)表示的是第l个源
  7. C k C_k Ck
理论拆解:
  1. 第一条很容易理解。由观测样本X恢复出源S的过程是一个求逆的过程。在 f f f是可逆平滑的情况下才可以求逆,求导。
  2. 第二条表示的意思是源S可能的组合空间足够大(实数)。这条是为了避免ill-posed conditions。比如雅可比矩阵的某一个部分一直满足后面的假设条件,使得假设虽然成立但仍无法求解。
  3. 第三条表示预测雅可比矩阵support的数量小于等于真实雅可比矩阵support support的数量。
  4. 第四条表示的意思是,对于某一列 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 ) x=f(s) x=f(s),再做逆变换 f − 1 f^{-1} f1
    整个过程是分量逐一逆变换加上排列,也就是component-wise invertible transformation and a permutation。
证明
问题简化

证明的目标是 h : = f ^ − 1 ∘ f h := \hat{f}^{-1} \circ f h:=f^1f 为源s的permutation with component-wise invertible变换。也就是: f ^ = f ∘ h − 1 ( s ) \hat{f} = f \circ h^{-1}(s) f^=fh1(s). 假设 D ( s ) D(s) D(s) 表示一个对角矩阵, P P P 表示一个排列变换矩阵。通过使用链式法则, 我们可以把 f ^ = f ∘ h − 1 ( s ) \hat{f} = f \circ h^{-1}(s) f^=fh1(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^)=Jfh1(h(s))=Jfg1P1(Pg(s))=Jfg1(P1Pg(s))JP1(Pg(s))=Jfg1(g(s))JP1(Pg(s))=Jf(g1(g(s)))Jg1(g(s))JP1(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\}_{\ell=1}^{|\mathcal{F}_{i, :}|} = \mathbb{R}^n_{\mathcal{F}_{i, :}} \tag{4} span{Jf(s())i}=1Fi,=RFi,n(4)

由于 { J f ( s ( ℓ ) ) i } ℓ = 1 ∣ F i , : ∣ \{J_f(s^{(\ell)})_i\}_{\ell=1}^{|\mathcal{F}_{i, :}|} {Jf(s())i}=1Fi, 形成了 R F i , : n \mathbb{R}^n_{\mathcal{F}_{i, :}} RFi,n 的一组基,对于任意 j 0 ∈ F i , : j_0 \in \mathcal{F}_{i, :} j0Fi,,我们可以将热独向量 e j 0 ∈ R F i , : n e_{j_0} \in \mathbb{R}^n_{\mathcal{F}_{i, :}} ej0RFi,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,:TRF^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} jFi,,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_{i=1}^n T(s)_{i,\sigma(i)}\} \neq 0. \tag{9} det(T(s))=σSn{sgn(σ)i=1nT(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_{i=1}^n T(s)_{i,\sigma(i)} \neq 0. \tag{10} σSn,i{1,,n},sgn(σ)i=1nT(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} j1=j2,τ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 j1=j2,我们可以假设 j 3 ≠ j 1 j_3 \neq j_1 j3=j1 而不失一般性(矩阵通常很大, j 3 = j 1 j_3 = j_1 j3=j1 只是概率非常非常小的一种情况,概率小到 1 n \frac{1}{n} n1)。

根据假设 iv, 存在 j 1 ∈ C j 1 j_1 \in C_{j_1} j1Cj1 使得:

⋂ i ∈ C j 1 F i , : = { j 1 } . (17) \bigcap_{i \in C_{j_1}} \mathcal{F}_{i, :} = \{j_1\}. \tag{17} iCj1Fi,:={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}=iCj1Fi,:,(18)

那么一定存在 i 3 ∈ C j 1 i_3 \in C_{j_1} i3Cj1 使得:

j 3 ∉ F i 3 , : (19) j_3 \not\in \mathcal{F}_{i_3, :} \tag{19} j3Fi3,:(19)

因为 j 1 ∈ F i 3 , : j_1 \in \mathcal{F}_{i_3, :} j1Fi3,:,我们有 ( 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 mn. 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|} ACRm×C represents a submatrix of A ∈ R m × n A \in \mathbb{R}^{m \times n} ARm×n consisting of columns with indices C C C. Then, for all k ∈ C k \in C kC, 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|. kCsupp(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.

![[Pasted image 20231122193737.png]]

理论拆解:
  1. 第一条:保证了混合矩阵的结构足够复杂,不是特殊的单一结构。
  2. 第二条:L0正则化表示的是矩阵中不为0的点的数量。这条表示预测的混合矩阵越稀疏越好。
  3. 第三条:support的并集(按行求并,也就是向行投影)中support的数量 - 行重叠子矩阵的秩 > 每一列的support support数量。假设的目的是:每个source影响的观测越少越好,source共同作用越小越好。图中是一个例子, k = 1 k = 1 k=1 并且 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. kCsupp(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{(黑点的数量)}, kCsupp(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^T=I_s} \|AU\|_0,\tag{1} U^:=argURs×s,UUT=IsminAU0,(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'} iIj成立,并且 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^1U^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^j0=AU^j0= iIjAiU^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} iIjAiU^i,j 0 iIjsupp(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} iIj,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} iIjAiU^i,j 0>supp(Ai)=Ai0= AiU^i,j 0.(4)

然后我们可以构造 U ~ : = [ U ~ 1 … U ~ s ] \tilde{U} := \begin{bmatrix} \tilde{U}_1 & \ldots & \tilde{U}_s \end{bmatrix} U~:=[U~1U~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' j=j 并且 U ^ i , j ≠ 0 \hat{U}_{i,j} \neq 0 U^i,j=0的列 U ~ j \tilde{U}_{j} U~j,我们设 U ~ i , j = 1 \tilde{U}_{i,j} = 1 U~i,j=1。因此:

∥ 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,j=j,j=j.(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 jJ,设 U ^ i , j = 1 \hat{U}_{i,j} = 1 U^i,j=1,其中 i j i_j ij 是列 U j U_{j} Uj 中对应的非零项的唯一索引。对于其他 j ∉ J j \not\in J jJ 并且 U i , j ≠ 0 U_{i,j} \neq 0 Ui,j=0的列 U j U_{j} Uj,设 U i , j = 1 U_{i,j} = 1 Ui,j=1。则有:

{ ∥ 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^j0AU^j0>AU~j0,=AU~j0,jJ,j/J.

如前所述,每个列索引 j j j 对应一个唯一的行索引。 U ~ \tilde{U} U~ 是一个置换矩阵且 U ~ U ~ T = I s \tilde{U}\tilde{U}^T = I_s U~U~T=Is。因此有:

∥ 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

  1. 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.

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/201799.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

电子学会C/C++编程等级考试2022年12月(一级)真题解析

C/C++等级考试(1~8级)全部真题・点这里 第1题:加一 输入一个整数x,输出这个整数加1后的值,即x+1的值。 时间限制:1000 内存限制:65536输入 一个整数x(0 ≤ x ≤ 1000)。输出 按题目要求输出一个整数。样例输入 9样例输出 10 答案: //参考答案: #include<bits/st…

Linux中的进程程序替换

Linux中的进程程序替换 1. 替换原理2. 替换函数3. 函数解释4. 命名理解程序替换的意义 1. 替换原理 替换原理 用fork创建子进程后执行的是和父进程相同的程序(但有可能执行不同的代码分支),子进程往往要调用一种exec函数以执行另一个程序。当进程调用一种exec函数时,该进程的…

C++ DAY08 异常

概念 异常事件&#xff08;如&#xff1a;除 0 溢出&#xff0c;数组下标越界&#xff0c;所要读取的文件不存在 , 空指针&#xff0c;内存不足 等等&#xff09; 在 C 语言对错误的处理是两种方法&#xff1a; 一是使用整型的返回值标识错误&#xff1b; 二是使用 errn…

含分布式电源的配电网可靠性评估(matlab代码)

1主要内容 该程序参考《基于仿射最小路法的含分布式电源配电网可靠性分析》文献方法&#xff0c;通过概率模型和时序模型分别进行建模&#xff0c;实现基于概率模型最小路法的含分布式电源配电网可靠性评估以及时序模型序贯蒙特卡洛模拟法的含分布式电源配电网可靠性评估。程序…

【docker】docker总结

一、Docker简介 Docker是开源应用容器引擎&#xff0c;轻量级容器技术。基于Go语言&#xff0c;并遵循Apache2.0协议开源Docker可以让开发者打包他们的应用以及依赖包到一个轻量级、可移植的容器中&#xff0c;然后发布到任何流行的Linux系统上&#xff0c;也可以实现虚拟化容…

基于STM32的色彩识别与分类算法优化

基于STM32的色彩识别与分类算法优化是一项与图像处理和机器学习相关的研究任务&#xff0c;旨在实现高效的色彩识别和分类算法在STM32微控制器上的运行。本文将介绍基于STM32的色彩识别与分类算法优化的原理和实现步骤&#xff0c;并提供相应的代码示例。 1. 色彩识别与分类概…

MongoDB的常用操作以及python连接MongoDB

一,MongoDB的启动 mongod --dbpath..\data\db mongodb注意同时开两个窗口&#xff0c;不要关&#xff01; 二, MongoDB的简单使用 简单介绍一下mongoDB中一些操作 show dbs: 显示所有数据库 show databases: 显示所有数据库 use xxxx: 使用指定数据库/创建数据库&#xff08…

OpenCvSharp从入门到实践-(02)图像处理的基本操作

目录 图像处理的基础操作 1、读取图像 1.1、读取当前目录下的图像 2、显示图像 2.1、Cv2.ImShow 用于显示图像。 2.2、Cv2.WaitKey方法用于等待用户按下键盘上按键的时间。 2.3、Cv2.DestroyAllWindows方法用于销毁所有正在显示图像的窗口。 2.4实例1-显示图像 2.4实例…

机器人算法—ROS TF坐标变换

1.TF基本概念 &#xff08;1&#xff09;什么是TF&#xff1f; TF是Transformations Frames的缩写。在ROS中&#xff0c;是一个工具包&#xff0c;提供了坐标转换等方面的功能。 tf工具包&#xff0c;底层实现采用的是一种树状数据结构&#xff0c;根据时间缓冲并维护多个参考…

No matching variant of com.android.tools.build:gradle:7.4.2 was found.

一、报错信息 创建个新项目&#xff0c;运行直接报错&#xff0c;信息如下&#xff1a; No matching variant of com.android.tools.build:gradle:7.4.2 was found. The consumer was configured to find a runtime of a library compatible with Java 8, packaged as a jar,…

Visual Studio连接unity编辑器_unity基础开发教程

Visual Studio连接unity编辑器 问题描述解决方法意外情况 问题描述 当我们在unity编辑器中打开C#脚本的时候发现Visual Studio没有连接unity编辑器&#xff0c;在编写代码的时候也没有unity关键字的提醒。 简单来说就是敲代码没有代码提示。 解决方法 这时候需要在unity中进行…

数字逻辑电路基础-时序逻辑电路之锁存器

文章目录 一、锁存器简介二、verilog源码三、综合及仿真结果 一、锁存器简介 本文介绍数字逻辑电路中一种常用的基础时序逻辑电路-锁存&#xff0c;顾名思义&#xff0c;它的功能就是将输入在控制信号有效时透明传输到输出端&#xff0c;当控制信号无效时&#xff0c;输出值保…

Tomcat实现WebSocket即时通讯 Java实现WebSocket的两种方式

HTTP协议是“请求-响应”模式&#xff0c;浏览器必须先发请求给服务器&#xff0c;服务器才会响应该请求。即服务器不会主动发送数据给浏览器。 实时性要求高的应用&#xff0c;如在线游戏、股票实时报价和在线协同编辑等&#xff0c;浏览器需实时显示服务器的最新数据&#x…

【高级网络程序设计】Week2-3 HTML

一、The Basics 1. HTML&HTML file HTMLMarkup languageHyper Text Markup LanguageHTML fileText file with markup tags.htm/.html extension Create an html file Open an editor Type: <html><head><titile><body> Save it as .html Open i…

Redis-Redis缓存高可用集群

1、Redis集群方案比较 哨兵模式 在redis3.0以前的版本要实现集群一般是借助哨兵sentinel工具来监控master节点的状态&#xff0c;如果master节点异常&#xff0c;则会做主从切换&#xff0c;将某一台slave作为master&#xff0c;哨兵的配置略微复杂&#xff0c;并且性能和高可…

Android手机如何用Charles抓包HTTPS接口

对Charles的安装和使用&#xff0c;这里就不重复介绍了&#xff0c;之前有介绍Charles工具。 本文重点介绍在Android手机上如何配置抓包环境 1.获取Charles配置 去Help -> SSL Proxying -> Install Charles Root Certificate on a Mobile Device or Remote Browser 查…

JMeter处理接口签名sign

写接口脚本的时候&#xff0c;很多接口涉及到签名&#xff0c;今天介绍下用JMeter编写签名脚本的方法。 举个例子&#xff0c;开启红包接口&#xff0c;请求方式为post POST /v1/api/red/open json请求参数 { "red_id":1, "timestamp":"1667033841…

详解StringBuilder和StringBuffer(区别,使用方法,含源码讲解)

目录 一.为什么要使用StringBuilder和StringBuffer 字符串的不可变性 性能损耗 二.StringBuilder和StringBuffer StringBuffer源码讲解 使用方式 三.常用方法总结 示例&#xff1a; 四.StringBuilder和StringBuffer的区别 一.为什么要使用StringBuilder和StringBuffe…

【技巧】PDF文件如何编辑?

日常办公中我们经常会用到PDF文件&#xff0c;PDF具备很好的兼容性、稳定性及安全性&#xff0c;但却不容易编辑&#xff0c;那PDF要如何编辑呢&#xff1f; 如果打开PDF文件就只是只读的性质&#xff0c;说明文件是在线打开&#xff0c;或者通过PDF阅读器打开的&#xff0c;这…

pikachu靶场Table pikachu.member doesn’t exist:解决

背景&#xff1a; 第一次搭建pikachu靶场&#xff0c;搭建好后访问index.php后&#xff0c;尝试练习&#xff0c;发现界面显示Table pikachu.member doesn t exist&#xff0c;后来找了很多教程&#xff0c;没有解决&#xff0c;后来发现是自己没有进行初始化&#xff0c;给大家…