# Solving: $\underset{\alpha}{\text{min}} \; || \left( b - A(\alpha \circ x ) \right) ||_{2}^{2}$

I want to solve the following minimization problem:

$$\underset{\alpha}{\text{min}} \; || \left( b - A(\alpha \circ x ) \right) ||_{2}^{2}$$

where $$\alpha, x \in \mathbb{C}^{N}$$ and $$b \in \mathbb{C}^{M}$$ and $$A \in \mathbb{C}^{M \times N}$$ and $$\circ$$ denotes the Hadamard product.

This can be done using gradient descent. Since the objective function is convex and analytic, we just need to find the $$\alpha$$ such that the gradient $$\frac{d}{d \alpha} = 0$$

To start, we rewrite the objective as:

$$f(\alpha) = || \left( b - A(\alpha \circ x ) \right) ||_{2}^{2} = ( b - A(\alpha \circ x ))^{H}( b - A(\alpha \circ x )) = \epsilon^{H} \epsilon$$

Now we can compute the differential:

$$f = \epsilon: \epsilon$$ $$df = 2\epsilon : d\epsilon = 2 \epsilon : d(b - A(\alpha \circ x )) = -2\epsilon: A( x \circ d \alpha)$$ $$df = -2 A^{H} \epsilon : x \circ d \alpha$$ $$\boxed{df = -2 A^{H} (\epsilon \circ x) : d \alpha}$$

Now this is where I am confused. According to the first identification theorem for differentials, the gradient should be:

$$\boxed{\frac{df}{d \alpha} = -2 (\epsilon \circ x)^{H} A}$$

And so the gradient descent update is:

$$\boxed{\alpha_{k+1} = \alpha_{k} + 2 \mu (\epsilon \circ x)^{H} A}$$

However, when minimizing $$|| b-Ax ||_{2}^{2}$$ wrt $$x$$, the derivative should be:

$$\frac{df}{d x} = 2 A^{T}(b - Ax)$$

So where did I go wrong? What should the gradient be?

• Note that $(A^H\epsilon\circ x) \ne A^H(\epsilon\circ x)$ – greg Dec 16 '19 at 0:45
• So is that where I am going wrong? So then we would have $df = -2A^{H} \epsilon \circ x : d \alpha$ which would mean that the derivative is $\frac{df}{d \alpha} = (-2A^{H} \epsilon \circ x)^{H} = -2 \epsilon^{H} A \circ x^{H}$ ? – The Dude Dec 16 '19 at 0:59
• Why do you want to solve this directly in $\alpha$ rather than minimizing with respect to $(\alpha \odot x)$ then solving for $\alpha$? The only difference comes in when $x$ has zero entries. In that case, you can simply delete columns of A corresponding to places where $x$ has zero. – Alex Dec 16 '19 at 2:52
• @Alex Because I am boxed in by my original formulation of the problem. Myopia induced by my own thinking. That is the only reason. – The Dude Dec 16 '19 at 22:04
• @Alex Actually $x$ will have zero entries. Could you write an answer detailing that idea? – The Dude Dec 16 '19 at 22:11

Define the matrices \eqalign{X &= {\rm Diag}(x),\quad Y &= AX \\} Reformulate the objective function to get rid of the Hadamard product (and the minus sign). \eqalign{ \phi &= (Y\alpha-b)^*:(Y\alpha-b) \\ d\phi &= (Y\alpha-b)^*:Y\,d\alpha \,\,\;+\; (Y\alpha-b):Y^*\,d\alpha^* \\ &= Y^T(Y\alpha-b)^*:d\alpha \;+\; Y^H(Y\alpha-b):d\alpha^* \\ \frac{\partial\phi}{\partial\alpha} &= Y^T(Y\alpha-b)^*,\quad \frac{\partial\phi}{\partial\alpha^*} = Y^H(Y\alpha-b) \\ } Set the gradient (it doesn't matter which one) to zero and solve for the optimal value. \eqalign{ Y^HY\alpha &= Y^Hb \\ \alpha &= (Y^HY)^{-1}Y^Hb \\&= Y^+b \\ } Notes:
$$\quad(b-Y\alpha)=\epsilon\;$$ in your terminology
$$\quad Y^+\;$$ is the Moore-Penrose inverse
$$Y\alpha = b \quad\implies \alpha = Y^+b$$