# Convex Optimization with ${L}_{1, 2}$ Regularization Term

I have an optimization problem such as follow: $$\underset{X}{\operatorname{argmin}}\sum _s \left \| T_sX_{:,s} - Y_{:,s} \right \|^2_2 +\lambda\left \| GX \right \|_{2,1} \tag{1}$$ I have introduced a new variable: $$\underset{X,Z}{\operatorname{argmin}}\sum _s\left \| T_sX_{:,s}-Y_{:,s} \right \|^2_2 +\gamma\left \| GX -Z\right \|^2_2+\lambda\left \| Z \right \|_{2,1} \tag{2}$$ And divided this problem into two sub-problems: $$\underset{Z}{\operatorname{argmin}} \gamma\left \| GX -Z\right \|^2_2+\lambda\left \| Z \right \|_{2,1}\tag{3.1}$$ $$\underset{X}{\operatorname{argmin}}\sum _s\left \| T_s X_{:,s} - Y_{:,s} \right \|^2_2 +\gamma\left \| GX -Z\right \|^2_2 \tag{3.2}$$ I have found that (from a paper) for the eqn 3.1, solution is as follows: $$Z_{n,:}=[GX]_{n,:} \operatorname{}max\left \{1-\frac{\lambda}{2\gamma \left \| [GX]_{n,:} \right \|_2} ,0\right\}\tag{4}$$ I am solving this problem iteratively. First, I solve for $$Z$$ using equation 4, then I am solving for $$X$$ using equation 3.2 and utilizing nonlinear conjugate gradient method. Something is clearly wrong since I cannot reach to a solution. And it is not like solutions are diverging but more like always 0.

Do you see anything wrong so far? If not, I can upload my nonlinear conjugate gradient method.

• On the first glance I got the impression that this is rather a mathematical problem than a signal processing one, have you considered to ask it at: Mathtematics Commented Jul 19, 2019 at 12:47
• @Irreducible Honestly I have asked the same question at math.stackexchange however got no response. You are correct though. Commented Jul 19, 2019 at 13:03
• I think your approach is correct. First, you are using variable splitting method, and then using augmented Lagrangian to solve it in an iterative manner. Why do you want to use gradient method to solve (3.2)? It looks like a simple least squares problem in $\mathbf{x}_i$, where $\mathbf{x}_i$ is a column of $\mathbf{X}$. Commented Jul 19, 2019 at 18:20
• @Maxtron it indeed is a rather easy to solve 3.2. Thank you for the hint. I simply solved for X that minimizes 3.2 and worked like a charm. Thanks again :) Have a nice day Commented Jul 19, 2019 at 22:18
• @strahd anytime :) Commented Jul 20, 2019 at 19:00

The problem is given by:

$$$$\arg \min_{X} \frac{1}{2} \sum_{k} {\left\| {T}_{k} {X}_{:, k} - {Y}_{:, k} \right\|}_{2}^{2} + \lambda {\left\| G X \right\|}_{2, 1} \\ = \arg \min_{X} \frac{1}{2} \sum_{k} {\left\| {T}_{k} {X}_{:, k} - {Y}_{:, k} \right\|}_{2}^{2} + \lambda \sum_{l} {\left\| G {X}_{:, l} \right\|}_{2}$$$$

In the above the MATLAB notation of : is used to select a column.
It is also assumed that the Mixed Norm $${\left\| \cdot \right\|}_{2, 1}$$ is operating on each column. In case working on each rows is needed one could easily transpose $$X$$.

One could see above that the problem can be solved per column of $$X$$ independently. Hence it can be solved in a separable manner column of $$X$$ as a vector:

$${X}_{:, i} = \arg \min_{x} \frac{1}{2} {\left\| {T}_{i} x - {Y}_{:, i} \right\|}_{2}^{2} + \lambda {\left\| G x \right\|}_{2}$$

Now this is a simple problem which can be solved using Sub Gradient Descent and its accelerated variants.

The OP also mentions that $${T}_{k}$$ is the DFT matrix which is a Unitary Matrix namely it preserves the $${L}_{2}$$ norm. So the problem could be written:

\begin{aligned} \arg \min_{x} \frac{1}{2} {\left\| T x - y \right\|}_{2}^{2} + \lambda {\left\| G x \right\|}_{2} & = \arg \min_{x} \frac{1}{2} {\left\| {T}^{H} T x - {T}^{H} y \right\|}_{2}^{2} + \lambda {\left\| G x \right\|}_{2} \\ & = \arg \min_{x} \frac{1}{2} {\left\| x - {T}^{H} y \right\|}_{2}^{2} + \lambda {\left\| G x \right\|}_{2} \end{aligned}

In this form there is no need to calculate the DFT of $$x$$ each iteration.

Some of the Math derivation is given in my answer at The Sub Gradient and the Prox Operator of the of $${L}_{2, 1}$$ Norm (Mixed Norm).

• what's your favorite (clear, practical, electrical-engineering oriented) book on optimization theory ? Commented Jul 29, 2019 at 21:13
• @Fat32, You may have a look at my answer here - dsp.stackexchange.com/questions/59335. Though they are targeted on Convex Optimization. But I think it is better starting with it.
– Royi
Commented Jul 30, 2019 at 4:55
• Though I have been able to solve the problem, thanks for the great answer Commented Aug 1, 2019 at 11:41