least squares with L1 regularization in selected entries

Question

Say for $x \in \mathbb{R}^n$, I'm minimizing $\|Ax - b \|_2^2$ with L1 regularization on selected entries of $x$. i.e. instead of directly add a $\|x\|_1$ regularization term, it would be on $|x_i| + |x_j| + \cdots + |x_k|$, where ${i, j, \cdots, k}$ are the entries I wish to impose sparsity constraint. If with gradient-based method, how should I approach this problem? I know for the regular L1 norm regularization we can use subgradient, but how to deal with this problem?

Answer 1

Consider the proximal mapping $$ \mathrm{prox}_t(\mathbf{x}) =\arg \min_\mathbf{z} \frac{1}{2t} \| \mathbf{x-z} \|_2^2 + \lambda \|\mathbf{z}\|_1 $$

We can reason components by components. For those components that are not impacted by the regularization term, the minimizer is x_i For the others, it is $S_{\lambda t}(x_i)$.

Let call $S_{\lambda t}^*$ this modified soft-threshold operator

Proximal gradient update is in this case $$ \mathbf{x}^+ = S^*_{\lambda t} \left[\mathbf{x} - t \mathbf{A}^T \left( \mathbf{Ax-b} \right) \right] $$