# Difference Between ${L}_{1}$ Regularized Least Squares Optimization Problem for Real and Complex Domain

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}$$?

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

$$\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

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

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

For simplicity defining:

$$$$\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}$$$$

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.