# 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


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.