Prove the existence of an improvement on the diagonal matrix in this optimization problem

119 Views Asked by At

Given $$ D = \begin{pmatrix} d_{1}^{2} & 0 & \cdots & 0 \\\ 0 & d_{2}^{2} & \cdots & 0 \\\\ \vdots & \vdots & \ddots & 0 \\\\ 0 & 0 & \cdots & d_{m}^{2} \end{pmatrix}$$ $$ U = \begin{pmatrix} u_{1}^{2} & 0 & \cdots & 0 \\\\ 0 & u_{2}^{2} & \cdots & 0 \\\\ \vdots & \vdots & \ddots & 0 \\\\ 0 & 0 & \cdots & u_{m}^{2} \end{pmatrix}$$ are two diagonal, $m \times m$, positive definite matrices.

Optimization Problem: $$ \max \hspace{5, pt} Tr\left( (A^\intercal D A)^{1/2} \right)$$ subject to the constraint that $$ (A^\intercal A)^{2} = A^\intercal U A$$ where the decision variable $A$ is an $m \times n$ matrix with $n \leq m$. Let $A^{* }$ be the global solution to this problem and $A^{0}$ be the $m \times m$ diagonal matrix that satisfies the constraint. I want to show that if $A^{*} \neq A^{0}$, then there exists an $m \times n$ matrix $A^{** }$ with $n < m$ that does better than the diagonal matrix $A^{0}$, such that there is exactly 1 nonzero entry in each row of $A^{** }$.

i.e. $ Tr\left( (A^{ ** ^\intercal} D A^{** })^{1/2} \right) > Tr\left( (A^{ 0 ^\intercal} D A^{0 })^{1/2} \right) $ for some $ A^{** }$ such that $$ (A^{ ** ^\intercal} A^{ ** })^{2} = A^{ ** ^\intercal} U A^{ ** }$$ and for all $ 1 \leq i \leq m$,

$a_{ik}^{** } \neq 0 \iff \forall j \neq k: \space 1 \leq j \leq n, \space a_{ij}^{** } = 0$