这个问题相当不简单。

秩为 r 的低秩表示不会导致找到最小和最大条目的简单方法。$X_{n\times n}=A_{n\times r}B^T_{r\times n}$$r$

然而，对于 r=1 的特殊情况 { , u您可以在，然后考虑到行中找到个最小或最大条目，对于。因此，对于，您当然可以将计算减少到。$r=1$$X_{n\times n}=uv^T$$u,v\in \mathbb R^n$$k$$k$$v$$\mathcal O(kn)$$u_i$$k$$i$$\mathcal O(k)$$i=1,\ldots,n$$r=1$$\mathcal O(kn)$

不幸的是，当时，事情变得棘手。以下关于 MathOverflow的问题讨论了计算整个矩阵的最大最小元素的选项，这是一个非常相似的问题。其中一个答案给出了的精确算法，该算法使用已知技术在 2 维和 3 维中找到凸包，也可以用于您的问题。但我怀疑这种特殊方法能否以有效的方式成功推广到更高的维度（）。$r>1$$r=2,3$$r>3$

另一个答案提到了一个非常有趣的想法，即使用 -net和的每一行/列，以计算与错误。我还没有尝试这个选项，但它在技术上是有意义的，并且应该可以扩展到一次查找值一行（通过一次仅将的 1 行映射到网络，同时在那里保留的记录）。方面是指数的$\epsilon$$r$$A$$B$$\mathcal O(nr+(1/\epsilon)^r)$$\epsilon$$k$$A$$B$$r$，这将使其仅适用于任何体面的。$r\ll\ll\ll n$$\epsilon$

几种可能的方法：

• NJ Higham 和 SD Relton，“估计矩阵的最大元素”，SIAM J. Sci。计算。, 卷。38，没有。5，第 C584-C601 页。预印本的替代链接。
• SA Goreinov、IV Oseledets、DV Savostyanov、EE Tyrtyshnikov 和 NL Zamarashkin，“如何找到好的子矩阵”，研究报告 08-10，ICM HKBU，香港九龙塘。或者，链接到Matrix Methods书中的一章。