基于线性规划的稀疏信号重构问题求解示例
问题描述
稀疏信号重构旨在从少量线性观测中恢复具有少量非零元素的信号。设原始信号 \(\mathbf{x} \in \mathbb{R}^n\) 是稀疏的（仅少数元素非零），观测向量 \(\mathbf{y} \in \mathbb{R}^m\)（\(m \ll n\)）满足 \(\mathbf{y} = \mathbf{A}\mathbf{x} + \mathbf{e}\)，其中 \(\mathbf{A} \in \mathbb{R}^{m \times n}\) 为观测矩阵，\(\mathbf{e}\) 为噪声。目标是通过 \(\mathbf{y}\) 和 \(\mathbf{A}\) 重构 \(\mathbf{x}\)。由于 \(m \ll n\)，问题欠定，需利用稀疏性先验。一种典型方法是将问题转化为线性规划：
\[\min_{\mathbf{x}} \|\mathbf{x}\|_1 \quad \text{s.t.} \quad \|\mathbf{A}\mathbf{x} - \mathbf{y}\|_\infty \leq \varepsilon, \]
其中 \(\varepsilon\) 为噪声容限，\(\|\cdot\|_1\) 和 \(\|\cdot\|_\infty\) 分别为 L1 范数和无穷范数。通过变量替换，该问题可转化为标准线性规划形式求解。
解题步骤
- 问题转化
- L1 范数 \(\|\mathbf{x}\|_1 = \sum_{i=1}^n |x_i|\) 不可微，需引入辅助变量 \(\mathbf{u} \in \mathbb{R}^n\) 满足 \(u_i \geq |x_i|\)。等价形式为：
\[ u_i \geq x_i, \quad u_i \geq -x_i, \quad u_i \geq 0 \quad (i=1,\dots,n). \]
目标函数变为 $ \min \sum_{i=1}^n u_i $。
- 无穷范数约束 \(\|\mathbf{A}\mathbf{x} - \mathbf{y}\|_\infty \leq \varepsilon\) 等价于：
\[ -\varepsilon \leq (\mathbf{A}\mathbf{x} - \mathbf{y})_j \leq \varepsilon \quad (j=1,\dots,m). \]
- 线性规划标准形式
定义决策变量 \(\mathbf{z} = [\mathbf{u}; \mathbf{x}] \in \mathbb{R}^{2n}\)，则问题可写为：
\[ \begin{aligned} \min_{\mathbf{z}} \quad & \mathbf{c}^\top \mathbf{z} \\ \text{s.t.} \quad & \mathbf{G} \mathbf{z} \leq \mathbf{h}, \end{aligned} \]
其中：
- \(\mathbf{c} = [\mathbf{1}_n; \mathbf{0}_n]\)（前 \(n\) 个分量为 1，后 \(n\) 个为 0），
- 约束矩阵 \(\mathbf{G}\) 和向量 \(\mathbf{h}\) 由以下部分构成：
- \(u_i - x_i \geq 0\) 和 \(u_i + x_i \geq 0\) 转化为 \([-1, 1]\) 和 \([-1, -1]\) 的块组合（共 \(2n\) 行），
- 观测约束 \(-\varepsilon \leq (\mathbf{A}\mathbf{x})_j - y_j \leq \varepsilon\) 转化为 \([\mathbf{0}, \mathbf{A}]\) 和 \([\mathbf{0}, -\mathbf{A}]\) 的块（共 \(2m\) 行）。
-
求解与重构
- 使用单纯形法或内点法求解上述线性规划，得到解 \(\mathbf{z}^* = [\mathbf{u}^*; \mathbf{x}^*]\)。
- 提取 \(\mathbf{x}^*\) 作为重构的稀疏信号。由于 L1 范数促进稀疏性，\(\mathbf{x}^*\) 的非零元素数量接近真实稀疏信号。
-
实例验证
生成随机稀疏信号 \(\mathbf{x}_{\text{true}}\)（非零元素占比 5%），观测矩阵 \(\mathbf{A}\) 为高斯随机矩阵，添加噪声后得到 \(\mathbf{y}\)。设置 \(\varepsilon = 0.1\)，求解线性规划后，比较 \(\mathbf{x}^*\) 与 \(\mathbf{x}_{\text{true}}\) 的误差（如均方误差），验证重构效果。
关键点
- L1 范数最小化是稀疏重构的核心，其线性规划形式可高效求解。
- 噪声容限 \(\varepsilon\) 需根据实际噪声水平调整，过大导致重构不精确，过小可能无可行解。
- 该方法在压缩感知、图像处理等领域有广泛应用。