随机化最小二乘逼近算法（Randomized Least Squares Approximation）
字数 3014 2025-12-15 01:14:40

随机化最小二乘逼近算法（Randomized Least Squares Approximation）

算法描述

本算法旨在高效求解大规模超定线性最小二乘问题。给定一个高瘦矩阵A (m×n, m >> n) 和一个向量b (m×1)，标准最小二乘问题为：

\[\min_{x} \|Ax - b\|_2^2 \]

其精确解可通过正规方程 \(A^T A x = A^T b\) 或QR分解得到，但计算成本为 \(O(mn^2)\)，对大规模矩阵过高。随机化最小二乘逼近算法通过随机投影将原问题压缩成一个规模小得多的问题，以近似解换取计算效率，典型加速到 \(O(mn \log n + n^3)\)。

解题过程

核心思想是用一个随机矩阵 \(\Omega\) 对原问题“降维”，在新空间中求解一个小规模最小二乘问题，再映射回原空间得到近似解。以下是详细步骤：

第1步：构造随机投影矩阵

  1. 目标：构造一个随机矩阵 \(\Omega\)，大小为 \(n \times l\)，其中 \(l\) 是一个略大于 \(n\) 的整数（例如 \(l = n + 10\)），用于对矩阵 \(A\) 的行空间进行采样和压缩。
  2. 选择分布：通常使用满足Johnson-Lindenstrauss引理的分布，如：
    • 高斯随机矩阵：\(\Omega\) 的元素独立同分布于标准正态分布 \(N(0, 1)\)。这是最经典的选择，理论性质好。
    • 稀疏符号随机矩阵（如Achlioptas矩阵）：元素以较大概率取0，以降低生成和乘法成本。
    • 快速变换矩阵（如Subsampled Randomized Fourier Transform, SRFT）：由离散傅里叶变换矩阵的一部分行和随机符号对角阵构成，可利用FFT实现快速乘法，成本为 \(O(m \log m)\)。
  3. 维度 \(l\) 的选取：\(l\) 是一个超参数，它控制了精度与速度的权衡。理论上，\(l\) 越大，近似解精度越高，但计算量也越大。实践中常取 \(l = n + p\)，其中 \(p\) 是一个小的“过采样”参数（如5, 10）。

第2步：形成压缩的草图矩阵

  1. 计算草图：计算压缩后的矩阵 \(S = A \Omega\)。矩阵 \(S\) 的大小是 \(m \times l\)。
  2. 计算成本：这是算法中最昂贵的步骤。如果 \(A\) 是稠密矩阵，成本是 \(O(mln)\)。如果使用SRFT等结构化随机矩阵，成本可降至 \(O(m \log m)\) 或 \(O(mn \log n)\)。如果 \(A\) 是稀疏矩阵，可以利用稀疏性加速。

第3步：计算压缩问题的QR分解

  1. 目标：对草图矩阵 \(S\) 进行QR分解，以获取原矩阵 \(A\) 列空间的一个近似正交基。
  2. 分解：计算 \(S = QR\)，其中 \(Q\) 是 \(m \times l\) 的矩阵，其列标准正交（\(Q^T Q = I_l\)），\(R\) 是 \(l \times l\) 的上三角矩阵。
  3. 几何解释：矩阵 \(Q\) 的列张成的子空间近似包含了矩阵 \(A\) 的列空间（即Range(A)）。由于 \(l > n\) 且是随机采样，这个近似在高概率下是相当好的。

第4步：投影原问题到低维空间

  1. 投影：将原最小二乘问题投影到 \(Q\) 张成的近似列空间上。这通过将原方程 \(Ax \approx b\) 近似为在 \(Q\) 的列空间上寻找最佳解来实现。
  2. 形成小规模问题：我们需要求解：

\[ \min_{y} \| Qy - b \|_2^2 \]

由于 $Q$ 的列标准正交，这个最小二乘问题的法方程简化为 $Q^T Q y = Q^T b$，即 $y = Q^T b$。因此，最优系数向量 $y^* = Q^T b$。
  1. 计算：计算 \(y = Q^T b\)，这是一个 \(l \times 1\) 的向量。

第5步：回代求解原变量

  1. 建立近似关系：我们有近似关系 \(Ax \approx Qy\)。由于 \(Q\) 近似是 \(A\) 列空间的一组基，我们假设存在一个系数向量 \(z\) 使得 \(Qy \approx A z\)。更精确地说，我们求解一个小规模的最小二乘问题来找到最佳的 \(x\) 使得 \(Ax\) 在 \(Q\) 的列空间上的投影是 \(Qy\)。
  2. 求解小规模正规方程：实际上，我们可以通过求解以下方程得到近似解 \(\tilde{x}\)：

\[ (A^T A) \tilde{x} = A^T (Q y) \]

为了避免计算 $A^T A$（可能条件数很差），我们利用 $Q$ 与 $A$ 的关系的一个有效替代。一个标准且稳定的方法是：
*   首先计算矩阵 $B = Q^T A$。$B$ 的大小是 $l \times n$。由于 $l \approx n$，这比 $A$ 小很多。
*   然后求解小型最小二乘问题：$\min_{\tilde{x}} \| B \tilde{x} - y \|_2^2$，其中 $y = Q^T b$。
  1. 求解小型问题：对 \(B\) 进行QR分解（或SVD，因其规模小）：设 \(B = U \Sigma V^T\)（经济SVD）或 \(B = \tilde{Q} \tilde{R}\)。然后解 \(\tilde{R} w = \tilde{Q}^T y\) 得到 \(w\)，最终 \(\tilde{x} = V w\)（SVD方式类似）。由于 \(B\) 是 \(l \times n\) 且 \(l \ge n\)，这个小问题的求解成本仅为 \(O(ln^2) \approx O(n^3)\)。

第6步：算法输出与误差分析

  1. 输出：算法返回近似解 \(\tilde{x}\)。
  2. 误差与可靠性：
    • 理论保证：在一定概率下（例如，对高斯随机矩阵），近似解 \(\tilde{x}\) 满足：

\[ \|A\tilde{x} - b\|_2^2 \le (1 + \epsilon) \min_{x} \|Ax - b\|_2^2 \]

    其中 $\epsilon$ 是一个与过采样参数 $p$ 和失败概率相关的小常数。这意味着目标函数值（残差范数平方）接近最优值。
*   **计算优势**：当 $m \gg n$ 时，主要计算成本是第2步形成草图 $S = A\Omega$ 和第3步对 $S$ 的QR分解（$O(ml^2)$）。与精确算法的 $O(mn^2)$ 相比，当 $l \approx n$ 时，加速显著，特别是当使用快速随机投影（如SRFT）时，可降至 $O(mn \log n + n^3)$。

总结：随机化最小二乘逼近算法通过随机投影快速获取原矩阵列空间的近似正交基，将大规模原问题压缩为一个维数近似为 \(n\) 的小规模最小二乘问题，从而在可控的精度损失下，极大地提升了大规模超定最小二乘问题的求解效率。其核心权衡在于通过引入随机性和可控的过采样参数 \(l\)，以极小的精度代价换取计算量从 \(O(mn^2)\) 到近 \(O(mn \log n)\) 的显著降低。

随机化最小二乘逼近算法（Randomized Least Squares Approximation） 算法描述 本算法旨在高效求解大规模超定线性最小二乘问题。给定一个高瘦矩阵A (m×n, m >> n) 和一个向量b (m×1)，标准最小二乘问题为： \[ \min_ {x} \|Ax - b\|_ 2^2 \] 其精确解可通过正规方程 \(A^T A x = A^T b\) 或QR分解得到，但计算成本为 \(O(mn^2)\)，对大规模矩阵过高。随机化最小二乘逼近算法通过随机投影将原问题压缩成一个规模小得多的问题，以近似解换取计算效率，典型加速到 \(O(mn \log n + n^3)\)。 解题过程 核心思想是用一个随机矩阵 \(\Omega\) 对原问题“降维”，在新空间中求解一个小规模最小二乘问题，再映射回原空间得到近似解。以下是详细步骤： 第1步：构造随机投影矩阵 目标 ：构造一个随机矩阵 \(\Omega\)，大小为 \(n \times l\)，其中 \(l\) 是一个略大于 \(n\) 的整数（例如 \(l = n + 10\)），用于对矩阵 \(A\) 的行空间进行采样和压缩。 选择分布 ：通常使用满足Johnson-Lindenstrauss引理的分布，如： 高斯随机矩阵 ：\(\Omega\) 的元素独立同分布于标准正态分布 \(N(0, 1)\)。这是最经典的选择，理论性质好。 稀疏符号随机矩阵 （如Achlioptas矩阵）：元素以较大概率取0，以降低生成和乘法成本。 快速变换矩阵 （如Subsampled Randomized Fourier Transform, SRFT）：由离散傅里叶变换矩阵的一部分行和随机符号对角阵构成，可利用FFT实现快速乘法，成本为 \(O(m \log m)\)。 维度 \(l\) 的选取 ：\(l\) 是一个超参数，它控制了精度与速度的权衡。理论上，\(l\) 越大，近似解精度越高，但计算量也越大。实践中常取 \(l = n + p\)，其中 \(p\) 是一个小的“过采样”参数（如5, 10）。 第2步：形成压缩的草图矩阵 计算草图 ：计算压缩后的矩阵 \(S = A \Omega\)。矩阵 \(S\) 的大小是 \(m \times l\)。 计算成本 ：这是算法中最昂贵的步骤。如果 \(A\) 是稠密矩阵，成本是 \(O(mln)\)。如果使用SRFT等结构化随机矩阵，成本可降至 \(O(m \log m)\) 或 \(O(mn \log n)\)。如果 \(A\) 是稀疏矩阵，可以利用稀疏性加速。 第3步：计算压缩问题的QR分解 目标 ：对草图矩阵 \(S\) 进行QR分解，以获取原矩阵 \(A\) 列空间的一个近似正交基。 分解 ：计算 \(S = QR\)，其中 \(Q\) 是 \(m \times l\) 的矩阵，其列标准正交（\(Q^T Q = I_ l\)），\(R\) 是 \(l \times l\) 的上三角矩阵。 几何解释 ：矩阵 \(Q\) 的列张成的子空间近似包含了矩阵 \(A\) 的列空间（即Range(A)）。由于 \(l > n\) 且是随机采样，这个近似在高概率下是相当好的。 第4步：投影原问题到低维空间 投影 ：将原最小二乘问题投影到 \(Q\) 张成的近似列空间上。这通过将原方程 \(Ax \approx b\) 近似为在 \(Q\) 的列空间上寻找最佳解来实现。 形成小规模问题 ：我们需要求解： \[ \min_ {y} \| Qy - b \|_ 2^2 \] 由于 \(Q\) 的列标准正交，这个最小二乘问题的法方程简化为 \(Q^T Q y = Q^T b\)，即 \(y = Q^T b\)。因此，最优系数向量 \(y^* = Q^T b\)。 计算 ：计算 \(y = Q^T b\)，这是一个 \(l \times 1\) 的向量。 第5步：回代求解原变量 建立近似关系 ：我们有近似关系 \(Ax \approx Qy\)。由于 \(Q\) 近似是 \(A\) 列空间的一组基，我们假设存在一个系数向量 \(z\) 使得 \(Qy \approx A z\)。更精确地说，我们求解一个小规模的最小二乘问题来找到最佳的 \(x\) 使得 \(Ax\) 在 \(Q\) 的列空间上的投影是 \(Qy\)。 求解小规模正规方程 ：实际上，我们可以通过求解以下方程得到近似解 \(\tilde{x}\)： \[ (A^T A) \tilde{x} = A^T (Q y) \] 为了避免计算 \(A^T A\)（可能条件数很差），我们利用 \(Q\) 与 \(A\) 的关系的一个有效替代。一个标准且稳定的方法是： 首先计算矩阵 \(B = Q^T A\)。\(B\) 的大小是 \(l \times n\)。由于 \(l \approx n\)，这比 \(A\) 小很多。 然后求解小型最小二乘问题：\(\min_ {\tilde{x}} \| B \tilde{x} - y \|_ 2^2\)，其中 \(y = Q^T b\)。 求解小型问题 ：对 \(B\) 进行QR分解（或SVD，因其规模小）：设 \(B = U \Sigma V^T\)（经济SVD）或 \(B = \tilde{Q} \tilde{R}\)。然后解 \(\tilde{R} w = \tilde{Q}^T y\) 得到 \(w\)，最终 \(\tilde{x} = V w\)（SVD方式类似）。由于 \(B\) 是 \(l \times n\) 且 \(l \ge n\)，这个小问题的求解成本仅为 \(O(ln^2) \approx O(n^3)\)。 第6步：算法输出与误差分析 输出 ：算法返回近似解 \(\tilde{x}\)。 误差与可靠性 ： 理论保证 ：在一定概率下（例如，对高斯随机矩阵），近似解 \(\tilde{x}\) 满足： \[ \|A\tilde{x} - b\| 2^2 \le (1 + \epsilon) \min {x} \|Ax - b\|_ 2^2 \] 其中 \(\epsilon\) 是一个与过采样参数 \(p\) 和失败概率相关的小常数。这意味着目标函数值（残差范数平方）接近最优值。 计算优势 ：当 \(m \gg n\) 时，主要计算成本是第2步形成草图 \(S = A\Omega\) 和第3步对 \(S\) 的QR分解（\(O(ml^2)\)）。与精确算法的 \(O(mn^2)\) 相比，当 \(l \approx n\) 时，加速显著，特别是当使用快速随机投影（如SRFT）时，可降至 \(O(mn \log n + n^3)\)。 总结 ：随机化最小二乘逼近算法通过随机投影快速获取原矩阵列空间的近似正交基，将大规模原问题压缩为一个维数近似为 \(n\) 的小规模最小二乘问题，从而在可控的精度损失下，极大地提升了大规模超定最小二乘问题的求解效率。其核心权衡在于通过引入随机性和可控的过采样参数 \(l\)，以极小的精度代价换取计算量从 \(O(mn^2)\) 到近 \(O(mn \log n)\) 的显著降低。