注意我们之前约定过切片的优先级高于求逆，所以这里的含义是 。不难发现实际上就是矩阵 的 列，所以上式实际上给出了一个 ID 近似：以上就是基于列驱 QR 分解的 ID 求解算法，也是 SciPy 内置的求解算法（rand=False）。注意该算法是无法保证 或者 的，但根据很多文献的反馈，在实践中它几乎不会出现 ，所以这算是一个比较良好的求解算法。此外，SciPy 也内置了列驱 QR 分解，在 scipy.linalg.qr 中设置 pivoting=True 即可打开。
随机求解列驱 QR 分解每一步正交化操作，需要遍历剩余的所有向量取误差最大者，这在 很大时往往难以接受，另一方面如果 很大，那么模长、内积的计算量也会很高，于是随机算法便应运而生，它设法减少 或 的值来降低计算复杂度。首先我们来看降低 n 的思路，即降低 的每个列向量的维度，常用的方法是随机投影，跟《让人惊叹的 Johnson-Lindenstrauss 引理：理论篇》介绍的 “JL 引理”如出一辙。具体来说，假设 是某个随机投影矩阵（其中 ），它的元素是从某个分布如 独立重复采样出来的，那么我们考虑在小矩阵 上执行列驱 QR 分解来确定被选中的 列的位置。更详细的介绍可以参考《Randomized algorithms for pivoting and for computing interpolatory and CUR factorizations》[3]。根据笔者有限的调研显示，SciPy 求解 ID 的随机算法也是用的是类似思路，只是把随机采样的矩阵换成了更加结构化的 “Subsampled Randomized Fourier Transform（SRFT）”，使得 这一步的计算量可以从 降到 。不过 SRFT 以及 SciPy 的实现细节笔者也不了解，有兴趣的读者可以参考《Enabling very large-scale matrix computations via randomization》[4]、《A brief introduction to Randomized Linear Algebra》[5] 等资料进一步深究。没有深究 SRFT 等复杂随机投影方法的另一个原因，是论文《Efficient Algorithms for Constructing an Interpolative Decomposition》[6] 发现更简单的列采样往往能得到更优的结果，而且还特别好理解，就是从 中随机采样 列，然后用列驱 QR 分解从这 列中选出 列作为 ，最后再来根据 求解 ，这样就将列驱 QR 分解的矩阵大小从 降低到 。实验显示这样的简单思路顶多在个别任务上增大了 的风险，但在误差上有明显优势：
从上述表格可以留意到一个也许会让人觉得意外的结果：随机列采样的 Optim-RID，在误差方面不仅优于同样是随机算法的 SciPy-RID，在个别任务上甚至还优于确定性算法 SciPy-ID 和 Optim-ID（它们数学上是等价的，都是基于完整的列驱 QR 分解，只是实现上的效率有所不同）。
这个看似反直觉的现象，实则说明了一个事实：列驱 QR 分解虽然可以作为 ID 的一个较好的 baseline，但它选择基的能力可能跟随机选择差不了多少，列驱 QR 分解的主要作用只是保证大概率成立 。其实这也不难理解，我们以 为例，这时候列驱 QR 分解就是返回模长最大的那一列，可是模长最大的那列一定是好的（能使得重构误差最小的）基底吗？显然不是，好的基底应该是多数向量共同指向的方向，模长最大不能体现这一点。对于 ID 来说，列驱 QR 分解本质上是一种贪心算法，它将选 列贪心地转化为多个选 1 列的递归，而当 时，在 不算太大或者要求高精度的场景，通过枚举来精确求解的复杂度是可以接受的即遍历所有的 ，将剩下的所有列都投影到 上来计算总误差，选择总误差最小的 ，其复杂度跟 成正比。如果将列驱 QR 分解每一步选择模长最大的操作改为选择总误差最小的上式，那么就能找出更好的基底，从而实现更低的重构误差（代价自然是复杂度更高了，而且更加无法保证 了）。
总的来说，由于精确求解的 NP-Hard 性，所以 ID 有非常多的求解思路，上面列举的只是非常有限的几种，有兴趣的读者可以可以围绕着 Randomized Linear Algebra、Column Subset Selection 等关键词深入搜索。
特别要指出的是，Randomized Linear Algebra，旨在通过随机方法来加速各种矩阵运算，本身已经成为了一个内容丰富的学科，本文的随机 ID 和上一篇基于采样的 CR 近似，都是这个学科的经典例子。
