0
$\begingroup$

I have implemented a Least Squares Optimization with $ {L}_{1} $ Norm Regularization for the problem. My reference was - Least Squares Optimization with L1 Norm Regularization by Mark Schmidt.

The paper discuss the problem of solving:

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

The paper assume all variables are under the real domain. Namely $ A \in \mathbb{R}^{m \times n}, \; x \in \mathbb{R}^{n}, \; b \in \mathbb{R}^{m} $.
How would one solve the problem over the complex domain where $ A \in \mathbb{C}^{m \times n}, \; x \in \mathbb{C}^{n}, \; b \in \mathbb{C}^{m} $?

$\endgroup$
  • $\begingroup$ Replace $x$ with $ x+ iy$ and optimize over $x$ and $y$. $\endgroup$ – LinAlg Jan 25 '17 at 8:29
  • $\begingroup$ @LinAlg so if we consider real and imaginary part as two different variable,both should converse? $\endgroup$ – Creator Jan 25 '17 at 8:39
  • $\begingroup$ What do you mean by converse? Also see my answer here. $\endgroup$ – LinAlg Jan 25 '17 at 10:32
1
$\begingroup$

$$\DeclareMathOperator{\sign}{sign} \DeclareMathOperator{\prox}{prox} \DeclareMathOperator{\diag}{diag} \DeclareMathOperator{\tr}{tr} \newcommand{\MyParen}[1]{\left( #1 \right)} \newcommand{\MyBrack}[1]{\left\lbrack #1 \right\rbrack} \newcommand{\MyBrace}[1]{\left\lbrace #1 \right\rbrace} \newcommand{\MyNorm}[2]{{\left\| #1 \right\|}_{#2}} \newcommand{\MyNormSqr}[2]{{\left\| #1 \right\|}_{#2}^{2}} \newcommand{\MyNormTwo}[1]{\MyNorm{#1}{2}} \newcommand{\MyNormTwoSqr}[1]{\MyNormSqr{#1}{2}} \newcommand{\MyAbs}[1]{\left| #1 \right|} \newcommand{\MyCeil}[1]{\left \lceil #1 \right \rceil} \newcommand{\MyFloor}[1]{\left \lfloor #1 \right \rfloor} \newcommand{\MyProd}[2]{\langle #1, #2 \rangle} \newcommand{\MyUndBrace}[2]{\underset{#2}{\underbrace{#1}}} % \newcommand{\RR}[1]{\mathds{R}^{#1}} % Asaf's Style \newcommand{\RR}[1]{\mathbb{R}^{#1}} \newcommand{\EE}[1]{\mathbb{E} \MyBrack{#1}}$$

Solve the problem

$$\begin{equation} \label{eq:LSL1ObjFun} \arg \min_{x} \left\{ \frac{1}{2} {\left\| A x - b \right\|}_{2}^{2} + \lambda {\left\| x \right\|}_{1} \right\} \end{equation}$$

Where $ A \in {\mathbb{C}}^{m \times n} $, $ x \in {\mathbb{C}}^{n} $ and $ b \in {\mathbb{C}}^{m} $.

For simplicity defining:

$$\begin{equation} \label{eq:LSL1Fun} f \left( x \right) = \frac{1}{2} {\left\| A x - b \right\|}_{2}^{2} + \lambda {\left\| x \right\|}_{1} \tag{eq:LSL1Fun} \end{equation}$$

The $ {\ell}_{1} $ norm of a complex vector is defined as:

$$ \MyNorm{z}{1} = \sum_{k = 1}^{n} \sqrt{\Re^{2} \MyParen{ {z}_{k} } + \Im^{2} \MyParen{ {z}_{k} } } $$

By definition $ A = B + i C $, $ x = y + i z $ and $ b = c + i d $.
By setting $ \hat{A} = \begin{bmatrix} B & -C \\ C & B \end{bmatrix} $ and $ \hat{b} = \begin{bmatrix} c \\ d \end{bmatrix} $ one could rewrite Equation \ref{eq:LSL1Fun} as:

$$ f \left( y, z \right) = \frac{1}{2} \MyNormTwo{ \hat{A} \begin{bmatrix} y \\ z \end{bmatrix} - \hat{b} }^{2} + \lambda \sum_{j = 1}^{n} \sqrt{ {y}_{j}^{2} + {z}_{j}^{2} } $$

From here one could use classic methods to solve the problem.

$\endgroup$

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.