这是过去决赛中的一个问题，我们无法弄清楚。采用最小二乘系统

其中$A\in\mathbb{R}^{mxn}$，$m<n$和 A 是满秩。A 有$\mathcal{O}(n)$个非零条目。假设你只有$\mathcal{O}(n)$计算机内存。

1. 建议一种算法来逼近最小二乘问题的解
2. 预期的迭代次数和总计算成本是多少？
3. 解 x 中的预期误差是多少？（为此问题提供适当的错误定义）

我们只了解了一点迭代方法，例如瑞利商、逆迭代、幂迭代和共轭梯度。这些似乎都没有帮助。任何想法将不胜感激。

编辑：我现在在想，如果我们取一个随机的 mm 列以便形成一个方阵，然后在这个问题上使用 CG 怎么办？然后用各种随机列来找到平均解决方案？