3
$\begingroup$

Let $ \mathbf{x}_m = \mathbf{z}_m - \alpha\mathbf{v} \in \mathbb{C}^N$, with $m=1,\dots,M$, be $M$ complex vectors such that

  1. $\mathbf{z}_m, m=1,\dots,M$ and $\mathbf{v}$ complex $N$-dimensional vectors,
  2. $\alpha$ a complex scalar.

Define the matrix $\mathbf{X}$ of dimension $N\times M$ as: $$ \mathbf{X} = [\mathbf{x}_1|\mathbf{x}_2|\cdots|\mathbf{x}_M]. $$ How can I solve the following minimization problem: $$ \min_{\alpha}\det(\mathbf{I} + \mathbf{X}^H\mathbf{S}^{-1}\mathbf{X}) $$ where

  1. $\mathbf{I}$ indicates the identity matrix of dimension $M \times M$,
  2. $\mathbf{S}$ is an invertible, Hermitian and positive definete matrix of dimension $N \times N$.

Thanks!

$\endgroup$
  • $\begingroup$ So H is conjugate transpose or something else? $\endgroup$ – mathreadler Mar 7 '17 at 10:26
  • $\begingroup$ Like most optimization problems: compute the derivative (using Jacobi formula) and set it to zero. $\endgroup$ – Simon Mar 7 '17 at 10:32
  • $\begingroup$ Yes, H is the conjugate transpose. I tried to use the Jacobi formula, but I was not able to obtain a closed form solution... $\endgroup$ – Vuk Mar 7 '17 at 10:59
2
$\begingroup$

In addition to $(V,Z)$ that Hans used, let's also define $$\eqalign{ Q &= S^{-1/2} \cr P &= \alpha^2VV^H-\alpha(VZ^H+ZV^H)+ZZ^H+S \cr }$$ I'm also going to insist that $\alpha$ is real, and all of the "complexity" is baked into the ${\mathbf v}$ vector.

Anyway, Sylvester's Theorem allows us to rewrite the determinant as $$\eqalign{ f &= \det(I+X^HQ^HQX) \cr &= \det(I+QXX^HQ^H) \cr &= \det\Big(Q(S+XX^H)Q\Big) \cr &= \det(Q)^2\,\,\det(S+XX^H) \cr\cr f\det(S) &= \det(S+XX^H) \cr &= \det\Big(S+(\alpha V-Z)(\alpha V-Z)^H\Big) \cr &= \det\Big(\alpha^2VV^H-\alpha(VZ^H+ZV^H)+ZZ^H+S\Big) \cr &= \det(P) \cr }$$ The derivative wrt $\alpha$ is $$\eqalign{ \frac{d\det(P)}{d\alpha} &= \det(P)P^{-T}:\frac{dP}{d\alpha} \cr &= \det(P)P^{-T}:(2\alpha VV^H-VZ^H-ZV^H) \cr }$$ Setting the derivative to zero yields $$\eqalign{ 2\alpha(VV^H:P^{-T}) &= (VZ^H+ZV^H):P^{-T} \cr\cr \alpha &= \frac{(VZ^H+ZV^H):P^{-T}}{(VV^H+VV^H):P^{-T}} \cr\cr }$$ This is an iterative equation rather than a solution, since $P$ on the RHS is a function of $\alpha$.
I have no idea if the iteration converges or diverges, but you can try it and see.

$\endgroup$
  • $\begingroup$ Thanks! From other consideration about this problem, I'm quite sure that a close form exists and it is of the form: [ \alpha_0=\frac{1}{M\mathbf{v}^H\mathbf{S}^{-1}\mathbf{v}}\su‌​m\nolimits_{m=1}^{M_‌​1}\mathbf{v}^H\mathb‌​f{S}^{-1}\mathbf{x}_‌​m, ] but I'm not able to prove it... $\endgroup$ – Vuk Mar 28 '17 at 13:20
  • $\begingroup$ Since the $\{x_m\}$ vectors are themselves functions of $\alpha,\,$ I don't see how your assumed expression is a solution. Rather, like my own answer, it appears to be a recursive definition of the form $$\alpha = f(\alpha)$$ $\endgroup$ – greg Mar 28 '17 at 14:17
  • $\begingroup$ Sorry, you are right of course! x_m should be z_m in my previous post $\endgroup$ – Vuk Mar 28 '17 at 16:38
2
$\begingroup$

Define $$\eqalign{ V & = v1^T \cr Z & = [z_1 | z_2| \ldots | z_M] \cr X & = \alpha V-Z \cr M & = I + X^HS^{-1}X \,\,= M^H \cr \cr }$$

Then $$\eqalign{ f &= \det M \cr \cr df &= fM^{-T}:dM \cr &= fM^{-T}:X^HS^{-1}dX \cr &= fM^{-T}:X^HS^{-1}V\,d\alpha \cr \cr \frac{df}{d\alpha} &= fM^{-T}:X^HS^{-1}V \cr &= f\,1^TM^{-1}X^HS^{-1}v \cr\cr }$$ Set the derivative to zero and apply the Woodbury formula to the $M$ term $$\eqalign{ 0 &= 1^T\Big(I-X^H(S+XX^H)^{-1}X\Big)X^HS^{-1}v \cr 1^TX^HS^{-1}v &= 1^TX^H(S+XX^H)^{-1}XX^HS^{-1}v \cr \cr }$$ In order to continue, each of the $X$'s must be expanded into $(\alpha V-Z)$, and then rearranged to solve for $\alpha$. At this point, an algebraic solution doesn't look very promising.

However, since this is a just a scalar function ($f$) of a scalar variable ($\alpha$), a numerical solution should be easy. And you will have the exact formula for ($df/d\alpha$) at each step in the iteration, which will improve speed and accuracy.

$\endgroup$

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.