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

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?

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

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

• Why does $\lvert \psi_k \rvert \leq \lvert b_k \rvert$ satisfy the rotation constraint? $\psi_k$ needs to be a rotated version of $b_k$, no? Commented Mar 9, 2020 at 15:24
• Good catch, updated to equality. Commented Mar 9, 2020 at 15:27