是否有 python 基础追踪求解器的实现？

Question

最初，我想在 Python 中使用 YALL1 package for L1 minimization, however, it's written in matlab. After some research I couldn't find a basis pursuit 求解器，但那里有吗？或者，我可以使用哪些现有库来解决这个最小化问题？

这里是原题（BP+）：

Answer 1

我认为你可以使用二次锥规划 (quick reference) 进行基追踪。

在python中你可以使用cvxopt to solve quadratic cone programs

编辑：偶数 one of their examples。

Answer 2

如原始论文中所述基于基础的原子分解 Pursuit关于Basis Pursuit (BP)，BP可以等价地重新表述为线性规划(LP)问题，LP已经开发出非常高效的求解器。

在this se.math site中有一个讨论和给定BP问题的LP问题标准形式的公式。回想一下，在 BP 中，您正在寻找形状为 (x_dim, ) 的 x，这样 A@x=y 和 x 对 L1 范数来说是最小的。因此，您只需要一个脚本，该脚本采用形状为 (y_dim, x_dim) 的数组 A、形状为 (y_dim, ) 的数组 y 和 returns 标准形式。

这是使用 LP 的标准形式处理 BP 问题和 returns 最优 x 的函数（我以这种方式编写它以便它适合 [=28] 中使用的术语=]).该脚本使用 scipy.optimize.linprog 作为 LP 的后端。

import numpy as np
from scipy.optimize import linprog

def get_optimal_x_for_bp(A, y):
    x_dim, y_dim = A.shape[1], y.shape[0]
    eye = np.eye(x_dim)

    obj = np.concatenate([np.zeros(x_dim), np.ones(x_dim)])

    lhs_ineq = np.concatenate([np.concatenate([eye, -eye], axis=1), np.concatenate([-eye, -eye], axis=1)], axis=0)
    rhs_ineq = np.zeros(2 * x_dim)

    lhs_eq = np.concatenate([A, np.zeros((y_dim, x_dim))], axis=1)
    rhs_eq = y

    bnd = [*((None, None) for _ in range(x_dim)), *((0, None) for _ in range(x_dim))]

    res = linprog(c=obj, A_ub=lhs_ineq, b_ub=rhs_ineq, A_eq=lhs_eq, b_eq=rhs_eq, bounds=bnd, method="revised simplex")
    return res.x[:x_dim]

您可以在示例中检查它是否正常工作 2x_1-x_2=2:

if __name__ == '__main__':
    A = np.array([[2, -1]])
    y = np.array([2])

    x = get_optimal_x_for_bp(A, y)
    print(x)
Output: [1. 0.]

输出表明 x_1=1, x_2=0 是最优的 x。从下图可以看出这是真的：

你也可以把它应用到一些更复杂的问题上：

if __name__ == '__main__':
    x_dim, y_dim = 6, 4

    A = np.random.rand(y_dim, x_dim)
    y = np.random.rand(y_dim)

    x = get_optimal_x_for_bp(A, y)
    print(x)
Output: [ 0.          1.55953519  0.50597071  0.          0.1724968  -1.86814744]

请记住，正如关于 BP 的原始论文中所写，系统 A@x=y 应该是超完备的。

是否有 python 基础追踪求解器的实现？

Is there a python implementation of a basis pursuit solver?

python

optimization

minimization