1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Note that $(A^H\epsilon\circ x) \ne A^H(\epsilon\circ x)$ $\endgroup$ – greg Dec 16 '19 at 0:45
  • $\begingroup$ 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}$ ? $\endgroup$ – The Dude Dec 16 '19 at 0:59
  • $\begingroup$ 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. $\endgroup$ – Alex Dec 16 '19 at 2:52
  • $\begingroup$ @Alex Because I am boxed in by my original formulation of the problem. Myopia induced by my own thinking. That is the only reason. $\endgroup$ – The Dude Dec 16 '19 at 22:04
  • $\begingroup$ @Alex Actually $x$ will have zero entries. Could you write an answer detailing that idea? $\endgroup$ – The Dude Dec 16 '19 at 22:11
2
$\begingroup$

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

Or you can avoid the gradient calculations completely by noting that you want the least-squares solution of a linear system, i.e.
$$Y\alpha = b \quad\implies \alpha = Y^+b $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your help. I appreciate you showing the calculations to help me learn what I did wrong. $\endgroup$ – The Dude Dec 16 '19 at 22:06

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.