压缩感知的核心问题和基础理论 2025-11-04
压缩感知（Compressive Sensing）问题的核心在于：如何从y = A x y = A x y = A x s-稀疏（s-sparse） 向量 x x x
其中，A ∈ C m × N A \in \mathbb{C}^{m \times N} A ∈ C m × N 测量矩阵（measurement matrix） ，且 m < N m < N m < N x x x
核心问题在于两种不同的情境：
测量方案是否应当允许对所有 s s s x ∈ C N x \in \mathbb{C}^N x ∈ C N 进行重建；
或者，我们仅要求：给定某个特定的 s s s x ∈ C N x \in \mathbb{C}^N x ∈ C N
第二种情形乍看之下似乎不自然，因为向量 x x x A A A x x x m m m
在第一种情况下，m = 2 s m = 2s m = 2 s
在第二种情况下，m = s + 1 m = s + 1 m = s + 1
如果还要求重建方案稳定（stable） （此处的“稳定”含义稍后会更精确定义），则所需的最小测量数还会额外包含一个 ln ( N / s ) \ln(N/s) ln ( N / s ) 2 s 2s 2 s
在区分上述两种情境之前，值得注意以下两个性质的等价性：
(a) 若 x ∈ C N x \in \mathbb{C}^N x ∈ C N A z = y A z = y A z = y s s s { z ∈ C N : A z = A x , ∥ z ∥ 0 ≤ s } = { x } . \{ z \in \mathbb{C}^N : A z = A x, \| z \|_0 \le s \} = \{ x \}. { z ∈ C N : A z = A x , ∥ z ∥ 0 ≤ s } = { x } .
(b) 向量 x ∈ C N x \in \mathbb{C}^N x ∈ C N
min z ∈ C N ∥ z ∥ 0 subject to A z = y . (P0) \min_{z \in \mathbb{C}^N} \| z \|_0 \quad \text{subject to} \quad A z = y. \tag{P0} z ∈ C N min ∥ z ∥ 0 subject to A z = y . ( P0 ) 事实上，如果 x ∈ C N x \in \mathbb{C}^N x ∈ C N A z = y A z = y A z = y s s s x # x^\# x # s s s A x # = y A x^\# = y A x # = y x # = x x^\# = x x # = x
在给出这一情形的主要结果之前，我们首先注意到：欠定线性系统中稀疏解的唯一性可以通过多种方式重新表述。
关键记号
设 A ∈ C m × N A \in \mathbb{C}^{m \times N} A ∈ C m × N S ⊂ [ N ] S \subset [N] S ⊂ [ N ]
子矩阵 A S A_S A S ：我们用记号 A S A_S A S A A A S S S 子向量 x S x_S x S ：对于 x ∈ C N x \in \mathbb{C}^N x ∈ C N x S x_S x S x x x S S S S S S C N \mathbb{C}^N C N
定理 1 (唯一性与零空间)
设 A ∈ C m × N A \in \mathbb{C}^{m \times N} A ∈ C m × N
(a) 每个 s s s x ∈ C N x \in \mathbb{C}^N x ∈ C N A z = A x A z = A x A z = A x s s s A x = A z A x = A z A x = A z x , z x, z x , z s s s x = z x = z x = z
(b) 矩阵 A A A 2 s 2s 2 s ker A ∩ { z ∈ C N : ∥ z ∥ 0 ≤ 2 s } = { 0 } . \ker A \cap \{ z \in \mathbb{C}^N : \|z\|_0 \le 2s \} = \{ 0 \}. ker A ∩ { z ∈ C N : ∥ z ∥ 0 ≤ 2 s } = { 0 } .
(c) 对任意满足 card ( S ) ≤ 2 s \text{card}(S) \le 2s card ( S ) ≤ 2 s S ⊂ [ N ] S \subset [N] S ⊂ [ N ] A S A_S A S 单射的（injective） 。
(d) 矩阵 A A A 2 s 2s 2 s
证明：
(a) ⇔ (b)： 设 x , z x, z x , z s s s A x = A z A x = A z A x = A z x − z x - z x − z 2 s 2s 2 s A ( x − z ) = 0 A(x - z) = 0 A ( x − z ) = 0 ker A \ker A ker A 2 s 2s 2 s x = z x = z x = z s s s x x x { z ∈ C N : A z = A x , ∥ z ∥ 0 ≤ s } = { x } , \{ z \in \mathbb{C}^N : A z = A x, \|z\|_0 \le s \} = \{x\}, { z ∈ C N : A z = A x , ∥ z ∥ 0 ≤ s } = { x } , v ∈ ker A v \in \ker A v ∈ ker A 2 s 2s 2 s v = x − z v = x - z v = x − z x , z x, z x , z s s s supp ( x ) ∩ supp ( z ) = ∅ \text{supp}(x) \cap \text{supp}(z) = \emptyset supp ( x ) ∩ supp ( z ) = ∅ A x = A z A x = A z A x = A z x = z x = z x = z v = 0 v = 0 v = 0
(b) ⇔ (c) ⇔ (d)： 对任意 2 s 2s 2 s v v v S = supp ( v ) S = \text{supp}(v) S = supp ( v ) A v = A S v S A v = A_S v_S A v = A S v S S S S card ( S ) ≤ 2 s \text{card}(S) \le 2s card ( S ) ≤ 2 s v v v 2 s 2s 2 s A S A_S A S A A A 2 s 2s 2 s
注（最小测量数）：
我们特别注意到： 若希望从测量向量 y = A x ∈ C m y = A x \in \mathbb{C}^m y = A x ∈ C m s s s x ∈ C N x \in \mathbb{C}^N x ∈ C N rank ( A ) ≥ 2 s . \text{rank}(A) \ge 2s. rank ( A ) ≥ 2 s . m m m m ≥ 2 s . m \ge 2s. m ≥ 2 s .
定理 2 (Vandermonde 矩阵构造)
对于任意整数 N ≥ 2 s N \ge 2s N ≥ 2 s A ∈ C m × N A \in \mathbb{C}^{m \times N} A ∈ C m × N m = 2 s m = 2s m = 2 s s s s x ∈ C N x \in \mathbb{C}^N x ∈ C N y = A x ∈ C m y = A x \in \mathbb{C}^m y = A x ∈ C m x x x
证明：
令 t N > t N − 1 > ⋯ > t 2 > t 1 > 0 t_N > t_{N-1} > \cdots > t_2 > t_1 > 0 t N > t N − 1 > ⋯ > t 2 > t 1 > 0 A ∈ C m × N A \in \mathbb{C}^{m \times N} A ∈ C m × N m = 2 s m = 2s m = 2 s
A = [ 1 1 ⋯ 1 t 1 t 2 ⋯ t N ⋮ ⋮ ⋱ ⋮ t 1 2 s − 1 t 2 2 s − 1 ⋯ t N 2 s − 1 ] . (2) A = \begin{bmatrix} 1 & 1 & \cdots & 1 \\ t_1 & t_2 & \cdots & t_N \\ \vdots & \vdots & \ddots & \vdots \\ t_1^{2s-1} & t_2^{2s-1} & \cdots & t_N^{2s-1} \end{bmatrix}. \tag{2} A = 1 t 1 ⋮ t 1 2 s − 1 1 t 2 ⋮ t 2 2 s − 1 ⋯ ⋯ ⋱ ⋯ 1 t N ⋮ t N 2 s − 1 . ( 2 ) 取一个指标集合 S = { j 1 < j 2 < ⋯ < j 2 s } S = \{ j_1 < j_2 < \cdots < j_{2s} \} S = { j 1 < j 2 < ⋯ < j 2 s } A S ∈ C 2 s × 2 s A_S \in \mathbb{C}^{2s \times 2s} A S ∈ C 2 s × 2 s
det ( A S ) = ∣ 1 1 ⋯ 1 t j 1 t j 2 ⋯ t j 2 s ⋮ ⋮ ⋱ ⋮ t j 1 2 s − 1 t j 2 2 s − 1 ⋯ t j 2 s 2 s − 1 ∣ = ∏ k < ℓ ( t j ℓ − t j k ) > 0. \det(A_S) = \begin{vmatrix} 1 & 1 & \cdots & 1 \\ t_{j_1} & t_{j_2} & \cdots & t_{j_{2s}} \\ \vdots & \vdots & \ddots & \vdots \\ t_{j_1}^{2s-1} & t_{j_2}^{2s-1} & \cdots & t_{j_{2s}}^{2s-1} \end{vmatrix} = \prod_{k < \ell} (t_{j_\ell} - t_{j_k}) > 0. det ( A S ) = 1 t j 1 ⋮ t j 1 2 s − 1 1 t j 2 ⋮ t j 2 2 s − 1 ⋯ ⋯ ⋱ ⋯ 1 t j 2 s ⋮ t j 2 s 2 s − 1 = k < ℓ ∏ ( t j ℓ − t j k ) > 0. 这表明 A S A_S A S 可逆的 ，从而是单射的（injective）。由于定理 1 的条件 (c) 得到满足，每个 s s s x ∈ C N x \in \mathbb{C}^N x ∈ C N A z = A x A z = A x A z = A x s s s
拓展讨论：其他矩阵构造 许多其他矩阵同样满足定理 1 的条件 (c)。
完全正矩阵 (Totally Positive Matrix) ：t 1 , … , t N t_1, \ldots, t_N t 1 , … , t N 0 , 1 , … , 2 s − 1 0, 1, \ldots, 2s-1 0 , 1 , … , 2 s − 1 t N > ⋯ > t 1 > 0 t_N > \cdots > t_1 > 0 t N > ⋯ > t 1 > 0 M ∈ R N × N M \in \mathbb{R}^{N \times N} M ∈ R N × N I , J ⊂ [ N ] I, J \subset [N] I , J ⊂ [ N ] M I , J M_{I,J} M I , J det M I , J > 0 \det M_{I,J} > 0 det M I , J > 0 M I , J M_{I,J} M I , J I I I J J J M M M m = 2 s m = 2s m = 2 s I I I A A A 2 s 2s 2 s S ⊂ [ N ] S \subset [N] S ⊂ [ N ] A S A_S A S M I , S M_{I,S} M I , S
部分傅里叶矩阵 (Partial Fourier Matrix) ：t N , … , t 1 t_N, \ldots, t_1 t N , … , t 1 det ( A S ) ≠ 0 \det(A_S) \ne 0 det ( A S ) = 0 det ( A S ) > 0 \det(A_S) > 0 det ( A S ) > 0 t ℓ = e i 2 π ( ℓ − 1 ) / N , ℓ ∈ [ N ] , t_\ell = e^{i 2\pi (\ell - 1)/N}, \quad \ell \in [N], t ℓ = e i 2 π ( ℓ − 1 ) / N , ℓ ∈ [ N ] ,
A = [ 1 1 1 ⋯ 1 1 e i 2 π / N e i 2 π 2 / N ⋯ e i 2 π ( N − 1 ) / N ⋮ ⋮ ⋮ ⋱ ⋮ 1 e i 2 π ( 2 s − 1 ) / N e i 2 π ( 2 s − 1 ) 2 / N ⋯ e i 2 π ( 2 s − 1 ) ( N − 1 ) / N ] A = \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & e^{i 2\pi /N} & e^{i 2\pi 2 /N} & \cdots & e^{i 2\pi (N-1)/N} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & e^{i 2\pi (2s-1)/N} & e^{i 2\pi (2s-1)2/N} & \cdots & e^{i 2\pi (2s-1)(N-1)/N} \end{bmatrix} A = 1 1 ⋮ 1 1 e i 2 π / N ⋮ e i 2 π ( 2 s − 1 ) / N 1 e i 2 π 2/ N ⋮ e i 2 π ( 2 s − 1 ) 2/ N ⋯ ⋯ ⋱ ⋯ 1 e i 2 π ( N − 1 ) / N ⋮ e i 2 π ( 2 s − 1 ) ( N − 1 ) / N 同样允许从 y = A x ∈ C 2 s y = A x \in \mathbb{C}^{2s} y = A x ∈ C 2 s s s s x ∈ C N x \in \mathbb{C}^N x ∈ C N
关于 (P0) 的可行性 事实上，与定理 2 的证明类似的论证表明：对于任意满足 det ( A S ) = 0 \det(A_S) = 0 det ( A S ) = 0 S ⊂ [ N ] S \subset [N] S ⊂ [ N ] card ( S ) ≤ 2 s \text{card}(S) \le 2s card ( S ) ≤ 2 s ( 2 s ) × N (2s) \times N ( 2 s ) × N 大多数 ( 2 s ) × N (2s) \times N ( 2 s ) × N y = A x ∈ C 2 s y = A x \in \mathbb{C}^{2s} y = A x ∈ C 2 s s s s x ∈ C N x \in \mathbb{C}^N x ∈ C N
一般而言，直接求解 (P₀) 的重建过程在实践中不可行（即这是一个NP-Hard的问题），但在傅里叶测量的情形下，可以使用基于 Prony 方法（Prony’s method） 的更优重建方案。
定理 3 (Prony 方法与可行重建)
对于任意 N ≥ 2 s N \ge 2s N ≥ 2 s 可行的重建方法 ，可从前 m = 2 s m = 2s m = 2 s s s s
证明：
设 x ∈ C N x \in \mathbb{C}^N x ∈ C N s s s { 0 , 1 , … , N − 1 } \{0, 1, \ldots, N-1\} { 0 , 1 , … , N − 1 } S ⊂ { 0 , 1 , … , N − 1 } S \subset \{0,1,\ldots,N-1\} S ⊂ { 0 , 1 , … , N − 1 } ∣ S ∣ = s |S| = s ∣ S ∣ = s 2 s 2s 2 s x ^ ( j ) : = ∑ k = 0 N − 1 x ( k ) e − i 2 π j k / N , 0 ≤ j ≤ N − 1. \hat{x}(j) := \sum_{k=0}^{N-1} x(k)e^{-i2\pi jk/N}, \quad 0 \le j \le N-1. x ^ ( j ) := ∑ k = 0 N − 1 x ( k ) e − i 2 πjk / N , 0 ≤ j ≤ N − 1. s s s p ( t ) : = ∏ k ∈ S ( 1 − e − i 2 π k / N e i 2 π t / N ) . p(t) := \prod_{k \in S} (1 - e^{-i2\pi k/N} e^{i2\pi t/N}). p ( t ) := ∏ k ∈ S ( 1 − e − i 2 πk / N e i 2 π t / N ) . t ∈ S t \in S t ∈ S p p p p ^ \hat{p} p ^ S S S
由于 x x x S ‾ \overline{S} S 0 ≤ t ≤ N − 1 0 \le t \le N-1 0 ≤ t ≤ N − 1 p ( t ) x ( t ) = 0. p(t)x(t) = 0. p ( t ) x ( t ) = 0. p ^ ∗ x ^ = 0 , \hat{p} * \hat{x} = 0, p ^ ∗ x ^ = 0 ,
( p ^ ∗ x ^ ) ( j ) : = ∑ k = 0 N − 1 p ^ ( k ) x ^ ( j − k m o d N ) = 0 , ∀ 0 ≤ j ≤ N − 1. (2.6) (\hat{p} * \hat{x})(j) := \sum_{k=0}^{N-1} \hat{p}(k)\hat{x}(j - k \bmod N) = 0, \quad \forall 0 \le j \le N-1. \tag{2.6} ( p ^ ∗ x ^ ) ( j ) := k = 0 ∑ N − 1 p ^ ( k ) x ^ ( j − k mod N ) = 0 , ∀0 ≤ j ≤ N − 1. ( 2.6 ) 由于 p p p s s s p ^ ( 0 ) = 1 , p ^ ( k ) = 0 对于 k > s . \hat{p}(0) = 1, \quad \hat{p}(k) = 0 \text{ 对于 } k > s. p ^ ( 0 ) = 1 , p ^ ( k ) = 0 对于 k > s . p ^ ( 1 ) , … , p ^ ( s ) \hat{p}(1), \ldots, \hat{p}(s) p ^ ( 1 ) , … , p ^ ( s ) s ≤ j ≤ 2 s − 1 s \le j \le 2s-1 s ≤ j ≤ 2 s − 1
x ^ ( s ) + p ^ ( 1 ) x ^ ( s − 1 ) + ⋯ + p ^ ( s ) x ^ ( 0 ) = 0 , x ^ ( s + 1 ) + p ^ ( 1 ) x ^ ( s ) + ⋯ + p ^ ( s ) x ^ ( 1 ) = 0 , ⋮ x ^ ( 2 s − 1 ) + p ^ ( 1 ) x ^ ( 2 s − 2 ) + ⋯ + p ^ ( s ) x ^ ( s − 1 ) = 0. \begin{aligned} \hat{x}(s) + \hat{p}(1)\hat{x}(s-1) + \cdots + \hat{p}(s)\hat{x}(0) &= 0, \\ \hat{x}(s+1) + \hat{p}(1)\hat{x}(s) + \cdots + \hat{p}(s)\hat{x}(1) &= 0, \\ &\vdots \\ \hat{x}(2s-1) + \hat{p}(1)\hat{x}(2s-2) + \cdots + \hat{p}(s)\hat{x}(s-1) &= 0. \end{aligned} x ^ ( s ) + p ^ ( 1 ) x ^ ( s − 1 ) + ⋯ + p ^ ( s ) x ^ ( 0 ) x ^ ( s + 1 ) + p ^ ( 1 ) x ^ ( s ) + ⋯ + p ^ ( s ) x ^ ( 1 ) x ^ ( 2 s − 1 ) + p ^ ( 1 ) x ^ ( 2 s − 2 ) + ⋯ + p ^ ( s ) x ^ ( s − 1 ) = 0 , = 0 , ⋮ = 0. 即矩阵形式为：
[ x ^ ( s − 1 ) x ^ ( s − 2 ) ⋯ x ^ ( 0 ) x ^ ( s ) x ^ ( s − 1 ) ⋯ x ^ ( 1 ) ⋮ ⋮ ⋱ ⋮ x ^ ( 2 s − 2 ) x ^ ( 2 s − 3 ) ⋯ x ^ ( s − 1 ) ] [ p ^ ( 1 ) p ^ ( 2 ) ⋮ p ^ ( s ) ] = − [ x ^ ( s ) x ^ ( s + 1 ) ⋮ x ^ ( 2 s − 1 ) ] . \begin{bmatrix} \hat{x}(s-1) & \hat{x}(s-2) & \cdots & \hat{x}(0) \\ \hat{x}(s) & \hat{x}(s-1) & \cdots & \hat{x}(1) \\ \vdots & \vdots & \ddots & \vdots \\ \hat{x}(2s-2) & \hat{x}(2s-3) & \cdots & \hat{x}(s-1) \end{bmatrix} \begin{bmatrix} \hat{p}(1) \\ \hat{p}(2) \\ \vdots \\ \hat{p}(s) \end{bmatrix} = - \begin{bmatrix} \hat{x}(s) \\ \hat{x}(s+1) \\ \vdots \\ \hat{x}(2s-1) \end{bmatrix}. x ^ ( s − 1 ) x ^ ( s ) ⋮ x ^ ( 2 s − 2 ) x ^ ( s − 2 ) x ^ ( s − 1 ) ⋮ x ^ ( 2 s − 3 ) ⋯ ⋯ ⋱ ⋯ x ^ ( 0 ) x ^ ( 1 ) ⋮ x ^ ( s − 1 ) p ^ ( 1 ) p ^ ( 2 ) ⋮ p ^ ( s ) = − x ^ ( s ) x ^ ( s + 1 ) ⋮ x ^ ( 2 s − 1 ) . 由于 x ^ ( 0 ) , … , x ^ ( 2 s − 1 ) \hat{x}(0), \ldots, \hat{x}(2s-1) x ^ ( 0 ) , … , x ^ ( 2 s − 1 ) p ^ ( 1 ) , … , p ^ ( s ) \hat{p}(1), \ldots, \hat{p}(s) p ^ ( 1 ) , … , p ^ ( s ) x = [ 1 , 0 , … , 0 ] ⊤ x = [1,0,\ldots,0]^\top x = [ 1 , 0 , … , 0 ] ⊤ q ^ ( 1 ) , … , q ^ ( s ) \hat{q}(1), \ldots, \hat{q}(s) q ^ ( 1 ) , … , q ^ ( s ) q ^ ( 0 ) = 1 , q ^ ( k ) = 0 \hat{q}(0) = 1, \hat{q}(k) = 0 q ^ ( 0 ) = 1 , q ^ ( k ) = 0 k > s k > s k > s ( q ^ ∗ x ^ ) ( j ) = 0 , s ≤ j ≤ 2 s − 1. (\hat{q} * \hat{x})(j) = 0, \quad s \le j \le 2s-1. ( q ^ ∗ x ^ ) ( j ) = 0 , s ≤ j ≤ 2 s − 1. s s s q ⋅ x q \cdot x q ⋅ x q ⋅ x ^ = q ^ ∗ x ^ \widehat{q \cdot x} = \hat{q} * \hat{x} q ⋅ x = q ^ ∗ x ^ s s s
由此可得 q ⋅ x = 0 q \cdot x = 0 q ⋅ x = 0 q q q S S S q q q s s s S S S
因此，我们可以通过以下方式恢复 S S S
求解 p ( t ) = 0 p(t) = 0 p ( t ) = 0
或找出 ∣ p ( j ) ∣ |p(j)| ∣ p ( j ) ∣ s s s
最后，通过前 2 s 2s 2 s x ( j ) , j ∈ S x(j), \quad j \in S x ( j ) , j ∈ S
注（Prony 方法的局限性）：
尽管此重建过程在理论上优雅，但存在重要缺陷：它对稀疏性误差不稳定，也不具备对测量误差的鲁棒性。
我们将在第 11 章证明：任何稳定的 s s s m ≈ c s ln ( e N / s ) m \approx c\, s \ln(eN/s) m ≈ c s ln ( e N / s ) c > 0 c > 0 c > 0
在这一设定下，s s s x ∈ C N x \in \mathbb{C}^N x ∈ C N 事先固定的 ，随后才选择测量矩阵 A ∈ C m × N A \in \mathbb{C}^{m \times N} A ∈ C m × N x x x y = A x y = A x y = A x s s s A A A x x x x x x A A A ( s + 1 ) × N (s+1) \times N ( s + 1 ) × N
定理 4 (固定向量的恢复)
对于任意 N ≥ s + 1 N \ge s + 1 N ≥ s + 1 s s s x ∈ C N x \in \mathbb{C}^N x ∈ C N m = s + 1 m = s + 1 m = s + 1 A ∈ C m × N A \in \mathbb{C}^{m \times N} A ∈ C m × N x x x y = A x ∈ C m y = A x \in \mathbb{C}^m y = A x ∈ C m x x x
证明：
设 A ∈ C ( s + 1 ) × N A \in \mathbb{C}^{(s+1) \times N} A ∈ C ( s + 1 ) × N 不能 通过 ℓ 0 \ell_0 ℓ 0 y = A x y = A x y = A x s s s x x x x x x z ∈ C N z \in \mathbb{C}^N z ∈ C N S = supp ( z ) = { j 1 , … , j s } S = \text{supp}(z) = \{ j_1, \ldots, j_s \} S = supp ( z ) = { j 1 , … , j s } A z = A x A z = A x A z = A x ∥ z ∥ 0 < s \|z\|_0 < s ∥ z ∥ 0 < s S S S s s s A ( z − x ) = 0. A(z - x) = 0. A ( z − x ) = 0.
情况 1： 若 supp ( x ) ⊂ S \text{supp}(x) \subset S supp ( x ) ⊂ S ( A ( z − x ) ) [ S ] = 0 , (A(z - x))_{[S]} = 0, ( A ( z − x ) ) [ S ] = 0 , A S A_S A S f ( a 1 , 1 , … , a m , N ) : = det ( A S ) = 0. f(a_{1,1}, \ldots, a_{m,N}) := \det(A_S) = 0. f ( a 1 , 1 , … , a m , N ) := det ( A S ) = 0.
情况 2： 若 supp ( x ) ⊄ S \text{supp}(x) \not\subset S supp ( x ) ⊂ S V : = { u ∈ C N : supp ( u ) ⊂ S } + C x , V := \{ u \in \mathbb{C}^N : \text{supp}(u) \subset S \} + \mathbb{C}x, V := { u ∈ C N : supp ( u ) ⊂ S } + C x , s + 1 s + 1 s + 1 G : V → C s + 1 G : V \to \mathbb{C}^{s+1} G : V → C s + 1 v ↦ A v v \mapsto A v v ↦ A v 不可逆的 ，因为 G ( z − x ) = 0 G(z - x) = 0 G ( z − x ) = 0 G G G ( e j 1 , … , e j s , x ) (e_{j_1}, \ldots, e_{j_s}, x) ( e j 1 , … , e j s , x )
B x , S : = [ a 1 , j 1 ⋯ a 1 , j s ∑ j ∈ supp ( x ) x j a 1 , j ⋮ ⋱ ⋮ ⋮ a s + 1 , j 1 ⋯ a s + 1 , j s ∑ j ∈ supp ( x ) x j a s + 1 , j ] . B_{x,S} := \begin{bmatrix} a_{1,j_1} & \cdots & a_{1,j_s} & \sum_{j \in \text{supp}(x)} x_j a_{1,j} \\ \vdots & \ddots & \vdots & \vdots \\ a_{s+1,j_1} & \cdots & a_{s+1,j_s} & \sum_{j \in \text{supp}(x)} x_j a_{s+1,j} \end{bmatrix}. B x , S := a 1 , j 1 ⋮ a s + 1 , j 1 ⋯ ⋱ ⋯ a 1 , j s ⋮ a s + 1 , j s ∑ j ∈ supp ( x ) x j a 1 , j ⋮ ∑ j ∈ supp ( x ) x j a s + 1 , j . 定义
g S ( a 1 , 1 , … , a m , N ) : = det ( B x , S ) = 0. g_S(a_{1,1}, \ldots, a_{m,N}) := \det(B_{x,S}) = 0. g S ( a 1 , 1 , … , a m , N ) := det ( B x , S ) = 0.
这说明矩阵 A A A
( a 1 , 1 , … , a m , N ) ∈ f − 1 ( { 0 } ) ∪ ⋃ card ( S ) = s g S − 1 ( { 0 } ) . (a_{1,1}, \ldots, a_{m,N}) \in f^{-1}(\{0\}) \cup \bigcup_{\text{card}(S)=s} g_S^{-1}(\{0\}). ( a 1 , 1 , … , a m , N ) ∈ f − 1 ({ 0 }) ∪ card ( S ) = s ⋃ g S − 1 ({ 0 }) . 由于 f f f g S g_S g S f − 1 ( { 0 } ) f^{-1}(\{0\}) f − 1 ({ 0 }) g S − 1 ( { 0 } ) g_S^{-1}(\{0\}) g S − 1 ({ 0 }) A A A x x x y = A x y = A x y = A x
主题： 压缩感知, 稀疏恢复