3

我有矩阵系统：

A x B = C

A由和由. a_ _ 两者和都是未知的，但我有部分信息（我有一些值，但不是全部）并且被挑选得足够小，以至于系统预计会受到过度约束。不需要过度约束 in 中的所有行或列。nBnbABCnAB

我正在寻找最小二乘 线性回归之类的东西来找到最适合这个系统的东西（注意：我知道不会有一个唯一的解决方案，但我想要的只是最好的解决方案之一）

举个具体的例子；所有 a 和 b 都是未知的，所有 c 都是已知的，而 ? 被忽略。我想找到 一个仅考虑已知 c 的最小二乘解决方案。

[ a11, a12 ]                                     [ c11, c12, c13, c14, ?   ]
[ a21, a22 ]   [ b11, b12, b13, b14, b15]        [ c21, c22, c23, c24, c25 ]
[ a31, a32 ] x [ b21, b22, b23, b24, b25] = C ~= [ c31, c32, c33, ?,   c35 ]
[ a41, a42 ]                                     [ ?,   ?,   c43, c44, c45 ]
[ a51, a52 ]                                     [ c51, c52, c53, c54, c55 ]

请注意，如果 B 仅被修剪为 b11 和 b21 并且未知的第 4 行被剔除，那么这几乎是一个标准的最小二乘线性回归问题。

4

5 回答 5

5

如前所述，这个问题是不适定的。

令 A、B 和 C=5 为标量。您要求解决具有无限数量的解决方案的 a*b=5。

根据上面提供的信息，一种方法是最小化定义为的函数 g

g(A,B) = ||AB-C||^2 = 迹线((AB-C)*(AB-C))^2

使用牛顿法或准割线法 (BFGS)。
（您可以在此处轻松计算梯度）。M* 是 M 的转置，乘法是隐式的。（规范是 frobenius 规范......我删除了下划线 F，因为它没有正确显示）

由于这是一个固有的非线性问题，标准线性代数方法不适用。

如果您提供更多信息，我可能会提供更多帮助。

还有一些问题：我认为问题在于没有更多信息，就没有“最佳解决方案”。我们需要确定我们正在寻找的更具体的想法。一个想法，可能是一个“最稀疏”的解决方案。这个领域是一个热门的研究领域，世界上一些最优秀的人才在这里工作（参见 Terry Tao 等人关于核规范的工作）这个问题虽然容易处理，但仍然很难。

不幸的是，我还不能发表评论，所以我会在这里添加我的评论。如下所述，LM 是解决这个问题的好方法，而且只是一种方法。沿着牛顿型方法解决优化问题或非线性求解问题。

这是一个想法，使用上面给出的示例：让我们定义两个新向量，V 和 U，每个向量都有 21 个元素（与 C 中定义的元素数量完全相同）。

V 恰好是 C 的已知元素，列有序，所以（在 ​​matlab 表示法中）

V = [C11; C21; C31; C51; C12; .... ; [C55]

U 是一个向量，它是乘积 AB 的列排序，省略了与“？”相对应的元素 在矩阵 C中。将所有变量收集到 x 我们有
x = [a11, a21, .. a52, b11, b21 ..., b25]。

f(x) = U（如上定义）。

我们现在可以尝试使用您最喜欢的非线性最小二乘法求解 f(x)=V。

顺便说一句，虽然下面的海报推荐了模拟退火，但我建议不要这样做。它存在一些问题，但它是一种启发式方法。当您拥有强大的分析方法（例如 Gauss-Newton 或 LM）时，我会说使用它们。（根据我自己的经验）

于 2009-05-06T00:58:07.170 回答
2

一个疯狂的猜测：奇异值分解可以解决问题吗？

于 2009-05-04T17:28:13.610 回答
1

你有几个选择。Levenberg-Marquadt 算法通常被认为是最好的 LS 方法。可在此处获得免费实施。但是，如果计算速度很快并且您有相当数量的参数，我强烈建议使用 Monte Carlo 方法，例如模拟退火。

您从答案中的一组参数开始，然后将其中一个随机百分比增加到最大值。然后，您计算系统的适应度函数。现在，这是诀窍。你不会扔掉不好的答案。你用玻尔兹曼概率分布接受它们。

P = exp(-(x-x0)/T)

其中 T 是温度参数，x-x0 是当前适应值减去前一个。在 x 次迭代后，您将 T 减少一个固定量（这称为冷却计划）。然后，您对另一个随机参数重复此过程。随着 T 的减小，选择的不良解决方案越来越少，最终该过程变成了“贪婪搜索”，只接受提高拟合度的解决方案。如果您的系统有许多自由参数（> 10 左右），这确实是您有机会达到全局最小值的唯一方法。这种拟合方法需要大约 20 分钟来编写代码，并且需要几个小时来调整。希望这可以帮助。

仅供参考，Wolfram 在旅行商问题的背景下对此进行了很好的讨论，我一直在非常成功地使用它来解决一些非常困难的全局最小化问题。它比 LM 方法慢，但在最困难/相对较大的情况下要好得多。

于 2009-05-06T19:02:51.243 回答
1

我不知道如何处理你的缺失值，所以我将忽略这个问题。

没有唯一的解决方案。要找到最佳解决方案，您需要某种指标来判断它们。我将假设您想使用最小二乘度量，即 A 和 B 的最佳猜测值是最小化数字总和的那些 [C_ij-(AB)_ij]^2。

您没有提到的一件事是如何确定要用于 n 的值。简而言之，如果 1 <= n <= b，我们可以提出“好的”解决方案。这是因为 1 <= rank(span(C)) <= b。其中 rank(span(C)) = C 的列空间的维度。注意这是假设 a >= b。为了更正确，我们会写成 1 <= rank(span(C)) <= min(a,b)。

现在，假设您选择了 n，使得 1 <= n <= b。如果您选择 A 的列使得 span(A) = span(C 的前 n 个特征向量)，您将最小化残差平方和。如果没有其他好的理由，只需选择 A 的列作为 C 的前 n 个特征向量。一旦选择了 A，就可以通过通常的线性回归方式得到 B 的值。即 B = (A'A)^(-1)A' C

于 2009-05-16T03:15:32.843 回答
0

基于将 B 切割为单列并删除带有未知数的行将其转换为非常接近已知问题的认识，一种方法是：

  1. 具有随机值的种子 A。
  2. 独立求解 B 的每一列。
  3. 在给定步骤 2 中的 B 值的情况下，重新处理问题以允许求解 A 的每一行。
  4. 在第 2 步重复，直到事情解决。

我不知道这是否稳定。

于 2009-05-09T00:27:40.423 回答