Conversion of Basis Pursuit to Linear Programming
The Basis Pursuit problem is given by:
$$
\begin{align*}
\arg \min_{x} \: & \: {\left\| x \right\|}_{1} \\
\text{subject to} \: & \: A x = b
\end{align*}
$$
Method A
The term $ {\left\| x \right\|}_{1} $ can written in element wise form:
$$ {\left\| x \right\|}_{1} = \sum_{i = 1}^{n} \left| {x}_{i} \right| $$
Then setting $ \left| {x}_{i} \right| \leq {t}_{i} $ one could write:
$$
\begin{align*}
\arg \min_{t} \: & \: \boldsymbol{1}^{T} t \\
\text{subject to} \: & \: A x = b \\
& \: \left| {x}_{i} \right| \leq {t}_{i} \; \forall i
\end{align*}
$$
Since $ \left| {x}_{i} \right| \leq {t}_{i} \iff {x}_{i} \leq {t}_{i}, \, {x}_{i} \geq -{t}_{i} $ then:
$$
\begin{align*}
\arg \min_{t} \: & \: \boldsymbol{1}^{T} t \\
\text{subject to} \: & \: A x = b \\
& \: {x}_{i} \leq {t}_{i} \; \forall i \\
& \: {x}_{i} \geq -{t}_{i} \; \forall i
\end{align*}
$$
Which can be farther refined:
$$
\begin{align*}
\arg \min_{t} \: & \: \boldsymbol{1}^{T} t \\
\text{subject to} \: & \: A x = b \\
& \: I x - I t \preceq \boldsymbol{0} \\
& \: -I x - I t \preceq \boldsymbol{0}
\end{align*}
$$
Which is a Linear Programming problem.
Method B
Define:
$$ x = u - v, \; {u}_{i} = \max \left\{ {x}_{i}, 0 \right\}, \; {v}_{i} = \max \left\{ -{x}_{i}, 0 \right\} $$
Then the problem becomes:
$$
\begin{align*}
\arg \min_{u, v} \: & \: \sum_{i = 1}^{n} {u}_{i} + {v}_{i} \\
\text{subject to} \: & \: A \left( u - v \right) = b \\
& \: u \succeq \boldsymbol{0} \\
& \: v \succeq \boldsymbol{0}
\end{align*}
$$
Which is also a Linear Programming problem.
MATLAB Implementation
MATLAB Implementation is straight forward using the linprog() function.
The full code, including validation using CVX, can be found in my StackExchange Mathematics Q1639716 GitHub Repository.
Code Snippet - Method A
function [ vX ] = SolveBasisPursuitLp001( mA, vB )
numRows = size(mA, 1);
numCols = size(mA, 2);
%% vX = [vX; vT]
mAeq = [mA, zeros(numRows, numCols)];
vBeq = vB;
vF = [zeros([numCols, 1]); ones([numCols, 1])];
mA = [eye(numCols), -eye(numCols); -eye(numCols), -eye(numCols)];
vB = zeros(2 * numCols, 1);
sSolverOptions = optimoptions('linprog', 'Display', 'off');
vX = linprog(vF, mA, vB, mAeq, vBeq, [], [], sSolverOptions);
vX = vX(1:numCols);
end
Code Snippet - Method B
function [ vX ] = SolveBasisPursuitLp002( mA, vB )
numRows = size(mA, 1);
numCols = size(mA, 2);
% vU = max(vX, 0);
% vV = max(-vX, 0);
% vX = vU - vX;
% vUV = [vU; vV];
vF = ones([2 * numCols, 1]);
mAeq = [mA, -mA];
vBeq = vB;
vLowerBound = zeros([2 * numCols, 1]);
vUpperBound = inf([2 * numCols, 1]);
sSolverOptions = optimoptions('linprog', 'Display', 'off');
vUV = linprog(vF, [], [], mAeq, vBeq, vLowerBound, vUpperBound, sSolverOptions);
vX = vUV(1:numCols) - vUV(numCols + 1:end);
end
I used the code above in Reconstruction of a Signal from Sub Sampled Spectrum by Compressed Sensing.
Best Answer
The problem is given by:
$$\begin{align*} \arg \min_{x} \quad & {x}^{T} B x \\ \text{subject to} \quad & C x = d \end{align*}$$
Where $ B $ is Positive Semi Definite (PSD) matrix.
Since $ B $ is PSD one could write the problem as:
$$\begin{align*} \arg \min \quad & {\left\| A x - b \right\|}_{2}^{2} \\ \text{subject to} \quad & C x = d \end{align*}$$
Where $ {A}^{T} A = B $ (Since it is PSD it is guaranteed such $ A $ exists) and $ b = \boldsymbol{0} $.
Now, this a simple Least Squares problem with Linear Equality Constraints.
The Lagrangian is given by:
$$ L \left( x, \nu \right) = \frac{1}{2} \left\| A x - b \right\|_{2}^{2} + {\nu}^{T} \left( C x - d \right) $$
From KKT Conditions the optimal values of $ \hat{x}, \hat{\nu} $ obeys:
$$ \begin{bmatrix} {A}^{T} A & {C}^{T} \\ C & 0 \end{bmatrix} \begin{bmatrix} \hat{x} \\ \hat{\nu} \end{bmatrix} = \begin{bmatrix} {A}^{T} b \\ d \end{bmatrix} $$
Since $ B = {A}^{T} A $ and $ b = \boldsymbol{0} $ the above reduces to:
$$ \begin{bmatrix} B & {C}^{T} \\ C & 0 \end{bmatrix} \begin{bmatrix} \hat{x} \\ \hat{\nu} \end{bmatrix} = \begin{bmatrix} \boldsymbol{0} \\ d \end{bmatrix} $$
Now all needed is to solve the above with any Linear System Solver.
If you want to use iterative procedure you may use Linear Least Squares with Linear Equality Constraints - Iterative Solver (With included MATLAB Code).