使用特征减少 QR 分解

Question

我正在尝试使用 Eigen 解决 class 最小二乘问题 argmin (Ax - b)^2。我知道系统是多定的（即 m >= n，其中 A 是 m x n）并且 A 具有满秩 (n)。我选择使用 Eigen 的稀疏 QR 部分，因为 A 本身是稀疏的。我做到了这一点：

#include <Eigen/Sparse>
#include <Eigen/SparseQR>

void solve_least_squares(const Eigen::SparseMatrix<double>& matrix,
                         const Eigen::VectorXd& rhs)
{
  int m = matrix.rows();
  int n = matrix.cols();

  assert(m >= n);
  assert(matrix.isCompressed());

  Eigen::SparseQR<Eigen::SparseMatrix<double>, Eigen::COLAMDOrdering<int>> decomposition(matrix);

  Eigen::VectorXd t = (decomposition.matrixQ().transpose() * rhs).topRows(n);

  std::cout << t << std::endl;

  Eigen::VectorXd s = decomposition.matrixR().topRows(n).triangularView<Eigen::Upper>().solve(t);

  return decomposition.colsPermutation().inverse()*s;
}

但我想知道这是否是最有效的实现：首先，Eigen 似乎确定完整 QR 分解而不是简化分解（Q 是 m x m 而不是 m x n)。这看起来很浪费，因为我只需要前 n 行。

在密集的情况下，HouseholderQR中有任何例子 class:

MatrixXf A(MatrixXf::Random(5,3)), thinQ(MatrixXf::Identity(5,3)), Q;
A.setRandom();
HouseholderQR<MatrixXf> qr(A);
Q = qr.householderQ();
thinQ = qr.householderQ() * thinQ; // <- here
std::cout << "The complete unitary matrix Q is:\n" << Q << "\n\n";
std::cout << "The thin matrix Q is:\n" << thinQ << "\n\n";

这里使用矩阵乘法来得到缩减的Q，这似乎比对整个矩阵进行切片更低效。

由于 Eigen 的（密集）SVD 分解提供了计算薄 SVD 的选项，QR 分解是否有类似的选项？

Answer 1

在分解中，Q 因子存储为一系列 Householder 向量，而 matrixQ() 方法本质上是 returns 对该矩阵的引用（它以某种方式重载乘法"as if" 乘以实际矩阵）。当存储为 Householder 矩阵时，Q 表示 Q 的完整部分或薄部分没有区别（实际上，可以就地有效地用向量乘以完整矩阵）。

如果你想解决你的线性系统，你应该写

Eigen::VectorXd s = decomposition.solve(rhs);

顺便说一句：如果您不介意损失一些精度（并且您的矩阵条件足够好），您（在大多数情况下）通过求解正规方程（Matlab 符号）会更快：

x = (A'*A) \ (A'*b)

并使用稀疏的 Cholesky 分解（例如，Eigen::SimplicialLLT 或 Eigen::SimplicialLDLT）。但是用您的实际数据进行基准测试，并检查准确性是否足以满足您的用例（可能在重新使用 Cholesky 分解的细化步骤之后）。

使用特征减少 QR 分解

Reduced QR decomposition with eigen

c++

linear-algebra

eigen