Euclidean norm minimization using rotations, i.e., $\min\limits_\mathbf\Phi \lVert \mathbf{A \Phi b} \rVert_2^2$

Question

Given the following minimization $$\min\limits_\mathbf\Phi \lVert \mathbf{A \Phi b} \rVert_2^2$$ where $\mathbf A$ and $\mathbf b$ are a complex matrix and vector, respectively, and $$ \mathbf \Phi = \begin{bmatrix} e^{j\phi_1} & \cdots & 0\\ \vdots & \ddots & \vdots\\ 0 & \cdots & e^{j\phi_N}\, \end{bmatrix}$$ is a diagonal matrix of rotations.

How would the rotations $\{\phi_1,\ldots,\phi_N\}$ that minimize the cost function be found? I tried minimizing each rotation independently, but sometimes it leads to a local minimum.

What is the intuition about why the rotations would produce a smaller norm? Is there a geometric explanation?

Is there a reference where this problem has been studied?

Answer 1

Try the parameterization $\psi_k = e^{j \phi_k} b_k$. This change of variables yields $\lVert A \psi \rVert^2 = \psi^\top A^\top A \psi$, which is convex in $\psi$ and where the optimality condition is at

$$ \frac{\mathrm{d}}{\mathrm{d} \psi} \psi^\top A^\top A \psi = 2 A^\top A \psi = 0 $$

It remains to find $\psi$ such that each component $\lvert \psi_k \rvert = \lvert b_k \rvert$ to satisfy the rotation constraint.

A geometric interpretation of this is that $b$ is some fixed input, $A$ is fixed that we are feeding $b$ into, but before this application we are able to adjust each component of $b$ so that the modified input $\Phi b$ produces a smaller norm when fed into $A$.

Answer 2

$\def\p#1#2{\frac{\partial #1}{\partial #2}}\def\d{{\rm diag}}\def\D{{\rm Diag}}$For typing convenience, let $P=\Phi$ and also define the associated vector $p$ $$\eqalign{ p &= \d(P) \quad&\iff\quad P &= \D(p) \quad\implies\quad Pv = p\odot v\\ p_k &= e^{i\phi_k} \quad&\implies\quad dp &= ip\odot d\phi \;=\; iP\,d\phi \\ }$$ where $\odot$ denotes the elementwise/Hadamard product. And let's denote the trace/Frobenius product using a colon, i.e. $$\eqalign{ A:B &= {\rm Tr}(A^TB) \\ A^*:A &= \big\|A\big\|^2_F \\ }$$ Finally, it will also be convenient to define the matrices $$\eqalign{ M &= (bb^H)^*\odot A^HA \;\;=\;\; b^*b^T\odot A^HA \\ Q &= A^HAPbb^H \quad\iff\quad \d(Q) = Mp \\ }$$

Write the cost function, calculate its gradient, set it zero, and solve for the optimal $p$ vector.
$$\eqalign{ {\cal C} &= (APb)^*:APb \\ d{\cal C} &= A^*P^*b^*:A\,dP\,b &+\quad APb:A^*\,dP^*\,b^* \\ &= Q^*:dP \quad&+\quad conj \\ &= Q^*:\D(dp) \quad&+\quad conj \\ &= \d(Q^*):dp \quad&+\quad conj \\ &= M^*p^*:ip\odot d\phi \quad&+\quad conj \\ &= ip\odot M^*p^*:d\phi \quad&+\quad i^*p^*\odot Mp:d\phi \\ &= 2\;{\rm Real}(ip\odot M^*p^*):d\phi \\ &= 2\;{\rm Imag}(p^*\odot Mp):d\phi \\ \p{\cal C}{\phi} &= 2\;{\rm Imag}(p^*\odot Mp) \;\doteq\; 0 \\ }$$ Since $(p^*\odot p)$ is a real vector, this implies that if $Mp$ is a multiple of $p$ it will satisfy the zero gradient condition. Or in other words $$Mp = \lambda p$$ and therefore $p$ is an eigenvector of $\;(bb^H)^*\odot A^HA\;$ and the required angles are the elementwise logarithms $$\phi_k = -ip_k$$

---

To follow the above derivation, it's helpful to know that the Hadamard and Frobenius products commute with one another $$\eqalign{ B\,:\,C &= C\,:\,B \\ B\odot C &= C\odot B \\ A\odot B\,:\,C &= A\,:\,B\odot C \\ }$$ and that the cyclic property of the trace allows the terms in a Frobenius product to be rearranged in a number of different ways, e.g. $$\eqalign{ A:B &= B:A = B^T:A^T \\ CA:B &= C:BA^T = A:C^TB \\ }$$