2
$\begingroup$

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. Thanx in advance and have a nice day!

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Irreducible Jul 19 at 12:47
  • $\begingroup$ @Irreducible Honestly I have asked the same question at math.stackexchange however got no response. You are correct though. $\endgroup$ – strahd Jul 19 at 13:03
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Maxtron Jul 19 at 18:20
  • $\begingroup$ @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 $\endgroup$ – strahd Jul 19 at 22:18
  • $\begingroup$ @strahd anytime :) $\endgroup$ – Maxtron Jul 20 at 19:00
3
$\begingroup$

The problem is given by:

$$\begin{equation} \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} \end{equation}$$

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).

$\endgroup$
  • $\begingroup$ what's your favorite (clear, practical, electrical-engineering oriented) book on optimization theory ? $\endgroup$ – Fat32 Jul 29 at 21:13
  • $\begingroup$ @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. $\endgroup$ – Royi Jul 30 at 4:55
  • $\begingroup$ Though I have been able to solve the problem, thanks for the great answer $\endgroup$ – strahd Aug 1 at 11:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.