Adding Variance \ Weights Information When Solving a Basis Pursuit Denoising Problem (BPDN)

Question

Having a "measured" vector $\mathbf{y}$ with its statistics (counts or variance per element), one can use weighted least squares approach to solve the linear system $$\mathbf{A}\mathbf{x} = \mathbf{y}$$ by minimizing $$(\mathbf{y} - \mathbf{A}\mathbf{x})^T{\rm diag}(\mathbf{c})(\mathbf{y} - \mathbf{A}\mathbf{x}),$$ where $\mathbf{c}$ contains either counts or inverse variances.

When this linear problem is ill-posed but the model is sparse I can use the Basis Pursuit Denoising approach looking for a sparse solution:
$$ \mathbf{x}^{\ast} = \arg \min_{\mathbf{x}} \left\{ \frac{1}{2} {\left\| \mathbf{A} \mathbf{x} - \mathbf{y} \right\|}_{2}^{2} + \lambda {\left\| \mathbf{x} \right\|}_{1} \right\} $$

Logically i am tempted to just modify the $\mathbf{A}$ term to $\mathbf{A}^T {\rm diag}(\mathbf{c}) \mathbf{A}$ to include the weights for each element, but I am not sure this is a sound approach for the $L_1$ case. Is this approach valid or is there a different way to include the measurement statistic for such regularization?

Answer 1

Your formulation:

$$ \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| A \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}^{2} + \lambda {\left\| \boldsymbol{x} \right\|}_{1} $$

Has 2 elements:

1. The Fidelity Term
   This is basically measurements term with the model of AWGN with IID noise.
2. The Regularization Term
   This is a sparse promoting model by using the Laplace Distribution as a prior.

Since your measurement model is not IID but with different variance per measurement what you need is use Mahalanobis Distance in the measurement model (Which matches the Multivariate Gaussian Distribution).

Using some variation of the norm (See Norm with Symmetric Positive Definite Matrix) which is defined as:

$$ {\left\| \boldsymbol{x} \right\|}_{W}^{2} = \boldsymbol{x}^{T} W \boldsymbol{x}, \; \boldsymbol{x} \in \mathbb{R}^{n}, W \in \mathbb{S}_{++}^{n} $$

You may formulate your problem as:

$$ \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| A \boldsymbol{x} - \boldsymbol{y} \right\|}_{ {C}^{-1} }^{2} + \lambda {\left\| \boldsymbol{x} \right\|}_{1} $$

Where $ C $ is your covariance matrix (Basically $ \operatorname{diag} \left( \boldsymbol{c} \right) $ on your question).
The above is easy to solve using many methods as it is basically transformed LS by using Cholesky Decomposition of the Covariance Matrix.