Faster linear programming alternative to `scipy.optimize.minimize` for solving basis pursuit problems

[winwinashwin]

The scipy.optimize.minimize method tends to be really slow for solving the basis pursuit problem (ex. in the compressed sensing context) especially when we are dealing with less sparse vectors. A much faster alternative could be used by modelling the problem as a linear programming problem and using scipy.optimize.linprog instead

def basis_pursuit_v2(A, y):
    """Objective : minimize(  norm(x, 1)  )
       Subject to: A * x == y
    """
    numCols = A.shape[1]

    vF = np.ones((2 * numCols, 1))
    mAeq = np.hstack([A, -A])
    vBeq = y

    vUV = linprog(vF, None, None, mAeq, vBeq, bounds=(0, np.inf))
    return vUV.x[:numCols] - vUV.x[numCols:]

This answer explains the LP modelling