Logan Nielsen
← All notes

Note · Controls

Weighted Minimum Norm Problem

Generalization of Minimum Norm Problem

October 8, 2021 · 2 min read

Consider the minimum weighted norm problem given by

x∗=arg min⁡xxHQx  s.t.  Ax=b\begin{align} \pmb x^* = \argmin_{\pmb x} \pmb x^HQ\pmb x\ \ s.t. \ \ A\pmb x = \pmb b \end{align}

Where QQ is positive definite. and A∈Cm×nA \in \mathbb C^{m \times n} where m<nm < n

Solution

Since QQ is positive definite there exists a factorization Q=RHRQ = R^H R where RR is invertible.

We define a change of variables z=Rx  ⟹  x=R−1z\pmb z= R\pmb x \implies \pmb x = R^{-1} \pmb z.

Rewriting our problem in terms of the factorization and the change of variables we have

z∗=arg min⁡x (R−1z)H(RHR)(R−1z)  s.t.  AR−1z=b=arg min⁡z zHz  s.t.  AR−1z=b=arg min⁡z ∥z∥  s.t.  AR−1z=b\begin{align*} \pmb z^* &= \argmin_{\pmb x}\ (R^{-1} \pmb z)^H (R^HR)(R^{-1} \pmb z)\ \ s.t.\ \ AR^{-1}\pmb z = \pmb b \\[15pt] &= \argmin_{\pmb z}\ \pmb z^H\pmb z\ \ s.t.\ \ AR^{-1}\pmb z = \pmb b \\[15pt] &= \argmin_{\pmb z}\ \rVert\pmb z\lVert \ \ s.t.\ \ AR^{-1}\pmb z = \pmb b \end{align*}

Define T=AR−1T = AR^{-1}

z∗=arg min⁡z ∥z∥  s.t.  Tz=b\begin{align*} \pmb z^* = \argmin_{\pmb z}\ \rVert\pmb z\lVert \ \ s.t.\ \ T\pmb z = \pmb b \end{align*}

We now have a minimization problem in the usual form.

z=THc∧c=(TTH)−1b=TH(TTH)−1b=(AR−1)H(AR−1(AR−1)H)−1b=R−1HAH(AQA)−1b\begin{align*} \pmb z &= T^H\pmb c \quad \land \quad \pmb c = (TT^H)^{-1}\pmb b \\ &= T^H (TT^H)^{-1}\pmb b \\ &= (AR^{-1})^H(AR^{-1}(AR^{-1})^H)^{-1}\pmb b \\ &= R^{-1H}A^H(AQA)^{-1}\pmb b \end{align*}

Recall that our change of variables defined z=Rx\pmb z = R \pmb x. Now

Rx=R−1HAH(AQA)bx=R−1R−1HAH(AQA)b=(RHR)−1AH(AQA)b=Q−1AH(AQA)−1b\begin{align*} R\pmb x &= R^{-1H}A^H(AQA)\pmb b \\ \pmb x &= R^{-1}R^{-1H}A^H(AQA)\pmb b \\ &= (R^H R)^{-1}A^H(AQA)\pmb b \\ &= Q^{-1}A^H(AQA)^{-1}\pmb b \end{align*}