4
$\begingroup$

I would like to solve the following Regularized Least Squares Problem (Very Similar to LASSO):

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

Where $ A \in {\mathbb{R}}^{m \times n} $ and $ b \in {\mathbb{R}}^{m} $.
For simplicity one could define $ f \left( x \right) = \frac{1}{2} {\left\| A x - b \right\|}_{2}^{2} $ and $ g \left( x \right) = \lambda {\left\| x \right\|}_{1} $.

For $ x \in {\mathbb{R}}^{n} $ the solution can be achieved using Sub Gradient Method or Proximal Gradient Method.

My question is, how can it be solved for $ x \in {\mathbb{C}}^{n} $ (Assuming $ A \in {\mathbb{C}}^{m \times n} $ and $ b \in {\mathbb{C}}^{m} $)?
Namely if the problem is over the complex domain.

For instance, what is the Sub Gradient?
What is the Prox (Shrinkage of Complex Number)?

Thank You.

My Attempt for Solution 001

The Gradient of $ f \left( x \right) $ is given by:

$$ {\nabla}_{x} f \left( x \right) = {A}^{H} \left( A x - b \right) $$

The Sub Gradient of $ g \left( x \right) $ is given by:

$$ {\partial}_{x} g \left( x \right) = \lambda \operatorname{sgn} \left( x \right) = \lambda \begin{cases} \frac{x}{ \left| x \right| } & \text{ if } x \neq 0 \\ 0 & \text{ if } x = 0 \end{cases} $$

Namely it is the Complex Sign Function.

Then, the Sub Gradient Method is given by:

$$ {x}^{k + 1} = {x}^{k} - {\alpha}_{k} \left( {A}^{H} \left( A {x}^{k} - b \right) + \lambda \operatorname{sgn} \left( {x}^{k} \right) \right) $$

Where $ {\alpha}_{k} $ is the step size.

Yet it won't converge to CVX Solution for this problem.

Remark on Attempt 001

I think I understood why it doesn't work well.
The Absolute Value Function in the Complex Domain is (Quoted from Wikipedia Absolute Value Derivative Section):

enter image description here

$\endgroup$
  • $\begingroup$ @LinAlg, Why do you think so? $\endgroup$ – Royi Jan 1 '17 at 19:39
  • $\begingroup$ I was wrong, see my answer. $\endgroup$ – LinAlg Jan 1 '17 at 20:36
  • $\begingroup$ @LinAlg, I remember to do it. I will try it today and will mark it / comment accordingly. I really appreciate your efforts. By the way, My attempt was right. Just for strange reason solving those problems on the Complex Domain requires 2-3 folds more iterations. I really don't understand why. $\endgroup$ – Royi Jan 7 '17 at 11:14
  • $\begingroup$ Try an interior point solver for predictable performance. If you use matlab, YALMIP is a convenient way of formulating these problems. $\endgroup$ – LinAlg Jan 7 '17 at 11:47
  • $\begingroup$ @LinAlg, I'm trying to build a solve my self using Sub Gradient and Proximal Sub Gradient method. I actually made it for the Complex Formulation above (I will post code later). Yet it is so slow! I will try another formulation today. $\endgroup$ – Royi Jan 7 '17 at 13:11
4
$\begingroup$

Write $A = B + Ci$, $b=c+di$ and $x=y+zi$. The objective function is $$ \begin{align*}f(x) &= ||(B+Ci)(y+zi)-c-di||_1^2 + \lambda ||y+zi||_1 \\ &= ||By-Cz-c+(Cy+Bz-d)i||_2^2 + \lambda ||y+zi||_1 \\ &= ||By-Cz-c||_2^2 + ||Cy+Bz-d||_2^2 + \lambda \sum_{j=1}^n \sqrt{y_j^2+z_j^2} \\ &= \left\Vert\begin{pmatrix}B \\ -C \end{pmatrix}^T \begin{pmatrix}y\\z\end{pmatrix}-c\right\Vert_2^2 + \left\Vert\begin{pmatrix}C \\ B \end{pmatrix}^T\begin{pmatrix}y\\z\end{pmatrix}-d\right\Vert_2^2 + \lambda \sum_{j=1}^n \left\Vert\begin{pmatrix}e_j^T & 0 \\ 0 & e_j^T \end{pmatrix} \begin{pmatrix}y\\z\end{pmatrix}\right\Vert_2 \end{align*} $$ where $e_j$ is the $j^{th}$ unit vector. Finding the subgradient is now straightforward: $$ \begin{align*} 2\begin{pmatrix}B \\ -C \end{pmatrix} \left(\begin{pmatrix}B \\ -C \end{pmatrix}^T \begin{pmatrix}y\\z\end{pmatrix}-c\right) &+ 2\begin{pmatrix}C \\ B \end{pmatrix}\left(\begin{pmatrix}C \\ B \end{pmatrix}^T\begin{pmatrix}y\\z\end{pmatrix}-d\right) \\ &+ \lambda \sum_{j=1}^n \frac{\begin{pmatrix}e_j^T & 0 \\ 0 & e_j^T \end{pmatrix}^T \begin{pmatrix}e_j^T & 0 \\ 0 & e_j^T \end{pmatrix} \begin{pmatrix}y\\z\end{pmatrix}}{\left\Vert\begin{pmatrix}e_j^T & 0 \\ 0 & e_j^T \end{pmatrix} \begin{pmatrix}y\\z\end{pmatrix}\right\Vert_2} \end{align*}$$

$\endgroup$
  • $\begingroup$ I think you missed the $ b $ there (It also can be complex). Moreover, I think it should be $ -Cz $. Any other more general approach? $\endgroup$ – Royi Jan 2 '17 at 6:37
  • $\begingroup$ Thanks, fixed. What do you mean by 'more general approach'? $\endgroup$ – LinAlg Jan 2 '17 at 9:49
  • $\begingroup$ I still don't understand how to derive the Sub Gradient (With respect to $ x $) from your function. Can you see my attempt of solution above? $\endgroup$ – Royi Jan 2 '17 at 10:13
  • $\begingroup$ The variables are now $y$ and $z$. $\endgroup$ – LinAlg Jan 2 '17 at 11:46
  • $\begingroup$ Could you please write it explicitly? I understood there are 2 variable, now how could you apply Sub Gradient Method on both at once? Moreover, what's wrong with my attempt? Thank You. $\endgroup$ – Royi Jan 2 '17 at 11:56

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.