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} + \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} \) 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.

asked 02 Jan '17, 05:59

Royi's gravatar image

Royi
113
accept rate: 0%

edited 13 Jul '17, 13:32


This can be solved by decomposing the Complex Matrices into their real part and imaginary part.
Then this becomes a real problem with \( 2 n \) variables.

link

answered 13 Jul '17, 13:33

Royi's gravatar image

Royi
113
accept rate: 0%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×190
×21
×4
×1

Asked: 02 Jan '17, 05:59

Seen: 1,123 times

Last updated: 13 Jul '17, 13:33

OR-Exchange! Your site for questions, answers, and announcements about operations research.