MATLAB 中阈值内的最小二乘最小化
Least-squares minimization within threshold in MATLAB
MATLAB 的 cvx 套件可以解决下面的（看似无害的）优化问题，但对于我正在处理的大型全矩阵来说，它的速度相当慢。我希望这是因为使用 cvx 是矫枉过正，并且该问题实际上有一个解析解决方案，或者巧妙地使用一些内置的 MATLAB 函数可以更快地完成这项工作。
背景：众所周知，x1=A\b and x2=pinv(A)*b都解决了最小二乘问题：
minimize norm(A*x-b)
与norm(x2)<=norm(x1)的区别。事实上，x2 是问题的 最小范数解 ，因此 norm(x2)<=norm(x) 是所有可能的解 x。
定义D=norm(A*x2-b)，（相当于D=norm(A*x1-b)），然后x2解决问题
minimize norm(x)
subject to
norm(A*x-b) == D
问题：我想找到解决方案：
minimize norm(x)
subject to
norm(A*x-b) <= D+threshold
言之，我不需要norm(A*x-b)越小越好，在一定的容忍度内即可。我想要在 b 的 D+threshold 范围内获得 A*x 的最小范数解决方案 x。
我无法在网上或手动找到问题的解析解（例如在经典最小二乘问题中使用伪逆）。我一直在搜索 "least squares with nonlinear constraint" 和 "least squares with threshold".
之类的东西
任何见解将不胜感激，但我想我真正的问题是：
在 MATLAB 中解决此 "thresholded" 最小二乘问题的最快方法是什么？
有趣的问题。我不知道您的确切问题的答案，但下面提供了一个可行的解决方案。
回顾
定义 res(x) := norm(Ax - b)。
正如您所说，x2 最小化了 res(x)。在超定情况下（通常 A 的行数多于 col 的行数），x2 是唯一的最小值。在不确定的情况下，它由无限多的其他*加入。然而，在所有这些中，x2 是唯一一个最小化 norm(x).
的
总而言之，x2 最小化 (1) res(x) 和 (2) norm(x)，并按优先级顺序执行。事实上，这表征（完全确定）x2。
极限表征
但是，x2 的 another characterization 是
x2 := limit_{e-->0} x_e
哪里
x_e := argmin_{x} J(x;e)
哪里
J(x;e) := res(x) + e * norm(x)
可以证明
x_e = (A A' + e I)^{-1} A' b (eqn a)
不得不说，x2的这个定性相当神奇。即使 (A A')^{-1} 不存在，限制也存在。并且限制以某种方式保留了上面的优先级 (2)。
使用 e>0
当然，对于有限（但很小）的 e，x_e 不会最小化 res(x)（而是最小化 J(x;e)）。在您的术语中，差异是阈值。我将其重命名为
gap := res(x_e) - min_{x} res(x).
减小 e 的值一定会减小 gap 的值。因此，通过调整 e 很容易达到特定的 gap 值（即阈值）。**
这种类型的修改（将 norm(x) 添加到 res(x) 最小化问题）在统计文献中被称为正则化，通常被认为是稳定性的好主意（在数值上和参数方面）值）。
*：请注意 x1 和 x2 仅在欠定情况下不同
**：它甚至不需要任何繁重的计算，因为如果已经计算了 A 的 SVD，那么对于 e 的任何（正）值，(eqn a) 中的逆很容易计算.
MATLAB 的 cvx 套件可以解决下面的（看似无害的）优化问题，但对于我正在处理的大型全矩阵来说，它的速度相当慢。我希望这是因为使用 cvx 是矫枉过正，并且该问题实际上有一个解析解决方案，或者巧妙地使用一些内置的 MATLAB 函数可以更快地完成这项工作。
背景：众所周知，x1=A\b and x2=pinv(A)*b都解决了最小二乘问题：
minimize norm(A*x-b)
与norm(x2)<=norm(x1)的区别。事实上，x2 是问题的 最小范数解 ，因此 norm(x2)<=norm(x) 是所有可能的解 x。
定义D=norm(A*x2-b)，（相当于D=norm(A*x1-b)），然后x2解决问题
minimize norm(x)
subject to
norm(A*x-b) == D
问题：我想找到解决方案：
minimize norm(x)
subject to
norm(A*x-b) <= D+threshold
言之，我不需要norm(A*x-b)越小越好，在一定的容忍度内即可。我想要在 b 的 D+threshold 范围内获得 A*x 的最小范数解决方案 x。
我无法在网上或手动找到问题的解析解（例如在经典最小二乘问题中使用伪逆）。我一直在搜索 "least squares with nonlinear constraint" 和 "least squares with threshold".
之类的东西任何见解将不胜感激，但我想我真正的问题是： 在 MATLAB 中解决此 "thresholded" 最小二乘问题的最快方法是什么？
有趣的问题。我不知道您的确切问题的答案，但下面提供了一个可行的解决方案。
回顾
定义 res(x) := norm(Ax - b)。
正如您所说，x2 最小化了 res(x)。在超定情况下（通常 A 的行数多于 col 的行数），x2 是唯一的最小值。在不确定的情况下，它由无限多的其他*加入。然而，在所有这些中，x2 是唯一一个最小化 norm(x).
总而言之，x2 最小化 (1) res(x) 和 (2) norm(x)，并按优先级顺序执行。事实上，这表征（完全确定）x2。
极限表征
但是，x2 的 another characterization 是
x2 := limit_{e-->0} x_e
哪里
x_e := argmin_{x} J(x;e)
哪里
J(x;e) := res(x) + e * norm(x)
可以证明
x_e = (A A' + e I)^{-1} A' b (eqn a)
不得不说，x2的这个定性相当神奇。即使 (A A')^{-1} 不存在，限制也存在。并且限制以某种方式保留了上面的优先级 (2)。
使用 e>0
当然，对于有限（但很小）的 e，x_e 不会最小化 res(x)（而是最小化 J(x;e)）。在您的术语中，差异是阈值。我将其重命名为
gap := res(x_e) - min_{x} res(x).
减小 e 的值一定会减小 gap 的值。因此，通过调整 e 很容易达到特定的 gap 值（即阈值）。**
这种类型的修改（将 norm(x) 添加到 res(x) 最小化问题）在统计文献中被称为正则化，通常被认为是稳定性的好主意（在数值上和参数方面）值）。
*：请注意 x1 和 x2 仅在欠定情况下不同
**：它甚至不需要任何繁重的计算，因为如果已经计算了 A 的 SVD，那么对于 e 的任何（正）值，(eqn a) 中的逆很容易计算.