Background:
Suppose I have M samples of a signal $\mathbf{s}$ and I want to represent them by a linear combination of functions $\phi_{1}, \phi_{2}, \ldots, \phi_{L}$. I can do this by finding a vector of coefficients $\mathbf{a}$ such that $\mathbf{s} = \Phi \mathbf{a}$, where $\Phi = [\phi_{1}, \phi_{2}, \ldots, \phi_{L}]$ is the matrix with columns that are our functions.
I can find this vector $\mathbf{a}$ by solving the following problem, called the Basis Pursuit problem:
\begin{align} \text{minimize} & \; || \mathbf{a} ||_{1} \\ \text{subject to} & \; {\Phi} \mathbf{a} = \mathbf{s} \end{align}
Note: We see there that $\mathbf{s} \in \mathbb{R}^{M}$, $\Phi \in \mathbb{R}^{M \times L}$ and $\mathbf{a} \in \mathbb{R}^{L}$.
As discussed in the post, How Can $ {L}_{1} $ Norm Minimization with Linear Equality Constraints (Basis Pursuit / Sparse Representation) Be Formulated as Linear Programming?, we see that the Basis Pursuit problem can be formulated as a linear program:
\begin{align} \underset{\mathbf{x} }{\text{minimize}} & \; \mathbf{c}^{T} \mathbf{x} \\ \nonumber \text{subject to} & \; \mathbf{A} \mathbf{x} = \mathbf{b} \\ \nonumber & \; \mathbf{x} \geq \mathbf{0} \end{align}
where we let $\mathbf{A} = \begin{bmatrix} {\Phi} & - {\Phi} \end{bmatrix}$, ${\mathbf{x}}^{T} = \begin{bmatrix} \mathbf{a}^{+} & \mathbf{a}^{-} \end{bmatrix}$, $ \mathbf{c}^{T} = \begin{bmatrix} \mathbf{1}^{T} & \mathbf{1}^{T} \end{bmatrix}$ and $\mathbf{b}= \mathbf{s}$.
The Problem
I can't get this to work in CVXOPT, nor when I implement my own Primal-Dual interior point solver. I always run into the problem of $\mathbf{A}$ being singular:
Traceback (most recent call last):
File "test_basis_pursuit.py", line 165, in <module>
sol=solvers.lp(c,A,b)
File "/usr/local/lib/python3.6/dist-packages/cvxopt/coneprog.py", line 3010, in lp
dualstart, kktsolver = kktsolver, options = options)
File "/usr/local/lib/python3.6/dist-packages/cvxopt/coneprog.py", line 573, in conelp
raise ValueError("Rank(A) < p or Rank([G; A]) < n")
ValueError: Rank(A) < p or Rank([G; A]) < n
I thought the whole point of Basis Pursuit was to be able to use an overcomplete dictionary -- which means that the columns need not be linearly independent. Or must they be linearly independent? Why can't I use an overcomplete dictionary here?
How many dictionary elements do I need, or how can I construct them, such that they are both meaningful AND create a matrix that has the proper row rank?
Edit: In my specific application, I know the functional forms of the signals $\phi_{i}$ that my signal $\mathbf{s}$ is composed of -- namely trains of Gaussian shaped pulses. What I don't know is the period of the train, or how wide the Gaussian shaped pulses are. It would be great if I could just use these directly, but perhaps I cannot???
You may find more success with a different type of solver. L1 homotopy tends to be reliable, or you could try SPGL1 (or the Python version). If you continue to have problems that you suspect are due to collinearity then perhaps you could try elastic net.